请享用美味的快速幂算法-通俗易懂版

一、算法整体思路
第1步
　　按照最直接、最好理解的方式看，2的n次幂是n个2相乘，即有如下公式

　　例如：

第2步
　　然而为了节省大量时间，通过简单的思考和严格数学推理，我们不难理解以下结论：
        　　1.偶数幂的情况:
　　　　通过幂函数运算法则，有2n=（2n/2）2，即有如下等式：

　　　　例如24　的计算过程如下所示：

　　　　得到上面的表达式后，22是不是可以继续按照这个思想分解下去？of course！现在只是举了一个4次方的例子，我们可以从此得到启发，发现求n次幂最终可以归结为不断的重复这个分解的一个过程，直到幂不能分解（幂为0了）才停下来。
　　　　由此，上述过程可以描述为一个递归过程，递归基（递归结束条件）为”幂等于0“。得到以下递归表达式：

　　小插叙：
　　　　解释第二种情况前，有必要说明以下内容，这也是为什么第二种情况存在的原因：
　　　　如果n是奇数，我们知道，在计算机中，n/2会舍去小数，这样如果继续按照上述第一步的方法分解，逆推回去，会发现最终得到的幂是n-1；不信，且看下例

 
        　　2.奇数幂的情况：
　　　　好了，现在可以引出第二种情况，就是奇数幂的情况。我们要求得奇数幂的结果，可以从继续步骤1,即按照偶数幂的求法求出最终结果，再附加一个条件是，什么条件呢？
　　　　就是在原来的结果上乘上一个2，原因我相信在插叙中已经说的很明白了，它少了1次幂，现在是在补上这一次幂，即：

 　　3.最终递归表达式
　　　　那么到现在，我们可以写出完整的递归表达式了，在偶数幂的递归条件下，附加奇数幂的条件即可，即：

 
第3步
　　我们现在对于快速幂的求解思路应当是已经十分清晰了，现在我们来写递归函数(C++):

1. long long int fastpower(int n){
2.     if (n == 0)//递归基
3.         return 1;
4.     else if (n % 2 == 0)//偶数幂的情况
5.         return square(fastpower(n / 2));
6.     else//奇数幂的情况
7.         return square(fastpower(n / 2)) * 2;
8. }
9. long long int square(long long int t){
10.     return t * t;
11. }

复制代码

 
二、上刑
　　everybody，现在我们已经完全理清了思路，接下来要把它整成代码吧！
[code]#includeusing namespace std;long long int fastpower(int n);//求解快速幂long long int square(long long int t);//平方int main(void){    int n;    cin >> n;//输入幂    cout