开启辅助访问 切换到宽版

精易论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

用微信号发送消息登录论坛

新人指南 邀请好友注册 - 我关注人的新帖 教你赚取精币 - 每日签到


求职/招聘- 论坛接单- 开发者大厅

论坛版规 总版规 - 建议/投诉 - 应聘版主 - 精华帖总集 积分说明 - 禁言标准 - 有奖举报

查看: 4084|回复: 22
收起左侧

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

[复制链接]

结帖率:100% (42/42)
发表于 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, 下载次数: 131)

点评

快速幂主要用于ACM编程比赛中,可能各位易友接触较少   广东省广州市  发表于 2017-12-10 12:36

评分

参与人数 1好评 +1 精币 +5 收起 理由
凌哥 + 1 + 5 支持开源~!感谢分享

查看全部评分


本帖被以下淘专辑推荐:

签到天数: 12 天

发表于 2024-3-13 06:11:43 | 显示全部楼层   江苏省连云港市
感谢分享。。。。。。。。。。。
回复 支持 反对

使用道具 举报

结帖率:17% (1/6)

签到天数: 9 天

发表于 2024-3-5 09:44:32 高大上手机用户 | 显示全部楼层   浙江省台州市
好东西,感谢分享
回复 支持 反对

使用道具 举报

结帖率:100% (5/5)

签到天数: 24 天

发表于 2024-1-17 17:12:41 | 显示全部楼层   广东省佛山市
感谢分享
回复 支持 反对

使用道具 举报

结帖率:100% (1/1)
发表于 2023-4-7 16:25:17 | 显示全部楼层   福建省漳州市
感谢分享 一天一个小技巧
回复 支持 反对

使用道具 举报

发表于 2019-10-8 04:02:05 | 显示全部楼层   江苏省淮安市
感谢分享 学习了
回复 支持 反对

使用道具 举报

发表于 2019-10-8 00:50:49 | 显示全部楼层   江苏省淮安市
学习了 感谢大神
回复 支持 反对

使用道具 举报

发表于 2018-8-18 21:57:50 | 显示全部楼层   福建省泉州市
收藏了!
回复 支持 反对

使用道具 举报

发表于 2018-1-11 02:27:23 | 显示全部楼层   福建省漳州市
好作品就要顶
回复 支持 反对

使用道具 举报

发表于 2018-1-11 02:06:35 | 显示全部楼层   福建省漳州市
好作品就要顶
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则 致发广告者

发布主题 收藏帖子 返回列表

sitemap| 易语言源码| 易语言教程| 易语言论坛| 诚聘英才| 易语言模块| 手机版| 广告投放| 精易论坛
拒绝任何人以任何形式在本论坛发表与中华人民共和国法律相抵触的言论,本站内容均为会员发表,并不代表精易立场!
论坛帖子内容仅用于技术交流学习和研究的目的,严禁用于非法目的,否则造成一切后果自负!如帖子内容侵害到你的权益,请联系我们!
防范网络诈骗,远离网络犯罪 违法和不良信息举报电话0663-3422125,QQ: 800073686,邮箱:800073686@b.qq.com
Powered by Discuz! X3.4 揭阳市揭东区精易科技有限公司 ( 粤ICP备12094385号-1) 粤公网安备 44522102000125 增值电信业务经营许可证 粤B2-20192173

快速回复 返回顶部 返回列表