作业六：从乘法到指数运算

计算机数学

题目：我们第一个作业是让大家做两个整数相乘，看上去非常没有意义，其实过程非常有启发性。从这个思路出发，我们可以有一种快速的求指数的算法。即，给定整数a、x和n，求a的x次方mod n。请实现一种快速求指数的算法（命名为pow）。

递归

#递归
#求指数
def f(a,x):
    #递归终止条件
    if x==1: return a
    #x是偶数时，即求a的偶数次幂
    if x%2==0:
        #分解为等分的左右两个子问题
        return f(a,x//2)*f(a,x//2)
    #x是奇数时，即求a的奇数次幂
    if x%2!=0:
        #分解为左边偶数个a相乘(x//2)和右边奇数个a相乘((x//2)+1)
        return f(a,x//2)*f(a,(x//2)+1)
#取模运算
def Pow(a,x,n):
    return f(a,x)%n
#测试
print(Pow(2,10,17))

迭代

#迭代
def Pow(a,x,n):
    result=1
    while(x!=0):
        #判断x是否为奇数，若是，则result乘以单独的一个a
        if(x%2):
            result*=a
        #x减半
        x=x//2
        #求a平方
        a*=a
    return result%n
print(Pow(2,10,17))