计算机程序设计艺术一欧几里得算法

概念

欧几里德算法又称辗转相除法,用于计算两个整数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) 的公约数是一样的,其最大公约数也必然相等,得证。

书中的算法描述

给定两个正整数m和n，求它们的最大公因子，既能够同时整除m和n的最大正整数。 E1.[求余数]以n除以m并令r为所得余数。(我们将有0<= r < n) E2.[余数为零?]若r=0,算法结束，n即为答案。 E3.[减少]置m<-n, n <- r，并返回步骤E1。

※确保m>=n这在算法中不产生任何实质性的改变，只是稍稍增加了算法的长度，却在大约一半情况下减少了 运行时间。

代码实现

1.递归实现

int gcd(int m, int n) { if (m < n) { int tmp = m; m = n; n = tmp; } if (n == 0) { return m; } else { return gcd(n,m % n); } }

2.非递归实现

int gcd1(int m,int n) { if (m < n) { int tmp = m; m = n; n = tmp; } if (n == 0) return m; while (n > 0) { int tmp = m % n; m = n; n = tmp; } return m; }

重要讲解