求两个数的最大公约数（C++）
一.算法构造
1.辗转相除法
设两数为a,b设其中a 做被除数,b做除数，temp为余数
①大数放a中、小数放b中；
②求a/b的余数；temp=a%b
③、若temp=0则b为最大公约数；
④、如果temp!=0则把b的值给a、temp的值给b；
⑤、返回第二步；
流程图
2.枚举法
设两个数为a,b
①比较两个数的大小
②. 把较小的数从大到小列举
③在2过程中找到可以同时被a,b整除的数，则这个数为最大公约数
流程图
3.更相减损法
①.：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
②：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
③.第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
流程图
4.Stein算法
整体上就是把整数化小对两个正整数 x>y ：
①均为偶数 gcd( x,y ) =2gcd( x/2,y/2 )；
② 均为奇数 gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 )；
③.x奇y偶 gcd( x,y ) = gcd( x,y/2 )；
④.x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 )；
流程图
二.源代码
#include<iostream>#include<ctime>#include<cmath>using namespace std;//辗转相除法int gcd1(int a,int b){ int temp; if(a==0||b==0) return 0; if(a<b) { temp=a;a=b;b=temp;} //求最小值最大值，大的用a表示，小的用b表示 while(b!=0) //用循环求最大公约数 { temp=a%b; a=b; b=temp; } return a; //返回最大公约数}//枚举法int gcd2(int a,int b) { int temp; temp=(a>b)?b:a; //求两数中的最小数 while(temp>0) //最小数自减，直到可以同时被a,b整除 { if (a%temp==0&&b%temp==0) break; temp--; } return temp; //返回最大公约数}//更相减损法int gcd3(int a,int b){ int i=0,temp,x; if(a==0||b==0) return 0; if(a==b) return a; while(a%2==0&&b%2==0)//a,b可以被2整除的情况 { a/=2; b/=2; i+=1; //计算被2整除的次数 } if(a<b) //求两数的最大值最小值，a存大值，b存小值 { temp=a; a=b; b=temp; } while(x) { x=a-b; a=(b>x)?b:x; b=(b<x)?b:x; if(b==(a-b)) break; } if(i==0) return b; else return(int)pow(2,i)*b;//用<cmath>库的pow()函数求2^i，返回最大公约数 }//Stein算法int gcd4(unsigned int x,unsigned int y) { int factor=0; int temp; if(x<y) { temp=x; x=y; y=temp; } if(0==y) { return 0; } while(x!=y) { //当x时偶数时 if(x&0x1) { if(y&0x1) { //当x和y都是偶数时 y=(x-y)>>1; x-=y; } else { //当x是偶数，y是奇数 y>>=1;//移位运算 } } else { //当x是奇数 if(y&0x1) { x>>=1; if(x<y) { temp=x; x=y; y=temp; } } else { //当x和y都是奇数 x>>=1; y>>=1; ++factor; } } } return (x<<factor); } int main(){ int a,b,c,i,j; double dur; int row; int col=2;//用动态数组来实现行的输入 cout<<"输入二维数组的行(列默认为2):"; cin>>row; int **p2 ; p2 = new int*[row] ; for(i=0;i<row;i++) p2[i]=new int[col] ; //输入二维数组的值 for(i=0;i<row;i++) for(j=0;j<col;j++) p2[i][j]=rand()%20;//会生成伪随机数，每次随机出现的数都一样，适合本实验的时间比较//输出随机生成的二维数组 cout<<"输出二位数组:"<<endl; for( i=0;i<row;i++) { for(j=0;j<col;j++) cout<<p2[i][j]<<' ' ; cout<<endl; }//界面设置 cout<<"###############选择辗转相除法，请输入0################"<<endl; cout<<"###############选择穷举法，请输入1####################"<<endl; cout<<"###############选择更相减损法，请输入2################"<<endl; cout<<"###############选择stein算法，请输入3#################"<<endl; cout<<"请输入你想选择的方法:"; cin>>c; if(c<0||c>4) { cout<<"输入正确的数"<<endl; exit(0); } clock_t start,end; start=clock(); for(int k=0;k<row;k++) { //cout<<"请输入两个整数:"; //cin>>a>>b; switch(c) { case 0: cout<<"最大公约数为:"<<gcd1(p2[k][0],p2[k][1])<<endl;break; case 1: cout<<"最大公约数为:"<<gcd2(p2[k][0],p2[k][1])<<endl;break; case 2: cout<<"最大公约数为:"<<gcd3(p2[k][0],p2[k][1])<<endl;break; case 3: cout<<"最大公约数为:"<<gcd4(p2[k][0],p2[k][1])<<endl;break; } } end=clock(); dur=(double)(end-start); cout<<"时间为:"<<(dur/CLOCKS_PER_SEC)<<"s"<<endl; for(i=0;i<row;i++) delete []p2[i] ; delete []p2 ;}
三.运行结果
四.实验总结
这次实验让我掌握了很多知识，了解了四种求最大公约数的方法，尤其最后一种算法，对我讲比较难理解，花费了很长时间来理解代码的含义。在写代码的时候也遇到了各种各样的问题，第一个是计时函数的应用，因为之前也没有了解过语言的各种函数用法，做起来也比较吃力，也在网上，书上找了很多关于计时函数的用法，但是在实际过程中还是有很多错误，出现各种问题，时间输不出来，或者为负数等。第二个是要输入20组或50组数来比较四种方法的可行性，用随机数生成函数来实现，rand()函数生成的随机数都是伪随机数，方便了这次测试。还使用动态数组来自己输入二维数组行的大小，更方便一些。第三:这次实验也提高了一点我的编程能力，分析问题的能力，逻辑思维能力，除了这些还要认真阅读题目，理解题目，这次把20组数的测试想成了求20个数的最大公约数，在正确的道路上越来越远。第四:这次编程也让我知道我的编程能力很差，不知道的知识还很多，还是要多看书，多查资料。代码中出现的pow()函数，也是第一次了解，以后也要多了解一些常用的库函数。
五.流程图
枚举法
更相减损法
stein算法