如何求两数的最大公约数 - C语言论坛 - 编程论坛

| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 |

编程论坛 → 开发语言 → 『 C语言论坛』 → 如何求两数的最大公约数

我的收件箱(0)

欢迎加入我们，一同切磋技术

共有 8361 人关注过本帖

标题：如何求两数的最大公约数

只看楼主加入收藏

风居住的街道

性别保密呀，离线，找我有事吗？

Rank: 1

等　级：新手上路
帖　子：374
专家分：0
注　册：2008-10-24

收藏

得分:0

谁告诉你m(k) = m(k - 1) + 1的？！
那个是求余！对于求余，就我所知，也就是gcd(a, b)时，a % b 不会大于等于b而已……

刚才发的维基百科，有这样一句话“辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位数。”你到底看了没？！

发帖时间

2008-11-11 18:34

风居住的街道

性别保密呀，离线，找我有事吗？

Rank: 1

等　级：新手上路
帖　子：374
专家分：0
注　册：2008-10-24

收藏

得分:0

另：
看看这个：http://tieba.baidu.com/f?ct=335675392&tn=baiduPostBrowser&sc=3239345395&z=319136043&pn=0&rn=50&lm=0&word=%CA%FD%D1%A7

发帖时间

2008-11-11 18:36

liyanhong

美女呀，离线，留言给我吧！

Rank: 3

Rank: 3

来　自：水星
等　级：禁止访问
威　望：8
帖　子：1867
专家分：0
注　册：2008-5-3

收藏

得分:0

看了个数字有什么用谁信他！！

爱上你是我的错可是离开又舍不得听着你为我写的歌好难过
如果说我说如果我们还能重新来过不去计较谁对谁错会怎么做

发帖时间

2008-11-11 18:37

hokers

帅哥哟，离线，有人找我吗？

Rank: 1

等　级：新手上路
威　望：1
帖　子：102
专家分：0
注　册：2008-11-9

收藏

得分:0

反汇编看编译优化代码比比.哈哈

发帖时间

2008-11-11 18:37

风居住的街道

性别保密呀，离线，找我有事吗？

Rank: 1

等　级：新手上路
帖　子：374
专家分：0
注　册：2008-10-24

收藏

得分:0

[bo][un]liyanhong[/un] 在 2008-11-11 18:37 的发言：[/bo]

看了个数字有什么用谁信他！！

我晕！！我让你看的是这句：
对于辗转相除法,由m'=m%n知m=kn+m'粗略估计求模次数即为lnN.正如上所述,关心的是复杂度的数量级,并不用精确的求关系.

发帖时间

2008-11-11 18:39

风居住的街道

性别保密呀，离线，找我有事吗？

Rank: 1

等　级：新手上路
帖　子：374
专家分：0
注　册：2008-10-24

收藏

得分:0

关键是那句由m'=m%n可以得出m=kn+m'
所以可以得到gcd的递归式：
T(n) = T(n/k) + O(1)
根据主方法：
T(n) = O(lgn * 1) = O(lgn)

发帖时间

2008-11-11 18:43

peng_piao

帅哥哟，离线，有人找我吗？

Rank: 1

等　级：新手上路
帖　子：89
专家分：0
注　册：2008-11-5

收藏

得分:0

发帖时间

2008-11-11 22:53

batistutaluke

帅哥哟，离线，有人找我吗？

Rank: 1

来　自：东北大学
等　级：新手上路
帖　子：12
专家分：0
注　册：2008-10-27

收藏

得分:0

只学过辗转求余法，还不错，顶一个。。。。

还可以。。。

发帖时间

2008-11-11 22:55

网易

美女呀，离线，留言给我吧！

Rank: 1

来　自：金星
等　级：禁止访问
帖　子：193
专家分：0
注　册：2008-6-10

收藏

得分:0

[bo][un]peng_piao[/un] 在 2008-11-11 22:53 的发言：[/bo]

你是不是觉得辗转相除很简单？

请教一下您
gcd(m,n)=gcd(n m mod n) 能不能证明一下
gcd(m,0)=m能不能解释一下
Taver(n)=？
⊙（n）=？

答案是：雨中飞燕！

发帖时间

2008-11-11 23:08

iFreeBSD

帅哥哟，离线，有人找我吗？

Rank: 4

等　级：业余侠客
威　望：4
帖　子：474
专家分：236
注　册：2007-11-5

收藏

得分:0

[bo][un]风居住的街道[/un] 在 2008-11-11 18:34 的发言：[/bo]

谁告诉你m(k) = m(k - 1) + 1的？！
那个是求余！对于求余，就我所知，也就是gcd(a, b)时，a % b 不会大于等于b而已……

刚才发的维基百科，有这样一句话“辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位 ...

你分析是对的，欧几里德算法明显是O(lgn)怎么会是0（n2) , 纯属笔误。

without further ado, let’s get started

发帖时间

2008-11-11 23:17

快速回复：如何求两数的最大公约数

关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有，并保留所有权利。

Powered by Discuz, Processed in 0.018747 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved