简单C语言问题

Question

程序：8.1
对于求最大公约数用辗转相除法的疑问：
书上是这样写了一个最大公约数的函数：
int hcf(int u , int v)
{
int t , r;
if (v > u)

{
t = u; u = v ; v = t;

}

while ((r = u%v) != 0)

{
u = v;

v = r ;

}

return(v);

}
为什么这样能求出最大公约数？？？

Answer 1

先说明整除性的一些特点
（下文的所有数都是正整数，
不再重覆）
，
我们可以这样给出整除性的定义：

对于二个自然数a和b，若存在正整数q，使a=bq，则a能被b整除，b为a的因子，a为b的倍数。

如果a能被c整除，并且b也能被c整除，则c为a、b的公因数（公有因数）。

由此我们可以得出以下推论：
推论1、如果a能被b整除（a=qb），若k为正整数，则ka也能被b整除（ka=kqb）
推论2、如果a能被c整除（a=hc），b也能被c整除（b=tc），则(a±b)也能被c整除
因为：将二式相加：a+b=hc+tc=(h+t)c 同理二式相减：a－b=hc－tc=(h－t)c
所以：(a±b)也被c整除
推论3、如果a能被b整除（a=qb），b也能被a整除（b=ta），则a=b
因为：a=qbb=taa=qtaqt=1 因为q、t均为正整数，所以t=q=1
所以：a=b

辗转相除法是用来计算两个数的最大公因数，
在数值很大时尤其有用，
而且应用在电脑
程式上也十分简单。其理论如下:
如果q 和r 是m 除以n 的商及余数，即m=nq+r，则gcd(m,n)=gcd(n,r)。

证明是这样的:
设a=gcd(m,n)，b=gcd(n,r) a=gcd(m,n)
m能被a整除，并且n也能被a整除，则由推论1得：qn也能被a整除
由推论2得：m-qn也能被a整除,而m-qn=r，即r也能被a整除，所以a=b 。

或

b=gcd(n,r) n能被b整除，并且r也能被b整除，则由推论1得：qn也能被b整除
由推论2得：qn+r也能被b整除而m=qn+r，即m也能被b整除，所以a=b。

Answer 2

简单的来说，如果2个数n和m，他们的最大公约数为k的话，那么n%m的结果也必定是k的整数倍，这样一直下去就可以得到结果了，你这个看程序是看不出来的。你需要拿2个数来亲自实现。我当时学习这个方法的时候也是很模糊，后来实现后就清楚了。

比如25和15
之后变为15，5
再变为5，0
这个时候就能得到5是他们的最大公约数了本回答被提问者采纳

Answer 3

这是一个子函数，两个数分别是u，v第一个if是为了将uv按照大小排列。那个while，直到u能把v整除为止。最后返回值v就是公约数。