第一章：程序的算法设计
1.实验目的
a.明确算法的概念和特点。
b.通过对问题的分析，设计合理的算法解决问题；
2.题目描述
运行最大公约数的常用算法，并进行程序的调式与测试，要求程序设计风格良好，并添加异常处理模块（如输入非法等）。
3.需求分析
可以采用四种常用算法求取最大公约数,由计算机随机产生一定量的随即数组
- 辗转相除法
- 穷举法
- 更相减损法
- Stein算法。
4.算法设计
4.1辗转相除法
辗转相除法，又称欧几里得算法，其算法原理是：首先用两个正整数中较大的数作为被除数，用较小的数做除数进行除法运算，若余数不为0，再把上次的除数作为被除数，把上次的余数作为下次的除数，直到余数是0为止，此时的除数即为两数的最大公约数。
4.1.1算法分析
前提：利用随机函数随机产生数组a和数组b
(1).大数放a中、小数放b中；
(2).求a/b的余数；
(3).若temp=0则b为最大公约数；
(4).如果temp!=0则把b的值给a、temp的值给a；
(5).返回第二步；
4.1.2算法实现
int gcd(int a,int b)
{
if(a%b==0)
return b;
else;
return gcd(b,a%b);
}
4.2穷举法（利用数学定义）
穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：
从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。
4.2.1算法分析
前提：利用随机函数产生两个随即数组a和b
对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
4.2.2算法实现
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);//返回满足条件的数到主调函数处
4.3更相减损法
更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”
翻译成现代语言如下：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
4.3.1算法实现
int gcd2(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;
}
4.4 Stein算法
Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。来研究一下最大公约数的性质，发现有 gcd( kx,ky ) = kgcd( x,y ) 这么一个非常好的性质。试取 k=2，则有 gcd( 2x,2y ) = 2 * gcd( x,y )。很快联想到将两个偶数化小的方法。那么一奇一个偶以及两个奇数的情况如何化小呢？
4.4.1算法分析
前提：利用随机函数产生两个随即数组a和b，对两个正整数 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 )；
5.调试及测试
5.1调试界面
5.2数据测试
因为在VC++6.0上进行测试每种方法数据运行时间有误，于是在线上编译软件菜鸟编译上进行数据测试。
5.2.1测试10组数据
对10组数据时测试结果分析，发现，在相同数据情况下Stein算法运行时间最短，更相减损数运行时间最长。
5.2.2测试30组数据
对30组数据时测试结果分析，发现，在相同数据情况下辗转相除法运行时间最短，更相减损数运行时间最长。
5.2.3测试100组数据
对100组数据时测试结果分析，发现，在相同数据情况下辗转相除法运行时间最短，更相减损数运行时间最长
5.2.4结果分析
|
数据规模 |
辗转相除法 |
穷举法 |
更相减损术 |
Stein算法 |
|
10组*10^6 |
6 |
6 |
72 |
5 |
|
30组*10^6 |
8 |
33 |
82 |
11 |
|
100组*10^6 |
29 |
60 |
116 |
38 |
由此可得在数据规模及其小时，适合选用Stein算法，除此之外，更适合选用辗转相除法，穷举法和更相减损术不论数据规模大小都不推荐选用。
6．菜鸟编辑器截图
