UC知道想不通的c语言问题
来源：百度知道 编辑：UC知道 时间：2024/06/15 04:48:21
以下是一个求两个整数的最大公约数的一个模块：
int hcf(int u,int v) /*定义函数hcf，求两个整数u,v的最大公约数*/
{
int t,r; /*定义两个变量t,r*/
if(v>u) /*判断如果v>u，将两者互换，使终使u>v*/
{t=u;u=v;v=t;}
while((r=u%v)!=0) /*循环求余，如果余数不等于，则u=v,v=r*/
{u=v;v=r;}
return v; /*返回当前最大公约数*/
}
看了很久。。。。看不懂啊！！请高手帮小弟解释这个部分的执行过程。小弟还有50分。解释的好的全给你！！！我太郁闷了。。。。
int hcf(int u,int v) /*定义函数hcf，求两个整数u,v的最大公约数*/
{
int t,r; /*定义两个变量t,r*/
if(v>u) /*判断如果v>u，将两者互换，使终使u>v*/
{t=u;u=v;v=t;}
while((r=u%v)!=0) /*循环求余，如果余数不等于，则u=v,v=r*/
{u=v;v=r;}
return v; /*返回当前最大公约数*/
}
看了很久。。。。看不懂啊！！请高手帮小弟解释这个部分的执行过程。小弟还有50分。解释的好的全给你！！！我太郁闷了。。。。
这个嘛，我觉得你带进去两个具体的数字，就一目了然了呀，比如说：10与15~~while语句是一个除余判断，所以就要求u必须大于v,也就有了先前if语句的判断互换，当u除余v为0时，显然v一定是他们的最大公约数了，再大v就无法除了~如若除余不为0,这时候就带入具体数字理解下吧 15%10=5！=0，进入循环，将10代替了15的位置 5代替了10的位置，10%5=0，跳出循环，判断出5为最大公约数，问题得以验证~
Euclid
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。
----------------
注释：d | b 表示d能被b整除， mod表示取余数的运算
最大公约数就是辗转相除法
如果两个数 a，b a>b
a和b的最大公约数算法为
如果a%b==0 b就是最大公约数 否则 a=b b=a%b (两个同时算的,需要中间变量）
直道a%b==0
这里一个算法，辗转相除法
参考下面的链接
http://zhidao.baidu.com/question/25974010.html
主要还是辗转相除法：要求A与B的最大公