最大公约数相关
一、题目分析
分别用辗转相除法、枚举法、更相减损法、stein算法求最大公约数，并测试比较几种算法在不同规模测试数据下的平均运行时间。
二、算法构造（流程图）
辗转相除法
枚举法
更相减损法
stein算法
三、算法实现
辗转相除法非递归实现
var foo = 'bar';
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); /*返回最大公约数到调用函数处*/
}
辗转相除法递归实现
var foo = 'bar';
int gcd (int a,int b)
{ if(a%b==0)
return b;
else
return gcd(b,a%b);
}
穷举法实现
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); /*返回满足条件的数到主调函数处*/
}
更相减损术实现
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;
}
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 );
}
Stein算法递归实现
int gcd(int u,int v)
{
if (u == 0) return v;
if (v == 0) return u;
// look for factors of 2
if (~u & 1) // u is even
{
if (v & 1) // v is odd
return gcd(u >> 1, v);
else // both u and v are even
return gcd(u >> 1, v >> 1) << 1;
}
if (~v & 1) // u is odd, v is even
return gcd(u, v >> 1);
// reduce larger argument
if (u > v)
return gcd((u - v) >> 1, v);
return gcd((v - u) >> 1, u);
}
主函数
int main()
{
int(*f[6])(int,int) = { zhanzhuandigui,zhanzhuanfeidigui,meiju,jiansun,Stein_digui,Stein_feidigui };
/*辗转相除递归、非递归，枚举，更相减损，stein递归、非递归赋给函数指针数组*/
int a, b, c;
while (1)
{
cout << "请输入要计算最大公约数的两数a，b" << endl;
cin >> a >> b;
cout << "请选择要使用的计算方法" << '\n'\
<< "1.辗转相除递归 2.辗转相除非递归 3.枚举 4更相减损 5.stein递归 6.stein非递归赋" << endl;
cin >> c;
switch (c)
{
case 1:cout << f[0](a, b) << endl; break;
case 2:cout << f[1](a, b) << endl; break;
case 3:cout << f[2](a, b) << endl; break;
case 4:cout << f[3](a, b) << endl; break;
case 5:cout << f[4](a, b) << endl; break;
case 6:cout << f[5](a, b) << endl; break;
default:
break;
}
cout << "输入1退出,其他键继续" << endl;
cin >> c;
if (c == 1) break;
}
return 0;
}
四、调试、测试及运行结果
对测试代码进行调试
对各种不同算法效率进行测试的测试代码
int main()
{
int(*f[6])(int,int) = { zhanzhuandigui,zhanzhuanfeidigui,meiju,jiansun,Stein_digui,Stein_feidigui };
/*辗转相除递归、非递归，枚举，更相减损，stein递归、非递归赋给函数指针数组*/
int a, b, c;
DWORD t_start, t_end;
t_start = GetTickCount();
fstream f1;
//f1.open("1到100.txt",ios::in);
f1.open("自带随机数.txt",ios::in);
cout << "请选择要使用的计算方法" << '\n'\
<< "1.辗转相除递归 2.辗转相除非递归 3.枚举 4更相减损 5.stein递归 6.stein非递归赋" << endl;
cin >> c;
t_start = GetTickCount();
while(!f1.eof())
//for (int i = 0; i < 10000; i++)
{
f1 >> a >> b;
cout << f[c - 1](a, b) << endl;
}
t_end = GetTickCount();
system("cls");
std::cout << t_end - t_start << std::endl;
system("pause");
return 0;
}
测试结果（单位毫秒）
运行结果
五、总结归纳与疑问
复习了函数指针数组的用法，学习了通过Windows.h来进行较为精确的运行时间测定。在运行时间的测试过程中，用到了随机数生成器。在测试的过程中，发现了将运算结果输出到屏幕上会占用比较多的时间。在之前的学习中，我了解到函数递归调用相较于非递归调用会有更多的内存开销，似乎运行速度也会因此减慢，但是实际测试结果并不完全符合理论，有待进一步的学习验证。