求最大公约数的原理及算法实现.doc

1.辗转相除法GCD算法的基本原理 DCD - Greatest Common Divisor欧几里得定理： 若 a = b * r + q，则 GCD(a,b) = GCD(b,q)。证明： 假设 c = GCD(a,b) 则存在m使得a = m * c,b = n * c; 因为 a = b * r + q, 则 q = a - b * r = m * c - n * c * r = (m - n * r) * c; 因为 b = n * c , q = (m - n * r) * c 故要证明GCD(a,b) = GCD(b,q)，即证明 n 与 m - n * r互质 下面证明 m-nr与n互质： 假设不互质，则存在公约数k使得 m - n * r = x * k, n = y * k. 则: a= m * c = (n * r + x * k) * c = (y * k * r + x * k) * c = (y * r + x) * k * c b = n * c = y * c * k 则GCD(a,b) = k * c,与 c=gcd(a, b) 矛盾2.辗转相除法算法的实现2.1递归实现int GCD(int a, int b) if(!b)return a;elsereturn GCD(b, a % b);自己改进int GCD(int a, int b)if(!(a % b)return b;elsereturn GCD(b, a % b);2.2迭代实现int GCD(int a, int b) int c = a%b; while(c)a = b; b = c; c = a % b; return b;3.更相减损法更相减损术，是出自九章算术的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。 九章算术是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”翻译成现代语言如下：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减去小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。例如：用更相减损术求260和104的最大公约数。解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。此时65是奇数而26不是奇数，故把65和26辗转相减：65-26=3939-26=1326-13=13所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52。2.更相减损法算法的实现2.1递归实现#includeint main(void) int num = 0,result,a,b; scanf(%d %d,&a,&b); while( !(a % 2) & !(b %2) num+; a /= 2; b /= 2; result = pow(2,num) * GCD(a,b); printf(GCD:%dn,result); return 0;int GCD(int a,int b) if(a b) if( (a - b) = b) return b; else return GCD(b,a - b); else if(b - a) = a) return a; else return GCD(a,b - a); 2.2迭代实现#includeint main(void) int num = 0,result,a,b; scanf(%d %d,&a,&b); while( !(a % 2) & !(b %2) num+; a /= 2; b /= 2; result = pow(2,num) * GCD(a,b); printf(GCD:%dn,result); return 0;int GCD(int a,int b) if(a b) a = a - b; else a = b; b = a - b; return b;3. 辗转相除法与更相减损术的区别（1）都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。4-54.常用结论在解有关最大公约数、最小公倍数的问题时，常用到以下结论：（1）如果两个数是互质数，那么它们的最大公约数是1，最小公倍数是这两个数的乘积。例如8和9，它们是互质数，所以（8，9）=1，8，9=72。（2）如果两个数中，较大数是较小数的倍数，那么较小数就是这两个数的最大公约数，较大数就是这两个数的最小公倍数。例如18与3，183=6，所以（18，3）=3，18，3=18。（3）两个数分别除以它们的最大公约数，所得的商是互质数。例如8和14分别除以它们的最大公约数2，所得的商分别为4和7，那么4和7是互质数。（4）两个数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。5.扩展（求多个数的最大公约数）原理：GCD(a,b,c) = GCD(GCD(a,b),c)源码：# include # include int QuickSort(int length,int* array);int GCD(int length,int* array);int main()/freopen(C:Usersfroje.liuDesktopdata.txt,r,stdin);int i,length,* array;printf(Input array length:);scanf(%d,&length);array = (int *)malloc(length * sizeof(int);for(i = 0; i length; i+)scanf(%d,&arrayi);QuickSort(length,array);printf(Array length:%dn,length); printf(Array:n);for(i = 0; i length; i+)printf(%d ,arrayi);printf(n);printf(GCD:%dn,GCD(length,array);return 0;int QuickSort(int length,int* array)int i,j,temp,min;for(i = 0; i length; i+)min = i;for(j = i + 1; j length; j+)if(arrayj arraymin)min = j;temp = arraymin;arraymin = arrayi;arrayi = temp;return 0;int GCD(int length,int* array)int GCD,i