求最大公约数
题目名称
求最大公约数
题目要求
运行最大公约数的常用算法，并进行程序的调式与测试，要求程序设计风格良好，并添加异常处理模块（如输入非法等）。
算法设计
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的值给b；
(5)、返回第二步；
代码如下：
int divisor1(int a,int b)//辗转相除法求最大公约数
{
int t;
if(a<b)//大数放a中，小数放b中
{
t=a;
a=b;
b=t;
}
while(b!=0&&a%b!=0)//余数不为0，继续相除，直到余数为0
{
t=a%b;
a=b;
b=t;
}
return b;//返回最大公约数到调用函数处
}
2.穷举法（利用数学定义）
穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：
从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。
对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
代码如下：
int divisor2(int a,int b)//穷举法（枚举法）求最大公约数
{
int t;
t=(a>b)?b:a;//采种条件运算表达式求出两个数中的最小值
while(t>0)
{
if(a%t==0&&b%t==0)
break;//只要找到一个数能同时被a,b所整除，则中止循环*/
t--; //如不满足if条件则变量自减，直到能被a,b所整除
}
return t;// 返回最大公约数到调用函数处
}
3. 更相减损法
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
代码如下：
int divisor3(int a,int b)//更相减损法求最大公约数
{
int i=0,t,m;
if(a<b)//大数放a中，小数放b中
{
t=a;
a=b;
b=t;
}
while(a%2==0&&b%2==0)//a和b为偶数，用2约简，判断m和n能被多少个2整除
{
a=a/2;
b=b/2;
i+=1;
}
while(m)// 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数
{
m=a-b;
a=(m>b)?m:b;
b=(m<b)?m:b;
if(b==(a-b))
break;//减数和差相等，结束循环
}
if(i==0)
return b;//返回最大公约数到调用函数处
else
return (double)pow(2,i)*b;//返回最大公约数到调用函数处
}
4.Stein算法
对两个正整数 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 )；
代码如下：
int divisor4(int a,int b)//Stein算法求最大公约数
{
int factor=0;
int t;
if(a<b)//大数放a中，小数放b中
{
t=a;
a=b;
b=t;
}
while(a!=b)
{
if(a&0x1)//当a为奇数
{
if(b&0x1)//当a和b均为奇数
{
b=(a-b)>>1;
a-=b;
}
else//当a为奇数，b为偶数
{
b>>=1;
}
}
else//当a为偶数
{
if(b&0x1)//当a为偶数，b为奇数
{
a>>=1;
if(a<b)
{
t=a;
a=b;
b=t;
}
}
else//当a和b均为偶数
{
a>>=1;
b>>=1;
++factor;
}
}
}
return (a<<factor);
}
完整程序代码
#include"stdio.h"
#include"math.h"
#include"stdlib.h"
#include"time.h"
#define N 100
int divisor1(int a,int b)//辗转相除法求最大公约数
{
int t;
if(a<b)//大数放a中，小数放b中
{
t=a;
a=b;
b=t;
}
while(b!=0&&a%b!=0)//余数不为0，继续相除，直到余数为0
{
t=a%b;
a=b;
b=t;
}
return b;//返回最大公约数到调用函数处
}
int divisor2(int a,int b)//穷举法（枚举法）求最大公约数
{
int t;
t=(a>b)?b:a;//采种条件运算表达式求出两个数中的最小值
while(t>0)
{
if(a%t==0&&b%t==0)
break;//只要找到一个数能同时被a,b所整除，则中止循环*/
t--; //如不满足if条件则变量自减，直到能被a,b所整除
}
return t;// 返回最大公约数到调用函数处
}
int divisor3(int a,int b)//更相减损法求最大公约数
{
int i=0,t,m;
if(a<b)//大数放a中，小数放b中
{
t=a;
a=b;
b=t;
}
while(a%2==0&&b%2==0)//a和b为偶数，用2约简，判断m和n能被多少个2整除
{
a=a/2;
b=b/2;
i+=1;
}
while(m)// 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数
{
m=a-b;
a=(m>b)?m:b;
b=(m<b)?m:b;
if(b==(a-b))
break;//减数和差相等，结束循环
}
if(i==0)
return b;//返回最大公约数到调用函数处
else
return (double)pow(2,i)*b;//返回最大公约数到调用函数处
}
int divisor4(int a,int b)//Stein算法求最大公约数
{
int factor=0;
int t;
if(a<b)//大数放a中，小数放b中
{
t=a;
a=b;
b=t;
}
while(a!=b)
{
if(a&0x1)//当a为奇数
{
if(b&0x1)//当a和b均为奇数
{
b=(a-b)>>1;
a-=b;
}
else//当a为奇数，b为偶数
{
b>>=1;
}
}
else//当a为偶数
{
if(b&0x1)//当a为偶数，b为奇数
{
a>>=1;
if(a<b)
{
t=a;
a=b;
b=t;
}
}
else//当a和b均为偶数
{
a>>=1;
b>>=1;
++factor;
}
}
}
return (a<<factor);
}
int main()
{
int i=0,j=0,m,n;
int num[N][2]={0};
srand(time(0));//随机数生成
for(i=0;i<N;i++)
for(j=0;j<2;j++)
num[i][j]=rand()%10000+1; //生成0-10000以内的随机数
printf("请输入想要生成的随机数的组数：\n");
scanf("%d",&n);
printf("随机数；\n");
for(i=0;i<n;i++)
{
for(j=0;j<2;j++)
{
printf("%d\t",num[i][j]);
}
printf("\n");
}
int choose,t;
//菜单
printf("**************************\n");
printf("*******求最大公约数*******\n");
printf("*******1.辗转相除法*******\n");
printf("*****2.穷举法(枚举法)*****\n");
printf("*******3.更相减损法*******\n");
printf("*******4.Stein算法********\n");
printf("*******5.退出本菜单*******\n");
printf("**************************\n");
while(1)
{
printf("请选择要使用的算法：\n");
scanf("%d",&choose);
if(choose>5)
{
printf("\n输入错误！请在1-5之间重新选择：\n");
scanf("%d",&choose);
}
clock_t startTime,endTime;
startTime=clock();//记录算法运行开始的时间
switch(choose)//选择求最大公约数的算法，输出最大公约数
{
case 1:
for(i=0;i<n;i++)
{
t=divisor1(num[i][0],num[i][1]);
printf("%d和%d最大公约数为%d;\n",num[i][0],num[i][1],t);
}
break;
case 2:for(i=0;i<n;i++)
{
t=divisor2(num[i][0],num[i][1]);
printf("%d和%d最大公约数为%d;\n",num[i][0],num[i][1],t);
}
break;
case 3:for(i=0;i<n;i++)
{
t=divisor1(num[i][0],num[i][1]);
printf("%d和%d最大公约数为%d;\n",num[i][0],num[i][1],t);
}
break;
case 4:for(i=0;i<n;i++)
{
t=divisor1(num[i][0],num[i][1]);
printf("%d和%d最大公约数为%d;\n",num[i][0],num[i][1],t);
}
break;
case 5:exit(0);
}
long m = 10000000L;
double totalTime;
while( m-- );
endTime=clock();//记录算法运行结束的时间
totalTime=(double)(endTime-startTime)/CLOCKS_PER_SEC;//计算算法的运行时间
printf("该算法运行所用的时间为%f秒;\n",totalTime);
system("pause");
}
}
调试截图
测试截图
图1 生成随机数
图2 穷举法求最大公约数
图3 辗转相除法求最大公约数
图4 更相减损法求最大公约数
图5 Stein算法求最大公约数
图6 功能选择异常判断，退出程序
通过对这四种算法的比较，可以看出辗转相除法求最大公约数所用的时间最少。
实验总结
深入学习了利用不同的算法来求解两个正整数的最大公约数，还学习了随机数的生成以及clock()函数的使用。存在的问题主要是对循环语句掌握的不是很好，所以在写代码时频繁出错，导致运行的结果总是不如人意，花费了很长时间去修改循环语句，也向同学请教，最后完成了源代码。通过这次作业，我收获了很多知识，今后会不断学习、不断完善，努力写出更好的代码。