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

2008年10月30日 19:24 . 分类 编程相关 . 被踩 516 次 .

文章作者：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;
}

您可能还对以下内容感兴趣

Tags: ,

收藏、分享这篇文章! 用 RSS feed 订阅本博客 什么是订阅？ Trackback

评论

4 条评论 关于 “碾转相除法求最大公约数不用比较两数大小”

  1. 由 自然堂 发表于 2008年10月30日 21:46

    沙发

  2. 由 Jet 发表于 2008年10月30日 22:49

    下午睡了N节课的人...

  3. 由 felix021 发表于 2008年10月31日 17:30

    哪有那么复杂，就只有1行好吧。
    int gcd(int a, int b){ return a%b ? gcd(b, a%b), b; }

    Slyar 回复 于 10月 31st, 2008 18:16:

    不要用递归。。。

发表您的评论[审核后显示]




关闭
E-mail It