本站资源收集于互联网,不提供软件存储服务,每天免费更新优质的软件以及学习资源!

2的5次方怎么计算(快速幂运算步骤)

电脑教程 jingyan 1℃

2的5次方怎么计算快速幂运算步骤

在m和n都属于正数,并且m的n次方不超过LONG_MAX的情况下,如何求出m的n次方呢?一般都会想到用一个循环,如下

long result = 1;

for (int i = 0; i < n; i++)

result * = m;

result即为所求,算法复杂度O(n)。这样也能工作,但是当m和n变大时,效率会相当低下,如何优化呢?考虑2的4次方的情况,其实就是4个2相乘法;有没有看出撒问题呢?是的,重复计算!前二个2相乘的结果可以直接用,后面两个2的相乘不用再计算,即是

2X2X2X2 = 4X4

考虑2的5次方,即5个2相乘的情况,同样的道理

2X2X2X2X2 = 4X4X2

所呈现出来的规律即是

m的n次方,在n为偶数时,可以变成 m的n/2次方的平方;在n为奇数时,则有n – 1为偶数,则变成m的(n-1)/2次方的平方再乘以m, 从n变成n/2,问题规模变小,中间计算结果可重复利用,可用递归解决,其算法复杂度变成O(logn)。具体代码见下:

运行结果如下

转载请注明:范的资源库 » 2的5次方怎么计算(快速幂运算步骤)

喜欢 (0)