2.4第7题 求m,n的最大的公约数
求解思路：用碾转算法
关键点：证明 gcd(m,n) = gcd(n,m%n) (注gcd = greatest common divisor)
一、碾转算法：
设:m≥n
s1:若m%n = 0 , 则 n 为 m,n的最大公约数。
S2：若m%n ≥ 0 , 则 m = n , n = m % n 转到S1。
二 、 证明 gcd(m,n) = gcd(n,m%n)
(
定义：
k | m 表示 m 可以被 k 整除 k ∈n .
∨(x|0) 表示 0 可以被任何数整除 ， ∨(0±x)表示0不可以整除任何数。
引理：
假设 k | a ， k | b ,则 对于任何 x, y ∈ Z 有 k | xa + yb .
证明：
k|a = p ＝＞a = pk , k|b ＝＞b = qk , 因 k|(xp + yq) k ＝＞ k|xa+yb.
)
假设 k = gcd (m,n) ， j = gcd(n,m%n)
(1) k | m ,且 k | n . m = a n + m%n , m% n = m - an . 由引理可知 ， 取 x = 1 , y = -a ， 则 k | m%n 且 k | n ,
＝＞ k 是 n,m%n的公约数 , 所以 j ≥ k .
(2) j | n ,且 j | m%n . m = a n + m% n . 由引理可知 ， 取 x = a, y = 1， 则 j | m 且 j | n ,
＝＞ j 是 m,n 的公约数 , 所以 k ≥ j .
综上述两步得出j = k .
所以gcd(m,n) = gcd(n,m%n).
非递归算法：
int gcd (int m , int n)
{
int r = n ;
while (r != 0)
{
r = m % n ;
m = n;
n = r ;
}
if (r ==0)
{
return m;
}
}
递归算法：
int gcdRecursion (int m , int n)
{
if (m%n == 0)
{
return n ;
}
else
{
gcdRecursion(n,m%n);
}
}
另外附上Ider写的非递归算法
int gcd(int m, int n)
{
while (n)
{
n = m^n;
m = m^n;
n = (m^n)%m;
}
return m;
}
//当m=0,n=0时， gcd(m,n)返回0， 我们可以视其为无穷大 （见评论）