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

一、算法整体思路

第1步

  按照最直接、最好理解的方式看,2的n次幂是n个2相乘,即有如下公式

  例如:

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

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

    得到上面的表达式后,22是不是可以继续按照这个思想分解下去?of course!现在只是举了一个4次方的例子,我们可以从此得到启发,发现求n次幂最终可以归结为不断的重复这个分解的一个过程,直到幂不能分解(幂为0了)才停下来。

    由此,上述过程可以描述为一个递归过程,递归基(递归结束条件)为”幂等于0“。得到以下递归表达式:

  小插叙:

    解释第二种情况前,有必要说明以下内容,这也是为什么第二种情况存在的原因:

    如果n是奇数,我们知道,在计算机中,n/2会舍去小数,这样如果继续按照上述第一步的方法分解,逆推回去,会发现最终得到的幂是n-1;不信,且看下例

 

  2.奇数幂的情况:

    好了,现在可以引出第二种情况,就是奇数幂的情况。我们要求得奇数幂的结果,可以从继续步骤1,即按照偶数幂的求法求出最终结果,再附加一个条件是,什么条件呢?

    就是在原来的结果上乘上一个2,原因我相信在插叙中已经说的很明白了,它少了1次幂,现在是在补上这一次幂,即:

   3.最终递归表达式

    那么到现在,我们可以写出完整的递归表达式了,在偶数幂的递归条件下,附加奇数幂的条件即可,即:

 

第3步

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

long long int fastpower(int n){
    if (n == 0)//递归基
        return 1;
    else if (n % 2 == 0)//偶数幂的情况
        return square(fastpower(n / 2));
    else//奇数幂的情况
        return square(fastpower(n / 2)) * 2;
}
long long int square(long long int t){
    return t * t;
}

 

二、上刑
  everybody,现在我们已经完全理清了思路,接下来要把它整成代码吧!

#include<iostream>
using namespace std;

long long int fastpower(int n);//求解快速幂
long long int square(long long int t);//平方

int main(void){

    int n;
    cin >> n;//输入幂
    cout << fastpower(n);

    //固定模块初始线
    cout << endl;
    system("pause");
    return 0;
    //固定模块终止线
}

long long int fastpower(int n){
    if (n == 0)//递归基
        return 1;
    else if (n % 2 == 0)//偶数幂的情况
        return square(fastpower(n / 2));
    else//奇数幂的情况
        return square(fastpower(n / 2)) * 2;
}
long long int square(long long int t){
    return t * t;
}

希望能帮助到你,祝你学有所成!

热门相关:峡谷正能量   锦庭娇   神算大小姐   锦庭娇   上神来了