关于求解最大公约数的一个问题！！！

鹰派程序员发布于 2012-03-22 19:48， 551 次点击

这是我在书上考到的代码，求解最大公约数，用的是递归函数，有些不太理解
int rgcd(int v1,int v2)
{
    if(v2!=0)
          return rgcd(v2,v1%v2);
    return v1;
}

6 回复

nicum2012-03-22 19:59

最大公约数算法
数 a,b 设最大公约数为k
则 a=c*k b=d*k 设b>a,则 b=a*m+n
有 d*k=c*m*k+n => d=c*m+(n/k) => n%k=0
n=b%a
则 n,a 的最大公约数和 a,b 的最大公约数一样

鹰派程序员2012-03-22 20:08

回复 2楼 nicum

我理解了你说的这个算法了，可关于代码：你说的a相当于v1和v2中的一个，那如何用v1和v2体现出你说的n呢，比如：123和15把，最大公约数是3，你能用这个例子来给我讲讲这个过程吗，谢谢你了

pangding2012-03-22 21:25

回复 3楼鹰派程序员

123 ＝ 15＊8 ＋ 3
15 ＝ 3＊5 ＋ 0
所以最大公约数是 3。

就是那个定理说的，(123, 15) = (15, 3) = 3

pangding2012-03-22 21:31

辗转相除定理是说：两个数的最大公约数等于它们相除的余数与较小数的最大公约数。
123 除以 15 余 3，所以 123 和 15 的最大公约数与 15 和 3 的最大公约数相同。15 能被 3 整除，所以 3 就是它们的最大公约数。

2 楼还给了定理的证明，可以说是非常认真。

nicum2012-03-22 21:35

回复 3楼鹰派程序员

不是写了吗 n=b%a;等价于 n=v1%v2;

朔风乱雪2012-03-22 23:04

学习到了，二楼写的好清楚