免费注册	查看新帖 \|


平台论坛博客文库

› 论坛 › 程序设计 › C/C++ › 辗转相除法求最大公约数感性理解

最近访问板块

发新帖

查看: 2084 | 回复: 4

上一主题

下一主题

[算法] 辗转相除法求最大公约数感性理解 [复制链接]

论坛徽章:: 13

15-16赛季CBA联赛之八一
日期:2016-07-08 21:00:14

15-16赛季CBA联赛之同曦
日期:2017-02-15 14:26:15

15-16赛季CBA联赛之佛山
日期:2017-02-20 14:19:26

15-16赛季CBA联赛之青岛
日期:2017-05-07 16:49:11

15-16赛季CBA联赛之广夏
日期:2017-07-30 09:13:12

15-16赛季CBA联赛之广东
日期:2018-07-05 22:34:36

15-16赛季CBA联赛之江苏
日期:2018-09-03 12:10:21

15-16赛季CBA联赛之上海
日期:2018-09-25 03:49:22

15-16赛季CBA联赛之广东
日期:2018-09-25 04:09:12

电梯直达

跳转到指定楼层

1楼 [收藏(0)] [报告]

发表于 2016-01-29 23:45 |只看该作者 |倒序浏览

红线表示较大数的值，蓝线表示较小数的值，它们不能整除，就是因为灰线后多了一截余数。
现在假设黄线表示找到的公约数，那么依次从红线中减去黄线的大小，最终肯定到达灰线位置，此时，黄线必须满足2个条件：
① 可以整除蓝线；
② 可以整除红线的多余长度（灰线后面部分）。
如果此时多余长度可以整除蓝色长度，则多余长度为最大公约数，否则问题转换为求蓝线和多余长度的最大公约数，同样的道理依次往后求，直到找到最大公约数，“最差情况”是找到1的时候才退出。

所以辗转相除法的过程就是：
① 较大数/较小数，如果余数=0，则较小数为最大公约数，否则进行第②步；
② 用较小数作为新的较大数，余数作为新的较小数，然后执行第①步。

文库|博客

论坛徽章:: 14

水瓶座
日期:2014-06-10 09:51:02

15-16赛季CBA联赛之江苏
日期:2017-11-27 11:42:35

15-16赛季CBA联赛之八一
日期:2017-04-12 14:26:28

15-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:12

15-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58

程序设计版块每日发帖之星
日期:2016-02-11 06:20:00

程序设计版块每日发帖之星
日期:2016-02-09 06:20:00

15-16赛季CBA联赛之上海
日期:2015-12-25 16:40:35

15-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36

程序设计版块每日发帖之星
日期:2015-08-24 06:20:00

2015亚冠之德黑兰石油
日期:2015-08-07 09:57:30

2015年辞旧岁徽章
日期:2015-03-03 16:54:15

2楼 [报告]

发表于 2016-02-01 09:43 |只看该作者

欧几里德表示看不懂

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

论坛徽章:: 2

2015年辞旧岁徽章
日期:2015-03-03 16:54:15

2015元宵节徽章
日期:2015-03-06 15:52:30

3楼 [报告]

发表于 2016-02-01 18:18 |只看该作者

我理解楼主的意思

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

论坛徽章:: 11

2015年迎新春徽章
日期:2015-03-04 09:55:28

2017金鸡报晓
日期:2017-02-08 10:39:42

15-16赛季CBA联赛之辽宁
日期:2016-12-15 10:24:17

15-16赛季CBA联赛之佛山
日期:2016-11-30 09:04:20

15-16赛季CBA联赛之江苏
日期:2016-04-29 15:56:12

15-16赛季CBA联赛之同曦
日期:2016-04-12 13:21:18

2016猴年福章徽章
日期:2016-02-18 15:30:34

15-16赛季CBA联赛之山东
日期:2016-02-16 11:37:52

每日论坛发贴之星
日期:2016-02-07 06:20:00

程序设计版块每日发帖之星
日期:2016-02-07 06:20:00

15-16赛季CBA联赛之新疆
日期:2018-01-09 16:25:37

4楼 [报告]

发表于 2016-02-04 10:12 |只看该作者

支持,这个就是以前windows在商业上远胜unix的主要原因

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

论坛徽章:: 223

2022北京冬奥会纪念版徽章
日期:2015-08-10 16:30:32

操作系统版块每日发帖之星
日期:2016-05-10 19:22:58

操作系统版块每日发帖之星
日期:2016-02-18 06:20:00

操作系统版块每日发帖之星
日期:2016-03-01 06:20:00

操作系统版块每日发帖之星
日期:2016-03-02 06:20:00

15-16赛季CBA联赛之上海
日期:2019-09-20 12:29:32

19周年集字徽章-周
日期:2019-10-01 20:47:48

15-16赛季CBA联赛之八一
日期:2020-10-23 18:30:53

20周年集字徽章-20
日期:2020-10-28 14:14:26

15-16赛季CBA联赛之广夏
日期:2023-02-25 16:26:26

CU十四周年纪念徽章
日期:2023-04-13 12:23:10

操作系统版块每日发帖之星
日期:2016-05-10 19:22:58

5楼 [报告]

发表于 2016-02-15 18:31 来自手机 |只看该作者

楼上的观点深奥了，求解释

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

发新帖

Chinaunix › 论坛 › 程序设计 › C/C++ › 辗转相除法求最大公约数感性理解

北京盛拓优讯信息技术有限公司. 版权所有京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP