**第一章 程序的算法设计**

一、题目要求
运行最大公约数的常用算法，并进行程序的调试与测试，要求程序设计风格良好，并添加异常处理模块（如输入非法等）。
二、算法构造
程序的思路大致为：
（1）利用随机函数rand()随机生成[1,100]的数；
（3）用户根据提供的6种算法选择输入算法的序号即可执行该算法；
（4）计算出该算法执行的时间。

下面分别给出四种算法的流程图：
1.辗转相除法（嵌套调用）（如图2-1）：
其算法过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给a；
5、返回第二步；

2.辗转相除法（递归调用）

3.穷举法（如图2-3）：穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。
定义:对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。

4.更项减损法（如图2-4）：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

5.Stein法（非递归调用）（如图2-5）：
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 ，就用这个。

6.辗转相除法（递归调用）（如图2-6）：
![图2-6 Stein算法（递归）流程图](https://img-blog.csdnimg.cn/2019030913304867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI2MDM1MA==,size_16,color_FFFFFF,t_70
图2-6 Stein算法（递归）流程图
三、算法实现

/**
 *实验课题：求最大公约数
 *项目创建时间：2019.3.5
 *项目最后一次编辑时间：2019.3.8
 **/

#include"iostream"
#include"time.h"
#include"Windows.h"
#include"stdlib.h"
#include"math.h"
//const int N=500;  //定义数据规模
using namespace std;

//辗转相除法 嵌套调用
//自定义函数求两数的最大公约数
int divisor1(int a,int b)
{
	int temp;/*定义整型变量*/
	if(a<b)   /*通过比较求出两个数的最大值和最小值，保证变量a的值最大*/
	{
		temp=a;
		a=b;
		b=temp;
	}
	while(b!=0)
	{
		temp=a%b;
		a=b;
		b=temp;
	}
	return (a);   /*返回最大公约数到调用函数处*/
}

//自定义函数求两数的最小公倍数
int multiple1(int a,int b)
{
	int divisor(int a,int b);  /*自定义函数返回值类型*/
	int temp;					
	temp=divisor1(a,b);			//再次调用自定义函数，求最大公约数
	return (a*b/temp);          //返回最小公倍数到主函数进行输出
}



//辗转相除法 递归调用
int gcd1(int a,int b)
{
	if(a%b==0)
		return b;
	else
		return gcd1(b,a%b);
}

//方法2：穷举法
//穷举法求最大公约数
int divisor2 (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 multiple2 (int a,int b)
{
  int p,q,temp;
  p=(a>b)?a:b;   /*求两个数中的最大值*/
  q=(a>b)?b:a;  /*求两个数中的最小值*/
  temp=p;      /*最大值赋给p为变量自增作准备*/
  while(1)   /*利用循环语句来求满足条件的数值*/
  {
    if(p%q==0)
      break;  /*只要找到变量的和数能被a或b所整除，则中止循环*/
    p+=temp;   /*如果条件不满足则变量自身相加*/
  }
  return  (p);
}

//方法三：更相减损法
int gcd3(int m,int n)
{
	int i=0,temp=0,x=1;
	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.0,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 gcd4(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 gcd4(u >> 1, v);
        else // both u and v are even
            return gcd4(u >> 1, v >> 1) << 1;
    }
     if (~v & 1) // u is odd, v is even
        return gcd4(u, v >> 1);
     // reduce larger argument
    if (u > v)
        return gcd4((u - v) >> 1, v);
     return gcd4((v - u) >> 1, u);
}





/**
*和ctime时间库有关的函数：
*clock()函数的返回值是毫秒，返回值类型为浮点型；要输出正确的时间差需要把它换成秒
*换成秒的方式为：除以CLOCKS_PER_SEC（宏定义为 1000）
*
*/

/**思路上：
 *1.先随机生成N组数据，利用二维数组List[2][N]存贮这N组数据，同一列的两个数最为一组进行操作
 *  随机生成的数据范围都在（1，100）
 *2.利用菜单操作，六种算法用户随意选择其中一种，可实现对同组数据的
 */
int main()
{
	int size;
	cout<<"请输入数据的规模（组数）"<<endl;
	cin>>size;
	//动态分配数组
	int (*List)[2]=new int [size][2];
	
	//先随机生成20个数，取每一列的整数求最大公约数和
	//利用二维数组List[size][2]存放N对数，N由程序员宏定义
	//利用rand()随机生成这10对数
	for( int i = 0; i < size ;i++)
		for(int j =0 ; j < 2 ; j++)
			List[i][j]=0;

	//规定随机生成的数范围是(1,100)
	srand((unsigned)time(NULL));
	for(int i = 0 ;i < size ;i++)
		for(int j =0 ; j < 2 ; j++)
	{
		List[i][j]=(rand()%99)+1;
	}

		//直接输出二维数组
		cout<<"以下是系统随机生成的"<<size<<"组数"<<endl;
		for(int j =0 ; j < 2 ; j++)
		{
			for(int i = 0 ;i < size ;i++)
			printf("%d\t",List[i][j]);
			printf("\n");
		}
		
		int m=1;
		while(m)
		{
			cout<<"请选择需要计算的方法（1~6）"<<endl;
			cout<<"1.辗转相除法(嵌套)；"<<endl;
			cout<<"2.辗转相除法(递归)；"<<endl;
			cout<<"3.穷举法；"<<endl;
			cout<<"4.更相减损法；"<<endl;
			cout<<"5.Stein算法(非递归)"<<endl;
			cout<<"6.Stein算法(递归)"<<endl;
			int k;     //计算方法的标号
			cin>>k;
			cout<<endl;
			
			clock_t start_time=clock();//开始计算算法运行的开始时间

			switch(k)//选择算法类型
			{
				case 1://辗转相除法(嵌套)
				{
					 for(int i=0; i < size; i++)
					 {
						 cout<<"The higest common divisor is "<<divisor1(List[i][0],List[i][1])<<endl; /*输出最大公约数*/
					 }
					 break;
				}

				case 2://辗转相除法(递归)
				{
					 for(int i=0; i < size; i++)
					 {
					 cout<<"The higest common divisor is "<<gcd1(List[i][0],List[i][1])<<endl; /*输出最大公约数*/
					 }
					 break;
				}
				case 3://穷举法
				{
					 for(int i=0; i < size; i++)
					 {
						 cout<<"The higest common divisor is "<<divisor2(List[i][0],List[i][1])<<endl; /*输出最大公约数*/
					 }
					 break;
				}
				case 4://更相减损法
				{
					 for(int i=0; i < size; i++)
					 {
						 cout<<"The higest common divisor is "<<gcd3(List[i][0],List[i][1])<<endl; /*输出最大公约数*/
					 }
					 break;
				}
				case 5://Stein算法(非递归)
					 for(int i=0; i < size; i++)
					 {
						 cout<<"The higest common divisor is "<<Stein(List[i][0],List[i][1])<<endl; /*输出最大公约数*/
					 }
					 break;
				case 6://Stein算法(递归)
					 for(int i=0; i < size; i++)
					 {
						 cout<<"The higest common divisor is "<<gcd4(List[i][0],List[i][1])<<endl; /*输出最大公约数*/
					 }
					 break;
				default:exit(1);
			}
			clock_t end_time=clock();//计算算法结束的时间
			//输出算法执行的时间
			cout<<"计算第"<<k<<"种算法的执行时间为："<<double(end_time-start_time)/CLOCKS_PER_SEC<<endl;
			
			//是否返回菜单
			cout<<"是否继续？不继续退出按0"<<endl;
				char q;
				cin>>q;
				if(q=='0')
					m=0;
				system("cls");//清屏
		}
	delete[]List;
	return 0;
}

四、调试
下面就针对各种算法求取最大公约数功能一一取值调试验证。
（一）辗转相除法（嵌套）
有主函数传递参数到该算法函数的两个整数为28和24

经过几次while循环，预期跳出循环时b=0,a=4,a的值正好为最大公约数。实际调试结果截图如下，正好符合预期。

（二）辗转相除法（递归）
有主函数传递参数到该算法函数的两个整数为62和48

经过几次递归，a和b的值变化如下：

显然再最后一次递归中，a正好能够整除b，返回值b=2，符合最大公约数预期值2。
（三）穷举法
有主函数传递参数到该算法函数的两个整数为9和20

图4-5
再while几次循环之中，由于不满足循环之中if的条件，temp变量依次递减，直至为1才满足该条件。最后，返回值为1，符合预期最小公约数1。

图4-6
（四）更相减损法
有主函数传递参数到该算法函数的两个整数为94和32，理论上预期最大公约数应为2。

图4-7
在while循环中，当x=2时，满足循环语句中的的条件跳出循环，返回值为2，符合预期（如图4-8）。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20190309133746265.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI2MDM1MA==,size_16,color_FFFFFF,t_70图4-8
（五）Stein算法（非递归）
有主函数传递参数到该算法函数的两个整数为11和12，理论上预期最大公约数应为1。
图4-9
返回值符合预期值1.
图4-10
（六）Stein算法（非递归）
有主函数传递参数到该算法函数的两个整数为4和54，理论上预期最大公约数应为2。
图4-11
跳出递归循环的局部变量值：
图4-12
五、测试
针对6种算法各自功能的测试，随机给定10组整数，判断求最大公约数的正确性。
为了保证各个方法测试的公平性以及验证的全面性、方便性，让系统随机生成的10组数都一样。生成的10组数如图所示，用户选择不同的方法即可输出各组的最大公约数。
图5-1

1. 测试第一个算法（辗转相除法（嵌套））（如图5-1）
2. 测试第二个算法（辗转相除法（递归））（如图5-3）
   图5-1 图5-2
   经检验，辗转相除法两种方法的10组数据最大公约数的输出结果不仅完全相同而且输入结果也符合预期结果。
3. 测试第三个算法（穷举法）（如图5-3）
   图5-3
   经检验，穷举法的10组数据的最大公约数输出结果符合预期结果。
4. 测试第四个算法（更相减损法）（如图5-4）
   图5-4
   经检验，穷举法的10组数据的最大公约数输出结果符合预期结果。
5. 测试第五个算法（Stein(非递归)）（如图5-5）
6. 测试第六个算法（Stein(递归)）（如图5-6）
   图5-5 图5-6
   经检验，Stein法的两种算法的10组数据的最大公约数输出结果不仅完全相同也符
   合预期结果。
   现进行第二阶段各种算法的执行时间的对比。为了保证执行时间比较的方便性，给予更大的基数。

六、运行结果
判断4种算法各自功能执行的效率。为了更好地判断几种算法的执行效率，给予更大规模的数据，给予不同基数，分别取N=50，100，200判断各种算法执行的时间，即可判断算法的复杂度。
现给予基数N=50，表示系统随机生成50组数据。
下面是系统随机生成的50组数（图6-1）：
图6-1
第一个算法（辗转相除法（嵌套））（如图6-2）的执行时间为：
图6-2
计算第二个算法（辗转相除法（递归））（如图6-3）
图6-3
计算第三个算法（穷举法）（如图6-4）
图6-4
计算第四个算法（更相减损法）（如图6-5）
图6-5
计算第五个算法（Stein(非递归)）（如图6-6）
图6-6
计算第六个算法（Stein(递归)）（如图6-7）
图6-7
综上运行结果执行时间的对比，四种算法执行时间自大而小的顺序为
执行时间顺序：更相减损法> Stein(非递归)> 穷举法> Stein(递归)> 辗转相除法（递归）>辗转相除法（嵌套）；

再给予基数N=100，表示系统随机生成100组数据。
下面是系统随机生成的100组数（图6-8）：
图6-8
第一个算法（辗转相除法（嵌套））（如图6-9）的执行时间为：
图6-9
计算第二个算法（辗转相除法（递归））（如图6-10）
图6-10
计算第三个算法（穷举法）（如图6-11）
图6-11
计算第四个算法（更相减损法）（如图6-12）
图6-12
计算第五个算法（Stein(非递归)）（如图6-13）
图6-13
计算第六个算法（Stein(递归)）（如图6-14）
图6-14
综上运行结果结果执行时间的对比，六种算法执行时间自大而小的顺序为
执行时间顺序：更相减损法> Stein(递归)> 穷举法> Stein(非递归)> 辗转相除法（递归）>辗转相除法（嵌套）；

再给予基数N=200，表示系统随机生成200组数据。
下面是系统随机生成的200组数：

图6-15
第一个算法（辗转相除法（嵌套））（如图6-16）的执行时间为：
图6-16
计算第二个算法（辗转相除法（递归））（如图6-17）
图6-17
计算第三个算法（穷举法）（如图6-18）
图6-18
计算第四个算法（更相减损法）（如图6-19）
图6-19
计算第五个算法（Stein(非递归)）（如图6-20）
图6-20
计算第六个算法（Stein(递归)）（如图6-21）
图6-21
综上运行结果执行时间的对比，六种算法执行时间自大而小的顺序为
执行时间顺序：辗转相除法（嵌套）>穷举法> Stein(非递归)> 更相减损法>辗转相除法（递归）> Stein(递归)
综上不同基数算法执行时间的，六种算法执行时间自大而小顺序为:
N=50 更相减损法> Stein(非递归)> 穷举法> Stein(递归)> 辗转相除法（递归）>辗转相
除法（嵌套）；
N=100 更相减损法> Stein(递归)> 穷举法> Stein(非递归)> 辗转相除法（递归）>辗转相
除法（嵌套）；
N=200 辗转相除法（嵌套）>穷举法> Stein(非递归)> 更相减损法>辗转相除法（递归）>
Stein(递归)

七、 实验心得
1.在该程序的设计中，大体思路是这样的：
（1）利用随机函数rand()随机生成[1,100]的数，程序员利用宏定义const规定测试数据的规模，理论上这个N可以上万；
（2）利用数组存储的顺序性，将这些大规模规模抽象为一个二维数组，这个二维数组有两行，N列。这个二维数组本人定义为List[2][N]，计算最大公约数的两个参数则为List[0][i]、
List[1][i]。
（3）利用菜单功能形式，给予用户更多的选择权。用户根据提供的6种算法选择输入算法的序号即可执行该算法；
（4）在计算该算法，会利用time库函数的函数clock()函数来获取执行该步骤的时间，即可计算出该算法执行的时间。
2.当然本人在完成文档任务后，还发现代码还有许多可以优化的地方，比如：
（1）程序员对N的宏定义限制了用户对数据规模选择的自由。可利用new表达式动态分配数组。具体操作如下：
int (*List)[2]=new int [size][2];
最后程序结束时delete[]List;
（2）比较算法的执行快慢其实可以利用排序算法求得，但本人认为算法就六种，直接观察求得。
3.在执行时间的处理计算上，利用ctime库的函数clock()获取执行某算法步骤的时间，利用start_time和end_time变量求取时间，利用时间差即可得出执行时间。通过程序设计，明白了该函数的一些知识点和注意事项，如：
（1）clock()函数的返回值是毫秒，返回值类型为浮点型；
（2）要输出正确的时间差需要把它换成秒换成秒的方式为：除以CLOCKS_PER_SEC
（宏定义为 1000）。
4.生成随机数也是本次程序实践的一大突破，为了保证比较执行的时间的方便性，显然让用户一一输入不大现实，固让系统随机生成省去了很多麻烦。如：
srand((unsigned)time(NULL));
for(int i = 0 ;i < size ;i++)
for(int j =0 ; j < 2 ; j++)
{
List[i][j]=(rand()%99)+1; //规定随机生成的数范围是(1,100)
}
其中利用rand()函数随机生成，且定随机生成的数范围是(1,100)。