本文主要是介绍欧几里德算法(幂运算)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文中X(N) 表示X的N次方；
计算X(N) 的明显算法是使用N-1次乘法自乘，有一种递归算法更好：N≤1是这种递归的基准情形，否则若N为偶数，我们有X(N) = X(N/2) × X(N/2)，若X为奇数，则X(N) = X((N-1)/2) × X((N-1)/2) × X
例如：为了计算X(62)，算法将如下进行，它只用到9次乘法：
X(62) = (X(31))2，X(31) = (X(15))2 × X，X(15) = (X(7))2 × X，X(7) = (X(3))2 × X，X(3) = X(2) × X
在图中，第20行到第22行实际上是不需要的，因为如果N=1，那么27行将做同样的事情，
第27行还可以写成：
return pow(x,n-1) * x;
而不影响程序的正确性。事实上程序仍将以O(log n) 运行，但是下面所有对第24行的修改都是不可取的，最然它们看起来都正确：
1，return pow(pow(x,2),n/2);
2, return pow(pow(x,n/2),2);
3, return pow(x,n/2) * pow(x,n/2);
第一行和第二行都是不正确的，因为当N=2时递归调用pow中有一个是以2作为第二个参数。这样程序会有一个无限循环，将不能继续运行；
第三行会影响程序的效率，因为此时有两个大小为N/2的递归调用而不是一个。
这篇关于欧几里德算法(幂运算)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
