用辗转相除法，穷举法，更相减损法，stein求两个数的最大公约数，并比较时间。
- 题目分析
用四种不同的方法求两个数的最大公约数
辗转相除法：
其算法过程为：前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给a；
5、返回第二步；
穷举法：
穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
更相减损法：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
.Stein算法
整理一下，对两个正整数 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 ，就用这个。
流程图：
- 算法实现
#include "stdio.h"
#include"stdlib.h"
#include"time.h"
#include"math.h"
#include"iostream"
using namespace std;
/*辗转相除法*/
int d1(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 d2 (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 d3(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) d3(2,i)*n;
}
/*Stein算法*/
int d4( 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[50] ;
int i,t;
srand((unsigned)time(NULL));/*播种子*/
for(i = 0; i < 50; i++)
{
a[i] = rand() % 50;/*产生50以内的随机整数*/
printf("%d\t",a[i]);
}
printf("\n");
for(int b=1;b<=4;b++)
{
printf("输入你想选择的方法：");
scanf("%d",&t);
clock_t start, finish;
double duration;
start =clock();
for(i=0;i<20;i++) //每组数据开始遍历
{
switch(t)
{
case 1:printf("辗转相减法所得最大公约数为：%d\n",d1(a[2*i],a[2*i+1]));break;
case 2:printf("穷举法所得最大公约数为：%d\n",d2(a[2*i],a[2*i+1]));break;
case 3:printf("更相减损法所得最大公约数为：%d\n",d3(a[2*i],a[2*i+1]));break;
case 4:printf("Stein算法所得最大公约数为：%d\n",d4(a[2*i],a[2*i+1]));break;
}
}
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "time=%f seconds/n", duration );
system("pause");
}
}
调试图：
测试图：
辗转相除法运行结果
穷举法运行结果
更相减损发运行结果
Stein方法运行结果
结论：辗转相除法时间更短一点，但和更相减损法，stein相比差不多，穷举法最慢
- 经验归纳
在本次上机操作中，我们主要是用四种不同的算法来求解两个数的最大公约数，然后加入随机数组，多次测试，添加时间函数，来计算四种不同方法所需要的时间。通过比较，得出那种方法比较好。在本次实验中我遇到了很多问题。第一，写随机数组时用rand()，但每次随机数相同，后来通过百度寻找解决方法，发现每次产生随机数都调用一次函数，计算机运行时间太快，所以时间一样，要添加时间种子srand((unsigned)time(NULL));/*播种子*/。还有一个问题就是计算时间，不知道时间函数，不知道怎么往里面写，请教了同学，自己也查阅了资料，
clock_t start, finish;
double duration;
start =clock(); finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
同时也发现自己对于调用函数不是很熟悉，这就是要加强的地方。
我相信下次再碰到这种问题，就可以轻松解决了，同时在修改错误时发现要添加相应的头文件。不用怕问题多麻烦，当我们解决了这些问题时就是在增长知识的过程。我们会慢慢积累。有所提高。