易语言实现快速幂 ,快速求次方

灰灰君 · 发表于 2017-12-10 11:13:26

本帖最后由灰灰君于 2017-12-10 11:15 编辑

首先，快速幂的目的就是做到快速求幂，假设我们要求a^b,按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)也即是O(n)级别，快速幂能做到O(logn)，快了好多好多。它的原理如下：

　　假设我们要求a^b，那么其实b是可以拆成二进制的，该二进制数第i位的权为2^(i-1)，例如当b==11时

　　　　　　　　　　　　　　　　　　　　　　　　　　 a11=a(2^0+2^1+2^3)

　　11的二进制是1011，11 = 23×1 + 22×0 + 21×1 + 2o×1，因此，我们将a11转化为算 a2^0*a2^1*a2^3，也就是a1*a2*a8 ，看出来快的多了吧原来算11次，现在算三次
C/C++实现代码如下:

int poww(int a,int b){
int ans=1,base=a;
while(b!=0){
      if(b&1!=0)
      　　ans*=base;
      base*=base;
      b>>=1;
　 }
return ans;
}

易语言具体实现代码见附件.

快速幂.zip (1.01 KB, 下载次数: 146)

beatone · 发表于 2024-3-13 06:11:43

感谢分享。。。。。。。。。。。

离开了 · 发表于 2024-3-5 09:44:32

好东西，感谢分享

lm88818 · 发表于 2024-1-17 17:12:41

感谢分享

cxjd1987 · 发表于 2023-4-7 16:25:17

感谢分享一天一个小技巧

雪之孤寂 · 发表于 2019-10-8 04:02:05

感谢分享学习了

雪之孤寂 · 发表于 2019-10-8 00:50:49

学习了感谢大神

2857428593 · 发表于 2018-8-18 21:57:50

收藏了！

falali5566 · 发表于 2018-1-11 02:27:23

好作品就要顶

falali5566 · 发表于 2018-1-11 02:06:35

好作品就要顶

		自动登录	找回密码
密码			注册

[易语言纯源码] 易语言实现快速幂 ,快速求次方

点评

评分

本帖被以下淘专辑推荐: