最新消息:点击查看大S的省钱秘笈

碾转相除法求最大公约数不用比较两数大小

编程相关 Slyar 137浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

辗转相除,又名欧几里德算法(Euclidean algorithm),是求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》中,而在中国则可以追溯至东汉出现的《九章算术》。

以前学碾转相除的时候也没怎么考虑,看到书上说要先比较两个数的大小再碾转相除我就习惯性地先比较大小了,可是今天发现碾转相除法是不用比较两个数的大小的。。。

设我们有两个数m、n

1、用m除以n,得余数r

2、使m=n ,n=r

3、若r=0,则m就是最大公约数;若r不等于0,返回第1步

我们可以看到,如果m>n,那么没说的;如果m<n,在第一次m除以n后,余数恰好为m,这样一交换,最后还会变成m>n的情况。

C语言实现代码为:

#include <stdio.h>

int main()
{
int m, n, r = 1;
scanf("%d%d", &m, &n);
while (r != 0)
{
r = m % n;
m = n;
n = r;
}
printf("%d", m);
return 0;
}

还有一个利用条件运算符写的求最大公约数程序代码

#include<stdio.h>

int main()
{
int m, n;
scanf("%d%d", &m, &n);
while(m > n ? (m = m % n) : (n = n % m));
printf("%d", m + n);
return 0;
}

转载请注明:Slyar Home » 碾转相除法求最大公约数不用比较两数大小

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (4)

  1. 哪有那么复杂,就只有1行好吧。 int gcd(int a, int b){ return a%b ? gcd(b, a%b), b; }
    felix0218年前 (2008-10-31)回复
    • 不要用递归。。。
      Slyar8年前 (2008-10-31)回复
  2. 下午睡了N节课的人...
    Jet8年前 (2008-10-30)回复
  3. 沙发
    自然堂8年前 (2008-10-30)回复