快速幂算法

存在意义

顾名思义，为了能快速计算指数很高的幂。

算法思路

不断将指数减半，同时底数作平方运算，如此不断减少所需执行的次数，减小指数

举个例子来说明，计算：

常规计算需要做10次计算，即2*2*2*2*2*2*2*2*2*2，当指数非常大的时候，这样计算显然会非常慢。

快速幂过程：

1、指数减半，底数平方得：

2、指数变成奇数，无法减半，则分离出1来，即： =  * 4，再对进行指数减半操作，记下分离出来的4

3、对指数减半，底数平方，得： * 4

4、相同操作： * 4 =  * 4，指数变为奇数，分离出1来， * 4 =  * 256 * 4，记下256，此时指数为0，结束计算

5、综上， =  * 256 * 4 = 1024

用代码实现：

def Faspow(a,n):
    answer = 1
    while(n > 0):
        if n % 2 == 0:#指数为偶数就减半
            n = n / 2
            a = a * a
        else:#指数为奇数就提1
            answer = answer * a
            n = n - 1
            n = n / 2
            a = a * a
    return answer
a = int(input("请输入底数："))
n = int(input("请输入指数："))
result = Faspow(a,n)
print(result)

改进，这两句显得有点重复

n = n - 1
n = n / 2

def Faspow(a,n):
    answer = 1
    while(n > 0):
        if n % 2 == 1:
            answer = answer * a
        n = n // 2
        a = a * a
    return answer
a = int(input("请输入底数："))
n = int(input("请输入指数："))
result = Faspow(a,n)
print(result)