最大公约数的常用算法
一．实验目的
1.明确算法的概念和特点。
2.通过对问题的分析，设计合理的算法解决问题；
- 实验内容
运行最大公约数的常用算法，并进行程序的调式与测试，要求程序设计风格良好，并添加异常处理模块（如输入非法等）。
1.辗转相除法
辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理：
当b=0时，gcd(a,b) = a ；
当b！=0时，gcd(a,b) = gcd(b,a mod b)。
根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下：
函数嵌套调用
其算法过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给a；
5、返回第二步；
2.穷举法（利用数学定义）
穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。
对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数
3. 更相减损法
更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
翻译成现代语言如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
4.Stein算法
Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。来研究一下最大公约数的性质，发现有 gcd( k*x,k*y ) = k*gcd( x,y ) 这么一个非常好的性质。试取 k=2，则有 gcd( 2x,2y ) = 2 * gcd( x,y )。很快联想到将两个偶数化小的方法。那么一奇一个偶以及两个奇数的情况如何化小呢？
整理一下，对两个正整数 x>y ：
1.均为偶数 gcd( x,y ) =2gcd( x/2,y/2 )；
2.均为奇数 gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 )；
3.x奇y偶 gcd( x,y ) = gcd( x,y/2 )；
4.x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 )；
三．算法构造
1.辗转相除法
2.穷举法
3. 更相减损法
4.Stein算法
四．算法实现
#include <iostream>
#include <Windows.h>
#include <time.h>
#define MAX 100000
/*辗转相除法的函数嵌套调用*/
int divisor1(int a,int b)
{
int temp;
if(a<b)
{
temp=a;a=b;b=temp;
}
while(b!=0)
{
temp=a%b;
a=b;
b=temp;
}
return (a);
}
/*穷举法*/
int divisor2(int a,int b)
{
int temp;
temp=(a>b)?b:a;
while(temp>0)
{
if(a%temp==0&&b%temp==0)
break;
temp--;
}
return (temp);
}
/*更相减损法*/
int gcd2(int m,int n)
{
int i=0,temp,x;
while(m%2==0 && n%2==0) //判断m和n能被多少个2整除
{
m/=2;
n/=2;
i+=1;
}
if(m<n) //m保存大的值
{
temp=m;
m=n;
n=temp;
}
while(x)
{
x=m-n;
m=(n>x)?n:x;
n=(n<x)?n:x;
if(n==(m-n))
break;
}
if(i==0)
return n;
else
return (int )i*i*n;
}
/*stein算法的函数递归调用*/
int gcd(int u,int v)
{
if (u == 0) return v;
if (v == 0) return u;
// look for factors of 2
if (~u & 1) // u is even
{
if (v & 1) // v is odd
return gcd(u >> 1, v);
else // both u and v are even
return gcd(u >> 1, v >> 1) << 1;
}
if (~v & 1) // u is odd, v is even
return gcd(u, v >> 1);
// reduce larger argument
if (u > v)
return gcd((u - v) >> 1, v);
return gcd((v - u) >> 1, u);
}
int main(void)
{
int m,n,t1;
printf("Please input two integer number:");
scanf("%d%d",&m,&n);
t1=divisor1(m,n);
printf("辗转相除法的函数嵌套调用结果：\n");
printf("The higest common divisor is %d\n",t1);
t1=divisor2(m,n);
printf("穷举法的结果：\n");
printf("The higest common divisor is %d\n",t1);
t1=gcd2(m,n);
printf("更相减损法的结果：\n");
printf("The highest common divisor is %d\n",t1);
t1=gcd(m,n);
printf("stein算法的递归调用的结果：\n");
printf("The highest common divisor is %d\n",t1);
}
五．程序测试
1.测试
通过测试，比较了4种GCD算法在给定不同规模测试数据的情况下的平均运行时间。最开始，我是用的是计时函数clock()。
但是经过测试后发现，clock()的精度只能到毫秒，而且是长整型，在规模较小时无法准确测试。
因此，在进一步研究后，选用了可以精确到微秒的计时方法。
通过这种方法，由于是浮点型的缘故，可以更精确的进行计时。
2．测试结果及分析
在测试了分别为100、1000、10000、100000的四组规模之后，我们可以发现辗转相除法的函数嵌套调用用时一直最少，效率最高。
六．经验归纳
本次上机实验由于未作提前准备，上机时间花费了大量时间用于编写代码，在之后的实验中应当做好实验准备。在进行本次实验的过程中，我也进一步了解了这四种求最大公约数的算法以及多种计时工具，如clock()函数等。