1.簡單遞歸
最簡單的求冪算法是根據xn=x*xn-1，使用遞歸：
def foo(x,n): if n==0: return 1 else: return x*foo(x,n-1)
這樣求x的n次方，會進行n-1次乘法運算，n較大時效率很低。
2.高效遞歸
一種更高效的算法，可以將運算次數降到LogN的級別，由于：
xn=xn/2*xn/2 ， n為偶數時
xn=x(n-1)/2*x(n-1)/2*x ， n為奇數時
def foo(x,n): if n==0: return 1 else: if n%2==0: return foo(x,n/2)*foo(x,n/2) else: return foo(x,n/2)*foo(x,n/2)*x
可以將運算次數降到LogN的級別。
3.快速求冪
還有一種快速求冪算法，稱為二進制法：
比如求x的21次方，21的二進制為10101,由于x21=x16*x4*x1，可以看出根據二進制表示(10101)，每當遇到1時，則乘以x，從右向左前進一位則將x自乘。
def foo(x,n): result=1 while n: if (n&1): result*=x x*=x n>>=1 return result
這個算法用來計算非常的大的數時是十分高效的。例如有很多的素數測試算法都是依賴這個算法的不同變式。
4.抽象化
然后在某個地方我看到一個很有意思的想法，就是把上面的算法中的自乘函數化：
def foo(x,n,i,func): result=i while n: if (n&1): result=func(result,x) x=func(x,x) n>>=1 return resultif __name__=='__main__': PRint foo(2,16,1,lambda x,y:x*y)
這樣求x的n次方就能用foo(x,n,1,lambda x,y:x*y)來運算了。
如果求x*n，相當于將x自加n次，可以用foo(x,n,0,lambda x,y:x+y)來運算：
def foo(x,n,i,func): result=i while n: if (n&1): result=func(result,x) x=func(x,x) n>>=1 return resultif __name__=='__main__': print foo(2,16,0,lambda x,y:x+y)
如果要把某個字符x重復n次，可以用：
def repeat(x,n,i,func): result=i while n: if (n&1): result=func(result,x) x=func(x,x) n>>=1 return resultif __name__=='__main__': print repeat('a',16,'',lambda x,y:x+y)把一個列表復制n次：
def repeat(x,n,i,func): result=i while n: if (n&1): result=func(result,x) x=func(x,x) n>>=1 return resultif __name__=='__main__': print repeat([1,2],16,[],lambda x,y:x+y)
參考自：http://videlalvaro.github.io/2014/03/the-power-algorithm.html
新聞熱點
疑難解答
