C语言求两数最大公约数的四种算法
实验目的
1.明确算法的概念和特点；
2.通过对问题的分析，设计合理的算法解决问题。
实验内容
运行最大公约数的常用算法，并进行程序的调式与测试，要求程序设计风格良好，并添加异常处理模块（如输入非法等）。
题目分析
求两数的最大公约数，常用的算法有辗转相除法、穷举法、更相减损法、Stein算法等。将每一种算法用一个函数实现，再在主函数中用switch()语句调用任意一种算法，并且在主函数中利用rand()、srand()函数来产生随机函数进行每种算法平均运行时间的测试。
算法构造
辗转相除法
算法过程： 前提设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给a；
5、返回第二步。
流程图
代码
int divisor1(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.函数递归调用）
int divisor2(int a,int b)
{
if(a%b==0) //若a,b取余后余数为0，则返回最大公约数b
return b;
else
return divisor2(b,a%b); //否则递归调用，继续取余
}
穷举法
算法过程：对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
流程图
代码
int divisor3(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);
}
更相减损法
算法过程：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
流程图：
代码
int divisor4(int m,int n)
{ int i=0,temp,x;
while(m%2==0&&n%2==0) //判断a,b是否都是偶数，若是则用2约简
{
m/=2;
n/=2;
i+=1; //约简2的个数
}
if(m<n) //a保存最大值
{
temp=m;
m=n;
n=temp;
}
while(x) //当x不为0时
{
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;
}
Stein算法
算法过程：Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。最大公约数的性质有 gcd( kx,ky ) = 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 )；
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(int x,int y)
{
int factor=0;
int temp;
if(x<y)
{
temp=x;
x=y;
y=temp;
}
if(y==0)
return 0; //0能被任何非0数整除
while(x!=y)
{
if(x&0x1) //0x表示16进制
{
if(y&0x1) //x,y同为奇数
{
y=(x-y)>>1;
x=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);
}
源代码
#include<stdio.h>
#include<stdlib.h>
#include<math.h> //pow(2,i)的头文件
#include<time.h> //计算程序运行时间及随机产生数的头文件
//辗转相除法（1.函数嵌套调用）
int divisor1(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.函数递归调用）
int divisor2(int a,int b)
{
if(a%b==0) //若a,b取余后余数为0，则返回最大公约数b
return b;
else
return divisor2(b,a%b); //否则递归调用，继续取余
}
//穷举法
int divisor3(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 divisor4(int m,int n)
{
int i=0,temp,x;
while(m%2==0&&n%2==0) //判断a,b是否都是偶数，若是则用2约简
{
m/=2;
n/=2;
i+=1; //约简2的个数
}
if(m<n) //a保存最大值
{
temp=m;
m=n;
n=temp;
}
while(x) //当x不为0时
{
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;
}
//Stein算法
int Stein(int x,int y)
{
int factor=0;
int temp;
if(x<y)
{
temp=x;
x=y;
y=temp;
}
if(y==0)
return 0;//0能被任何非0数整除
while(x!=y)
{
if(x&0x1)//0x表示16进制
{
if(y&0x1)//x,y同为奇数
{
y=(x-y)>>1;
x=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,temp;
int m,n,p,i,N,s[100];
printf("--------------You have two options-------------\n");
printf(" 1.求两数最大公约数的操作\n");
printf(" 2.计算程序运行时间及随机数测试操作\n");
printf("-----------------------------------------------\n");
printf("Please input a number you want:\n ");
scanf("%d",&n);
if(n<1||n>2)
{
printf("error! Please input again!\n");
scanf("%d",&n);
}
if(n==1)
{
printf("请输入两个正整数（用逗号隔开）:\n");
scanf("%d,%d",&x,&y);
printf("There are five ways to find the greatest common divisor,you can choose one:\n");
printf("-----------------选择方法-------------------\n");
printf(" 1.辗转相除法（函数嵌套调用） \n");
printf(" 2.辗转相除法（函数递归调用） \n");
printf(" 3.穷举法 \n");
printf(" 4.更相减损法 \n");
printf(" 5.Stein算法 \n");
printf("--------------------------------------------\n");
while(1)
{
printf("Please input the way of you choice:\n");
scanf("%d",&m);
switch(m)
{
case 1:
printf("The way you choice is first(辗转相除法-函数嵌套调用)\n");
temp=divisor1(x,y);
printf("The greatest common divisor is %d\n",temp);
break;
case 2:
printf("The way you choice is second(辗转相除法-函数递归调用)\n");
temp=divisor2(x,y);
printf("The greatest common divisor is %d\n",temp);
break;
case 3:
printf("The way you choice is third(穷举法)\n");
temp=divisor3(x,y);
printf("The greatest common divisor is %d\n",temp);
break;
case 4:
printf("The way you choice is fourth(更相减损法 )\n");
temp=divisor4(x,y);
printf("The greatest common divisor is %d\n",temp);
break;
case 5:
printf("The way you choice is fifth(Stein算法 )\n");
temp=Stein(x,y);
printf("The greatest common divisor is %d\n",temp);
break;
}
}
}
else if(n==2)
{
clock_t start,finish;
double T;
srand((unsigned)time(NULL));
printf("你想测试多少组数据:\n");
scanf("%d",&N);
for(i=0;i<N;i++)
{
s[i]=rand()%500+1;
printf("%d ",s[i]);
}
printf("\n");
printf("There are five ways to find the greatest common divisor,you can choose one:\n"); //选择菜单
printf("-----------------选择方法-------------------\n");
printf(" 1.辗转相除法（函数嵌套调用） \n");
printf(" 2.辗转相除法（函数递归调用） \n");
printf(" 3.穷举法 \n");
printf(" 4.更相减损法 \n");
printf(" 5.Stein算法 \n");
printf("--------------------------------------------\n");
while(1)
{
int j=0;
printf("Please input the way of you choice:\n");
scanf("%d",&p);
while(p<1||p>5)
{
printf("输入错误！请重新输入:\n");
scanf("%d",&p);
}
switch(p)
{
case 1:
start=clock(); //程序运行，开始计时
while(j<N)
{
x=s[j++];
y=s[j++];
temp=divisor1(x,y);
printf("The greatest common divisor is %d\n",temp);
}
finish=clock(); //程序运行结束，结束计时
break;
case 2:
start=clock();
while(j<N)
{
x=s[j++];
y=s[j++];
temp=divisor2(x,y);
printf("The greatest common divisor is %d\n",temp);
}
finish=clock();
break;
case 3:
start=clock();
while(j<N)
{
x=s[j++];
y=s[j++];
temp=divisor3(x,y);
printf("The greatest common divisor is %d\n",temp);
}
finish=clock();
break;
case 4:
start=clock();
while(j<N)
{
x=s[j++];
y=s[j++];
temp=divisor4(x,y);
printf("The greatest common divisor is %d\n",temp);
}
finish=clock();
break;
case 5:
start=clock();
while(j<N)
{
x=s[j++];
y=s[j++];
temp=Stein(x,y);
printf("The greatest common divisor is %d\n",temp);
}
finish=clock();
break;
}
T=(double)(finish-start)/1000; //计算时间差，由于计算机计算的是毫秒，转换成秒要除以1000
printf("这个方法的运行时间是%f秒\n",T);
}
}
}
调试、测试及运行结果
运行结果
调试结果
测试运行时间
经验总结
遇到的问题
1.对于Stein算法自己没有理解清楚，看了程序也是似懂非懂，但想了一下觉得还是要弄明白，所以又在****上查了很多资料，也请教了身边的同学，对于这个算法是最后弄明白的。
2.对于在不同规模测试数据的情况下比较四种算法的运行时间，刚开始并没有想到用随机函数来产生数据，而是想手动输入，但这样的做法显然有局限性，对于随机函数也是参考了很多资料。
总结
四种算法相对来说，前两种方法比较简单，也容易理解，后两种算法确实需要思考、查资料，其中对于第三种更相减损法，我想的是：可不可以不用判断两数是否是偶数，直接在循环中大数减小数，直到两数相等。自己动手试了一下，这样确实也可以求出最大公约数，而且比较简单、容易理解。所以，通过这个例子，我觉得每一次的问题的答案都不应该是唯一的，我们应该勇于尝试新的方法。