x^n的算法—python

参考链接@小泡芙吖

三种方法的原理都是一样的
对于n，先将其换成二进制形式，在这里举个例子，假设n=11，其二进制形式是1011
从左边数的第二位开始，若等于0，则对x进行平方，若为1，则先对当前结果进行平方，再乘上x。

方法一：

# 11 -> 1011
# x^11=(((x)^2)^2*x)^2*2
def do(x, n):
    b = []
    res = 1

    while n > 0:
        b.append(n % 2)
        n //= 2

    for i in range(len(b), 0, -1):
        if b[i - 1]:
            res = res * res * x
        else:
            res = res * res

    return res

方法二：

# 11 -> 1011
# x^11=x^1*x^2*x^8
def do(x, n):
    res = 1
    tmp = x

    while n > 0:
        if n % 2:
            res *= tmp
        tmp = tmp * tmp
        n = n // 2

    return res

方法三：

# 递归法
# X^n可以分成三种情况
# 1.X，n=1;
# 2.X^(n/2),n>1,n%2=1;
# 3.X^(n/2),n>1,n%2=0;
def rec(x, n):
    if n == 1:
        return x

    y = rec(x, n // 2)

    if n % 2:
        return y * y * x
    else:
        return y * y