开启辅助访问 切换到宽版

精易论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

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

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


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

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

查看: 2041|回复: 11
收起左侧

[易语言纯源码] 求最大公约数-多种算法-高效

[复制链接]
结帖率:90% (161/179)
发表于 2022-10-3 10:04:42 | 显示全部楼层 |阅读模式   广东省佛山市
分享源码
界面截图:
是否带模块: 纯源码
备注说明: -
本帖最后由 Chumeng2333 于 2022-10-3 10:07 编辑
最大公约数,也称最大公因数、最大公因子是指两个或多个整数共有约数中最大的一个。
我将用多种方法计算出两个数的最大公约数
思路/代码/源码回复可见



最简单的是枚举法:
对两个整数a和b,共同的约数在1到min(a,b)[也就是求a和b哪个小]之间,从大到小枚举,若判断它能同时整除a和b两个数,即为两个数的最大公约数
代码:
这个_MIN的函数要保留!!,因为方法2也用到该函数!!
  
子程序名返回值类型公开备 注
_MIN整数型 
参数名类 型参考可空数组备 注
a整数型
b整数型
如果真 (a < b)
返回 (a)
返回 (b)

  
子程序名返回值类型公开备 注
gcd1整数型 枚举
参数名类 型参考可空数组备 注
a整数型
b整数型
变量名类 型静态数组备 注
i整数型 
变量循环首 (_MIN (a, b), 0, -1, i)
如果真 (a % i = 0 b % i = 0)
返回 (i)

变量循环尾 ()
返回 (1)

解释:a%i表示a除i的余数,a%i=0就是a能被i整除,即a是i的倍数或i是a的倍数。
这个算法的最坏时间复杂度为O(min(a,b))




从数学上讲使用方法1的分解质因数的方法,可以令我们从另一方面加深对公约数的理解。例如:a=24,b=60时,对a和b分解质因数得到:
a=2*2*2*3
b=2*2*3*5
收集共有的质因数是2、2、3,得到的最大公约数为:2*2*3=12
代码:
  
子程序名返回值类型公开备 注
gcd2整数型 短除法变形
参数名类 型参考可空数组备 注
a整数型
b整数型
变量名类 型静态数组备 注
gcd整数型 
i整数型 
gcd = 1
i = 2
判断循环首 (i × i ≤ _MIN (a, b))
判断循环首 (a % i = 0 b % i = 0)  ' 收集公共质因数
a = a ÷ i
b = b ÷ i
gcd = gcd × i
判断循环尾 ()
判断循环首 (a % i = 0)  ' a去掉a有b没有的质因数
a = a ÷ i
判断循环尾 ()
判断循环首 (b % i = 0)  ' b去掉a有b没有的质因数
b = b ÷ i
判断循环尾 ()
i = i + 1
判断循环尾 ()
如果 (a % b = 0)  ' 剩余的a和b必须有一个是质数或1
gcd = gcd × b
如果 (b % a = 0)
gcd = gcd × a




返回 (gcd)

解释:由于有i*i<=min(a,b)的优化,时间复杂度降为O(sqrt(min(a,b)))。循环完后,a和b有一个可能没分解完,要注意收集到gcd中,这个算法也可以看成是短除法的变形




我们在方法1采用了低效的算法——枚举法。下面让我们尝试用数学知识找到一种更好的算法!
假设c是a和b的最大公约数(假设a>b),那么有a%c=0,且,b%c=0,则(a-b)%c=0亦成立,即若c是b和a-b的公约数,c亦是a和b的公约数。两个公约数集合相等,两个集合中的
最大数也必然相等,简单讲就是:gcd(a,b)=gcd(b,a-b)。
因此我们可以采用函数进迭送,当迭到a=b时,a为a和b的最大公约数,即答案
用《九章算术》中的“更相减损法”求正整数a和b的最大公约数,即答案
代码:
  
子程序名返回值类型公开备 注
gcd3整数型 更相减损法
参数名类 型参考可空数组备 注
a整数型
b整数型
如果真 (a = b)
返回 (a)
如果真 (a < b)  ' 保证a>=b
交换变量 (a, b)
返回 (gcd3 (b, a - b))


这个算法很简洁!但可惜的是效率依然可能较低,比如说a很大,b很小时。那么我们是否可以再加以优化呢?
可以用方法3类似的方法证明:gcd(a,b)=gcd(b,a%b)(a>b)。
这样的话,我们就可以设计出一个更为高效的算法——欧几里德算法。
代码:
  
子程序名返回值类型公开备 注
gcd4整数型 欧几里德算法
参数名类 型参考可空数组备 注
a整数型
b整数型
如果真 (b = 0)
返回 (a)
返回 (gcd4 (b, a % b))

欧几里德算法的时间复杂度是多少呢?a>b时
(1)若b<=a/2,gcd(a,b)变为gcd(b,a%b),显然规模至少缩小一半。
(2)若b>a/2,a%b也最少缩小为a的一半。
总之进过一次迭代,gcd(a,b)的数据规模至少会变成原来的一半,所以这个算法的时间复杂度是O(lonN)。
全部代码:
  
窗口程序集名保 留  保 留备 注
程序集1   
子程序名返回值类型公开备 注
_启动子程序整数型 本子程序在程序启动后最先执行
调试输出 (gcd1 (145396, 65200))
调试输出 (gcd2 (145396, 65200))
调试输出 (gcd3 (145396, 65200))
调试输出 (gcd4 (145396, 65200))
返回 (0)  ' 可以根据您的需要返回任意数值
子程序名返回值类型公开备 注
gcd1整数型 枚举
参数名类 型参考可空数组备 注
a整数型
b整数型
变量名类 型静态数组备 注
i整数型 
变量循环首 (_MIN (a, b), 0, -1, i)
如果真 (a % i = 0 b % i = 0)
返回 (i)

变量循环尾 ()
返回 (1)
子程序名返回值类型公开备 注
gcd2整数型 短除法变形
参数名类 型参考可空数组备 注
a整数型
b整数型
变量名类 型静态数组备 注
gcd整数型 
i整数型 
gcd = 1
i = 2
判断循环首 (i × i ≤ _MIN (a, b))
判断循环首 (a % i = 0 b % i = 0)  ' 收集公共质因数
a = a ÷ i
b = b ÷ i
gcd = gcd × i
判断循环尾 ()
判断循环首 (a % i = 0)  ' a去掉a有b没有的质因数
a = a ÷ i
判断循环尾 ()
判断循环首 (b % i = 0)  ' b去掉a有b没有的质因数
b = b ÷ i
判断循环尾 ()
i = i + 1
判断循环尾 ()
如果 (a % b = 0)  ' 剩余的a和b必须有一个是质数或1
gcd = gcd × b
如果 (b % a = 0)
gcd = gcd × a




返回 (gcd)
子程序名返回值类型公开备 注
gcd3整数型 更相减损法
参数名类 型参考可空数组备 注
a整数型
b整数型
如果真 (a = b)
返回 (a)
如果真 (a < b)  ' 保证a>=b
交换变量 (a, b)
返回 (gcd3 (b, a - b))
子程序名返回值类型公开备 注
gcd4整数型 欧几里德算法
参数名类 型参考可空数组备 注
a整数型
b整数型
如果真 (b = 0)
返回 (a)
返回 (gcd4 (b, a % b))
子程序名返回值类型公开备 注
_MIN整数型 
参数名类 型参考可空数组备 注
a整数型
b整数型
如果真 (a < b)
返回 (a)
返回 (b)


i支持库列表   支持库注释   
spec特殊功能支持库

全部代码下载:
求最大公约数.e (5.44 KB, 下载次数: 15)

评分

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

查看全部评分


结帖率:91% (69/76)

签到天数: 10 天

发表于 4 天前 | 显示全部楼层   湖南省岳阳市
对你的界面很感兴趣,能不能发帖给我们下载啊
回复 支持 反对

使用道具 举报

签到天数: 5 天

发表于 2023-4-5 15:05:36 | 显示全部楼层   广东省茂名市
支持开源~!感谢分享
回复 支持 反对

使用道具 举报

结帖率:76% (26/34)
发表于 2023-3-27 23:27:06 | 显示全部楼层   宁夏回族自治区吴忠市
源码回复可见
回复 支持 反对

使用道具 举报

签到天数: 7 天

发表于 2022-10-13 17:49:28 | 显示全部楼层   浙江省绍兴市
学习学习,
回复 支持 反对

使用道具 举报

结帖率:100% (3/3)

签到天数: 2 天

发表于 2022-10-9 09:44:25 | 显示全部楼层   湖北省宜昌市
支持开源~!感谢分享
回复 支持 反对

使用道具 举报

发表于 2022-10-6 11:49:39 | 显示全部楼层   浙江省宁波市

支持开源~!感谢分享
回复 支持 反对

使用道具 举报

发表于 2022-10-6 06:37:07 | 显示全部楼层   安徽省合肥市
谢谢分享!!
回复 支持 反对

使用道具 举报

结帖率:87% (20/23)

签到天数: 7 天

发表于 2022-10-3 23:45:11 | 显示全部楼层   广东省东莞市
感谢分享  
回复 支持 反对

使用道具 举报

发表于 2022-10-3 15:07:24 | 显示全部楼层   广东省惠州市
谢谢分享~
回复 支持 反对

使用道具 举报

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

本版积分规则 致发广告者

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

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

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