一、题目分析：求两个数的最大公约数，设计求最大公约数的算法并使这两个数据调用求最大公约数的函数，得到最大公约数的值。
二、算法分析：
1.辗转相除法
辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理：
根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下：
其算法过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给a；
5、返回第二步；
代码：
int divisor (int a,int b) /
自定义函数求两数的最大公约数
/
{
int temp; /
定义整型变量
/
if(a<b) /
通过比较求出两个数中的最大值和最小值
/
{ temp=a;a=b;b=temp;} /
设置中间变量进行两数交换
/
while(b!=0) /
通过循环求两数的余数，直到余数为0
/
{
temp=a%b;
a=b; /
变量数值交换
/
b=temp;
}
return (a); /
返回最大公约数到调用函数处
/
}
流程图如下：
2.穷举法
穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。
对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
代码为：
int divisor (int a,int b) /*自定义函数求两数的最大公约数*/
{
int temp; /*定义义整型变量*/
temp=(a>b)?b:a; /*采种条件运算表达式求出两个数中的最小值*/
while(temp>0)
{
if (a%temp==0&&b%temp==0) /*只要找到一个数能同时被a,b所整除，则中止循环*/
break;
temp--; /*如不满足if条件则变量自减，直到能被a,b所整除*/
}
return (temp); /*返回满足条件的数到主调函数处*/
}
#include "stdio.h"
main()
{
int m,n,t1;
printf("please input two integer number:");
scanf("%d%d",&m,&n);
t1=divisor(m,n);
printf("The higest common divisor is %d\n",t1);
getch();
}
流程图如下：
3.更相减损法
更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
翻译成现代语言如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
int gcd(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 )pow(2,i)*n;
}
流程图如下：
4.Stein算法
Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。来研究一下最大公约数的性质，发现有 gcd( k
x,k
y ) = k
gcd( x,y ) 这么一个非常好的性质。试取 k=2，则有 gcd( 2x,2y ) = 2 * gcd( x,y )。很快联想到将两个偶数化小的方法。那么一奇一个偶以及两个奇数的情况如何化小呢？
先来看看一奇一偶的情况： 设有2x和y两个数，其中y为奇数。因为y的所有约数都是奇数，所以 a = gcd( 2x,y ) 是奇数。根据2x是个偶数不难联想到，a应该是x的约数。我们来证明一下：(2x)%a=0，设2x=n
a，因为a是奇数，2x是偶数，则必有n是偶数。又因为 x=(n/2)*a，所以 x%a=0，即a是x的约数。因为a也是y的约数，所以a是x和y的公约数，有 gcd( 2x,y ) <= gcd( x,y )。因为gcd( x,y )明显是2x和y的公约数，又有gcd( x,y ) <= gcd( 2x,y )，所以 gcd( 2x,y ) = gcd( x,y )。至此，我们得出了一奇一偶时化小的方法。
再来看看两个奇数的情况：设有两个奇数x和y，不妨设x>y，注意到x+y和x-y是两个偶数，则有 gcd( x+y,x-y ) = 2 * gcd( (x+y)/2,(x-y)/2 )，那么 gcd( x,y ) 与 gcd( x+y,x-y ) 以及 gcd( (x+y)/2,(x-y)/2 ) 之间是不是有某种联系呢？为了方便设 m=(x+y)/2 ，n=(x-y)/2 ，容易发现 m+n=x ，m-n=y 。设 a = gcd( m,n )，则 m%a=0,n%a=0 ，所以 (m+n)%a=0，(m-n)%a=0 ，即 x%a=0 ，y%a=0 ，所以a是x和y的公约数，有 gcd( m,n )<= gcd(x,y)。再设 b = gcd( x,y )肯定为奇数，则 x%b=0,y%b=0 ，所以 (x+y)%b=0 ，(x-y)%b=0 ，又因为x+y和x-y都是偶数，跟前面一奇一偶时证明a是x的约数的方法相同，有 ((x+y)/2)%b=0,((x-y)/2)%b=0 ，即 m%b=0 ，n%b=0 ，所以b是m和n的公约数，有 gcd( x,y ) <= gcd( m,n )。所以 gcd( x,y ) = gcd( m,n ) = gcd( (x+y)/2,(x-y)/2 )。
整理一下，对两个正整数 x>y ：
1.均为偶数 gcd( x,y ) =2gcd( x/2,y/2 )；
2.均为奇数 gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 )；
2.x奇y偶 gcd( x,y ) = gcd( x,y/2 )；
3.x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 )；
现在已经有了递归式，还需要再找出一个退化情况。注意到 gcd( x,x ) = x ，就用这个。
int Stein( unsigned int x, unsigned int y )
/* return the greatest common divisor of x and y */
{
int factor = 0;
int temp;
if ( x < y )
{
temp = x;
x = y;
y = temp;
}
if ( 0 == y )
{
return 0;
}
while ( x != y )
{
if ( x & 0x1 )
{/* when x is odd */
if ( y & 0x1 )
{/* when x and y are both odd */
y = ( x - y ) >> 1;
x -= y;
}
else
{/* when x is odd and y is even */
y >>= 1;
}
}
else
{/* when x is even */
if ( y & 0x1 )
{/* when x is even and y is odd */
x >>= 1;
if ( x < y )
{
temp = x;
x = y;
y = temp;
}
}
else
{/* when x and y are both even */
x >>= 1;
y >>= 1;
++factor;
}
}
}
return ( x << factor );
}
流程图如下：
三、算法实现
程序源代码：
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<math.h>
int fun1(int a,int b) //自定义利用辗转相除法计算最大公约数的函数
{
int temp;
if(a<b) //通过比较求出两个数中的最大值和最小值
{ temp=a;
a=b;
b=temp;
} //设置中间变量进行两数交换
while(b!=0) //通过循环求两数的余数，直到余数为0
{
temp=a%b;
a=b; //变量数值交换
b=temp;
}
return a; //返回最大公约数到调用函数处
}
int fun2(int a,int b) //自定义利用穷举法计算最大公约数的函数
{
int temp; //自定义整型变量
temp=(a>b)?b:a; //采用条件运算表达式求出两个数中的最小值
while(temp>0)
{
if(a%temp==0&&b%temp==0) //只要找到一个数能同时被a，b所整除，则中止循环
break;
temp--; //如不满足if条件则变量自减，直到能被a，b所整除
}
return temp; //返回满足条件的数到主调函数处
}
int fun3(int m,int n) //自定义利用更相减损法计算最大公约数的函数
{
int temp,x;
int i=0;
while(m%2==0&&n%2==0) //判断m和n能被多少个2整除
{
m/=2;
n/=2;
i+=1;
}
if(m<n) //m保存大的值
{
temp=n;
n=m;
m=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)pow(2,i)*n; //返回最大公约数到主函数处
}
int fun4(unsigned int x,unsigned int y) //自定义利用Stein算法计算最大公约数的函数
{
int factor=0;
int temp;
if(x<y) //使x保存大的值
{
temp=x;
x=y;
y=temp;
}
if(0==y) //若除数为0，返回0
return 0;
while(x!=y)
{
if(x&0x1)
{
if(y&0x1) //x，y都为奇数
{
y=(x-y)>>1;
x-=y;
}
else
{
y>>=1; //x为奇数，y为偶数
}
}
else
{
if(y&0x1) //x为偶数，y为奇数
{
x>>=1;
if(x<y)
{
temp=x;
x=y;
y=temp;
}
}
else //x，y都为偶数
{
x>>=1;
y>>=1;
++factor;
}
}
}
return (x<<factor); //返回最大公约数到主函数处
}
void main()
{
int x,y,z,temp;
printf("请输入两个数字计算这两个数字的最大公约数:\n"); //提示用户选择操作
scanf("%d%d",&x,&y); //键盘输入两个数字
printf("请选择您的操作（请输入1-4之间的数字）:\n"); //显示主界面
printf("使用函数嵌套调用辗转相除法计算两个数的最大公约数-------------1\n");
printf("使用穷举法计算两个数的最大公约数-----------------------------2\n");
printf("使用更相减损法计算两个数的最大公约数-------------------------3\n");
printf("使用函数递归调用Stein算法计算两个数的最大公约数--------------4\n");
while(1)
{
scanf("%d",&temp);
while(temp>4||temp<1) //判断输入是否规范
{
printf("您的输入有误，请重新输入:");
scanf("%d",&temp);
}
switch(temp) //根据用户选择执行不同的函数操作
{
case 1:
fun1(x,y); //使用辗转相除法
z=fun1(x,y);
printf("%d和%d这两个数最大公约数为%d\n",x,y,z);
break;
case 2:
fun2(x,y); //使用穷举法
z=fun2(x,y);
printf("%d和%d这两个数最大公约数为%d\n",x,y,z);
break;
case 3:
fun3(x,y); //使用更相减损法
z=fun3(x,y);
printf("%d和%d这两个数最大公约数为%d\n",x,y,z);
break;
case 4:
fun4(x,y); //使用Stein算法
z=fun4(x,y);
printf("%d和%d这两个数最大公约数为%d\n",x,y,z);
break;
}
printf("是否使用其它算法计算本组数据的最大公约数？\n");
printf("是----------------------------1\n");
printf("否----------------------------2\n");
scanf("%d",&temp);
while(temp>2||temp<1)
{
printf("您的操作有误，请重新选择你的操作:");
scanf("%d",&temp);
}
if(temp==2)
break;
else
printf("请选择使用的方法:\n");
}
}
四、调试，测试及运行结果
采用断点调试法逐步调试关键步骤变量正确性：
1.调试主函数中从键盘获取数据函数能否将输入数值赋予变量x，y
根据显示可以成功赋值。
2.调试自定义函数fun1（x，y）能否将形参x，y传递给实参a，b，以及处理a，b的大小关系并返回正确的数值。
变量a，b正确被赋值以及调换数值。
Fun1（）函数正确返回12和114的最大公约数6。Fun1（）函数调试完成。
3.调试自定义函数fun2（）能否正确执行函数内语句。
变量a，b正确赋值。
条件选择语句正确执行。
最终返回正确的最大公约数6。Fun2（）函数调试完成。
4.调试自定义函数fun3（）能否正确执行语句。
变量m，n正确赋值。
正确返回最大公约数的值2*3=6。函数fun3（）调试完成。
5.调试自定义函数fun4（）能否正确执行语句。
变量x，y正确赋值。
X，y开始为12,114。正确执行if语句后变量x，y的值为114,12变量值正确调换。
函数返回正确的最大公约数的值(x<<factor)，x为3，factor为1，结果为6。函数fun4（）调试完成。
4种算法对应的自定义函数全部调试完成，正常运行，调试完毕。
测试：使用头文件stdlib.h中的随机生成数字函数rand()生成所需要的数据分别调用4种算法对应的函数计算每一组数据的最大公约数并在屏幕上输出。定义clock_t类型的变量 start,end,sum用于记录时间，在每一种算法对应的函数之前添加代码start=clock();用来记录算法运行的初试时间，在算法执行结束后添加代码end=clock();用来记录算法运行的结束时间，另外添加代码time=(double)(end-start)/CLOCKS_PER_SEC;用来计算此算法程序运行时间并除以CLOCKS_PER_SEC将时间从毫秒转换为秒，最后添加代码printf(“使用穷举法计算%d组数据的最大公约数花费时间为%f秒\n”,i/2,time);在屏幕上输出运行时间。随机生成数据并分组显示在屏幕上的代码如下：
while(k<sum) //sum为需要测试数据个数
{
printf(“第%d组数据为:\t”,k/2+1);
shuju[k]=rand()%100+1;
printf(“%d\t”,shuju[k++]);
shuju[k]=rand()%100+1;
printf(“%d\n”,shuju[k++]);
}
使用随机生成20组数据进行测试并计算程序运行的时间：
使用辗转相除法测试计算20组数据最大公约数的时间为0.007秒
使用穷举法测试计算20组数据最大公约数的时间为0.017秒
使用用更相减损法测试计算20组数据最大公约数的时间为0.018秒
使用Stein算法测试计算20组数据最大公约数的时间为0.017秒
根据结果显示在计算20组数据最大公约数时使用辗转相除法是耗时最短的为0.007秒，而更相减损法是耗时最长的为0.018秒。
使用随机生成40组数据进行测试并计算程序运行的时间：
使用辗转相除法测试计算40组数据最大公约数的时间为0.019秒
使用穷举法测试计算40组数据最大公约数的时间为0.029秒
使用更相减损法测试计算40组数据最大公约数的时间为0.03秒
使用Stein算法测试计算40组数据最大公约数的时间为0.027秒
根据结果显示在计算40组数据的最大公约数时使用辗转相除法耗时最短为0.019秒，而使用更相减损法耗时最长为0.03秒。
使用随机生成60组数据进行测试并计算程序运行的时间：
使用辗转相除法测试计算60组数据最大公约数的时间为0.027秒
使用穷举法测试计算60组数据最大公约数的时间为0.054秒
使用更相减损法测试计算60组数据最大公约数的时间为0.052秒
使用Stein算法测试计算60组数据最大公约数的时间为0.047秒
根据结果显示在计算60组数据最大公约数时使用辗转相除法耗时最短为0.027秒，而使用穷举法耗时最长为0.054秒。
在使用辗转相除法分别计算20、40、60组数据最大公约数时耗时分别为0.007秒、0.019秒、0.027秒，平均时间为（0.007+0.019+0.027）/3=0.0177秒。
在使用穷举法分别计算20、40、60组数据最大公约数时耗时分别为0.017秒、0.029秒、0.054秒，平均时间为（0.017+0.029+0.054）/3=0.0333秒。
在使用更相减损法分别计算20、40、60组数据最大公约数时耗时分别为0.018秒、0.03秒、0.052秒，平均时间为（0.018+0.03+0.052）/3=0.0333秒。
在使用Stein算法分别计算20、40、60组数据最大公约数时耗时分别为0.017秒、0.027秒、0.047秒，平均时间为（0.017+0.027+0.047）/3=0.0303秒。
分析可得在4种计算最大公约数的算法中，辗转相除法耗时是相对最少的，而另外三种算法（穷举法、更相减损法、Stein算法）耗时相近且相对较长。
五、经验归纳
在编写程序时遇到了一些困难：出现了一些乱码，程序无限循环不能正常运行，条件选择出现错误执行等等。最后都慢慢修改得到解决，并有以下总结：
1.在编写程序代码时使用循环语句和条件选择语句的时候很容易出错，要么无限循环，要么是无法完成预期的功能，所以在编写循环语句的时候可以在语句中添加中间变量用于查看哪里出现了错误，程序完成之后可以直接在中间变量部分加上注释，方便理解也不会对程序运行结果产生负面影响。
2.在编写scanf()函数时，忘记变量前面的取地址符&或者判等时少写一个等号 ，导致程序出现乱码，以后编写程序时应该细心，少出现这种低级错误。