最大公约数
第一章上机 最大公约数
实验内容：运行最大公约数的常用算法，并进行程序的调式与测试，要求程序设计风格良好，并添加异常处理模块（如输入非法等）。
- 题目分析
（1）如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。根据约数的定义可知，某个数的所有约数必不大于这个数本身，几个自然数的最大公约数必不大于其中任何一个数。要求任意两个正整数的最大公约数即求出一个不大于其中两者中的任何一个，但又能同时整除两个整数的最大自然数。
（2）求取最大公约数有多种算法，我选取了四种方法；辗转相除法（递归方法）、穷举法（递归法）、更相减损法（非递归）、Stein算法（非递归）。
（3）在输入数据时，考虑到效率和规范格式，我想到使用随机数的生成，让它的范围被控制在1到100内。
2.算法构造
2.1主函数算法
（1）主函数中的测试数据不用手动输入，利用生成随机数的方法给二维数组赋值。
利用随机数发生器rand((unsigned int)(time(NULL))，用来生成随机数1~100。首先给srand()提供一个种子，它是一个unsigned int类型，其取值范围从0~65535；然后调用rand()，它会根据提供给srand()的种子值返回一个随机数(在1到100之间)根据需要多次调用rand()，从而不间断地得到新的随机数。
（2）计算4种GCD算法在给定不同规模测试数据的情况下的平均运行时间。
利用计时时间clock( )函数，精确到微妙时间。在计算最大公约数之前计时开始，之后计时结束，并输出时间。2.2 四个求最大公约数算法
（1）辗转相除法（递归方法）
（2）穷举法（递归法）
（3）更相减损法（非递归）
（4）Stein算法（非递归）
3.算法实现
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#include<windows.h>
#include<math.h>
#include<time.h>
#define MAX 100
//辗转相除法（递归）
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); /*返回最大公约数到调用函数处*/
}
//穷举法（递归）
int qiongju(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 jiansun(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;
}
//Stein算法（非递归）
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 );
}
//主函数
int main()
{
int a[10002];
int i,j;
double run_time;
_LARGE_INTEGER time_start; //开始时间
_LARGE_INTEGER time_over; //结束时间
double dqFreq; //计时器频率
LARGE_INTEGER f; //计时器频率
QueryPerformanceFrequency(&f);
dqFreq=(double)f.QuadPart;
srand((unsigned)time(NULL));
int k;//记录几组数
cout<<"请输入您想要比较几组整数的最大公约数"<<endl;
scanf("%d",&k);
printf("随机生成%d组整数",k);
int count[MAX][2];
for(i=0;i<k;i++)
for(j=0;j<2;j++)
{
count[i][j]=rand()%100;// /随机数生成,范围为1~100
printf("%d\t",count[i][j]);
}
cout<<endl;
int select;//case语句中的选项
char s='Y';//开始先让s为有效值，进行第一次的操作，之后再根据用户的需求让系统退出或继续
while(s=='Y')
{
cout<<"请问您要用哪种方法进行计算"<<endl;
cout<<"请选择数字编号1~4"<<endl;
cin>>select;
while(!(select>=1&&select<=4))
{
cout<<"输入有误，请重新输入："<<endl;
cin>>select;cout<<endl;
}
for(i=0;i<k;i++)
{
int m,n,t1;
m=count[0][i];
n=count[1][i];
printf("计算%d和%d的最大公约数\n",m,n);
QueryPerformanceCounter(&time_start); //计时开始
switch(select)
{
case 1:t1=divisor(count[i][0],count[i][1]);break;
case 2:t1=qiongju(count[i][0],count[i][1]);break;
case 3:t1=jiansun(count[i][0],count[i][1]);break;
case 4:t1=Stein(count[i][0],count[i][1]);break;
}
printf("您输入的两个整数%d和%d的最大公约数为：%d\n",select,m,n,t1);
}
system("cls");//清屏
QueryPerformanceCounter(&time_over); //计时结束
run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq; //乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
printf("用第%d种方法运算出%d组数字的最大公约数花费的时间为：%fus\n（微秒）\n",select,k,run_time);
cout<<"是否使用其他求最大公约数方法继续操作（Y/N）"<<endl;
cin>>s;
if(!(s=='Y'))
{ cout<<"系统退出！！"<<endl;
exit(0);
}
}
return 0;
}
4.调试、测试及运行结果
4.1调试
（1）程序运行后，发现计算后每组数字的最大公约数是为-858993460，是一个无穷小值，经调试后发现是程序中的一行代码写错了 其中的k应该改为i,否则在运行过程中一直没有给count[k][0]赋值，系统就将他的值输出为-858993460。
（2）程序改正后，进行调试，各项数据指标都正常。
4.2测试
（1）测试辗转相除法函数功能
（2）测试穷举法函数功能
（3）测试更相减损法函数功能
（4）测试Stein函数功能
4.3运行结果
根据不同规模下数据求取最大公约数来计算运行时间
（1） 随机生成10组数据
（2） 随机生成20组数据
（3） 随机生成30组数据
根据以上结果，我得出：
当数据规模较小时，辗转相除法的效率最高，更相减损法的效率最低；
当数据规模较大时，辗转相除法效率变慢了，穷举法的效率变快了。更相减损法的效率一直最慢，Stein算法的效率变化幅度不大。
（4） 异常输入（以下为手动输入版的主函数的运行截图，利用随机数给数组赋值的主函数一规避异常输入问题）当手动输入的数小于等于0时，提示重新输入正整数。
（5） 附加功能测试
给主函数中增加了是否再用其他方法给同一组数字求取最大公约数，回复Y出现选择求取方法的提示，回复N提示退出系统。
)
5.经验归纳
（1）当编写程序时定义的变量较多时，一定要注意各个变量应该用在何处，我就是因为这个错误，造成了程序结果输出的错误，经调试后发现的错误。
（2）当看到一个编程题时，不能急着下手，先要在脑中或纸上设计自己的算法，方法，并要优先考虑效率高的算法，不能只是写出来就好。
（3）在此次试验中，我还学会了生成随机数函数的用法，这个函数提高了输入数据的效率，并且规避了异常输入的问题。
（4）计算不同规模测试数据的情况下的平均运行时间时，我学会使用了clock（）函数，在以后的编程中我也可以使用它来知道算法的效率高低。
（5）我设计的程序运行一次可以选择多种算公约数的方法，每用一种方法，运行界面就会出现多行结果，我觉得这样让界面太过，就是用了system(“cls”);清屏函数。
（6）再复杂的编程题，都会有突破口，遇到困难不能避免，我们应该迎难而上。