一、问题描述：
运行最大公约数的常用算法
二、问题分析与设计：
1.辗转相除法（又名欧几里德法）
①函数嵌套调用
其算法过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给a；
5、返回第二步；
代码：
#include
using namespace std;
int divisor(int a,int b) //自定义函数求最大公约数
{
int temp; //整形零时变量
if(a { temp=a;a=b;b=temp; } while(b!=0) { temp=a%b; //a中大数除以b中小数循环取余，直到b及余数为0 a=b; b=temp; } return a; //返回最大公约数到调用函数处 } int multipile(int a,int b) //自定义函数求最小公倍数 { int divisor(int a,int b); //自定义函数返回值类型 int temp; temp=divisor(a,b); //再次调用自定义函数，求出最大公约数 return(a*b/temp); //返回最小公倍数到主调函数处进行输出 } int main() { int m,n,t1,t2; printf("请输入两个整形数字："); scanf("%d%d",&m,&n); if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0) { printf("请重新输入正确整数："); cin.clear(); //清除错误标记，重新打开输入流 cin.sync (); scanf("%d%d",&m,&n); } t1=divisor(m,n); t2=multipile(m,n); printf("最大公因数为：%d\n",t1); printf("最小公倍数为：%d\n",t2); return 0; } 测试及测试代码与平均运行时间： 测试代码： #include #include #include int divisor(int a,int b) { int temp; if(a { temp=a;a=b;b=temp; } while(b!=0) { temp=a%b; a=b; b=temp; } return a; } void main() { int m[5000],n[5000],t1,i; clock_t start,finish; double duration; time_t t=time(NULL); srand(t); for(i=0;i<5000;i++) { m[i]=rand()%100; n[i]=rand()%100; } start=clock(); for(i=0;i<5000;i++) { t1=divisor(m[i],n[i]); printf("%d %d %d\n",m[i],n[i],t1); } finish=clock(); duration=(double)(finish-start)/5000; //平均运行时间 printf("%f milliseconds\n",duration); } ②函数递归调用 #include #include using namespace std; int gcd(int a,int b) //自定义函数求最大公约数 { if(a%b==0) //终止条件 return b; //b及为最大公约数 else return gcd(b,a%b); } int main() { int m,n,t1; printf("请输入两个整形数字："); scanf("%d%d",&m,&n); if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0) //判断输入两数字是否小于零或为小数 { printf("请重新输入正确整数："); cin.clear(); //清除错误标记，重新打开输入流 cin.sync (); scanf("%d%d",&m,&n); } t1=gcd(m,n); printf("最大公因数为：%d\n",t1); printf("最小公倍数为：%d\n",m*n/t1); return 0; } 测试及测试代码与平均运行时间： 测试代码： #include #include #include int gcd(int a,int b) { if(a%b==0) return b; else return gcd(b,a%b); } void main() { int m[2000],n[2000],t1,i; clock_t start,finish; double duration; time_t t=time(NULL); srand(t); for(i=0;i<2000;i++) { m[i]=rand()%100; n[i]=rand()%100; } start=clock(); for(i=0;i<2000;i++) { t1=gcd(m[2000],n[2000]); printf("%d %d %d %d\n",m[i],n[i],t1); } finish=clock(); duration=(double)(finish-start)/2000; //平均运行时间 printf("%f seconds\n",duration); } 流程图 2.穷举法（也称枚举法）利用数学定义 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。 定义1：对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。 定义2：对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。 代码： #include using namespace std; 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 multiple(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 main() { int m,n,t1,t2; printf("请输入两个整形数字："); scanf("%d%d",&m,&n); if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0) { printf("请重新输入正确整数："); cin.clear(); //清除错误标记，重新打开输入流 cin.sync (); scanf("%d%d",&m,&n); } t1=divisor(m,n); t2=multiple(m,n); printf("最大公因数为：%d\n",t1); printf("最小公倍数为：%d\n",t2); return 0; } 测试及测试代码与平均运行时间： 测试代码： #include #include #include int divisor(int a,int b) { int temp; temp=(a>b)?b:a; while(temp>0) { if(a%temp==0&&b%temp==0) break; temp--; } return(temp); } void main() { int m[5000],n[5000],t1,i; clock_t start,finish; double duration; time_t t=time(NULL); srand(t); for(i=0;i<5000;i++) { m[i]=rand()%100; n[i]=rand()%100; } start=clock(); for(i=0;i<5000;i++) { t1=divisor(m[i],n[i]); printf("%d %d %d\n",m[i],n[i],t1); } finish=clock(); duration=(double)(finish-start)/5000; //平均运行时间 printf("%f seconds\n",duration); } 流程图 3. 更相减损法 更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法>也叫等值算法。 代码： #include #include using namespace std; int gcd(int m,int n) //求最大公约数 { int i=0,temp,x; while(m%2==0 && n%2==0) //判断m和n能被多少个2整除(i个) { m/=2; n/=2; i+=1; } if(m { temp=m; m=n; n=temp; } while(x) { x=m-n; //{ 以较大的数减较小的数， m=(n>x)?n:x; n=(n if(n==(m-n)) //并以大数减小数。} break; } if(i==0) return n; else return (int )pow(2,i)*n; } int main() { int m,n,t1; printf("请输入两个整形数字："); scanf("%d%d",&m,&n); if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0) //判断输入两数字是否小于零或为小数 { printf("请重新输入正确整数："); cin.clear(); //清除错误标记，重新打开输入流 cin.sync (); scanf("%d%d",&m,&n); } t1=gcd(m,n); printf("最大公因数为：%d\n",t1); printf("最小公倍数为：%d\n",m*n/t1); return 0; } 测试及测试代码与平均运行时间： 测试代码： #include #include #include #include int gcd(int m,int n) //求最大公约数 { int i=0,temp,x; while(m%2==0 && n%2==0) //判断m和n能被多少个2整除(i个) { m/=2; n/=2; i+=1; } if(m { temp=m; m=n; n=temp; } while(x) { x=m-n; //{以较大的数减较小的数， m=(n>x)?n:x; n=(n if(n==(m-n)) //并以大数减小数。} break; } if(i==0) return n; else return (int )pow(2,i)*n; } void main() { int m[2000],n[2000],t1,i; clock_t start,finish; double duration; time_t t=time(NULL); srand(t); for(i=0;i<2000;i++) { m[i]=rand()%100; n[i]=rand()%100; } start=clock(); for(i=0;i<2000;i++) { t1=gcd(m[i],n[i]); printf("%d %d %d\n",m[i],n[i],t1); } finish=clock(); duration=(double)(finish-start)/2000; //平均运行时间 printf("%f seconds\n",duration); } 流程图： 4.Stein算法 Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。来研究一下最大公约数的性质，发现有 gcd( kx,ky ) = kgcd( x,y ) 这么一个非常好的性质。 试取 k=2，则有 gcd( 2x,2y ) = 2 * gcd( x,y )。很快联想到将两个偶数化小的方法。 那么一奇一个偶以及两个奇数的情况如何化小呢？ 先来看看一奇一偶的情况： 设有2x和y两个数，其中y为奇数。因为y的所有约数都是奇数，所以 a = gcd( 2x,y ) 是奇数。 根据2x是个偶数不难联想到，a应该是x的约数。 我们来证明一下： (2x)%a=0，设2x=na，因为a是奇数，2x是偶数，则必有n是偶数。 又因为 x=(n/2)*a，所以 x%a=0，即a是x的约数。 因为a也是y的约数，所以a是x和y的公约数，有 gcd( 2x,y ) <= gcd( x,y )。 因为gcd( x,y )明显是2x和y的公约数，又有gcd( x,y ) <= gcd( 2x,y )， 所以 gcd( 2x,y ) = gcd( x,y )。 至此，我们得出了一奇一偶时化小的方法。 再来看看两个奇数的情况： 设有两个奇数x和y，不妨设x>y，注意到x+y和x-y是两个偶数， 则有gcd( x+y,x-y ) = 2 * gcd( (x+y)/2,(x-y)/2 )， 那么 gcd( x,y ) 与 gcd( x+y,x-y ) 以及 gcd( (x+y)/2,(x-y)/2 ) 之间是不是有某种联系呢？ 为了方便设 m=(x+y)/2 ，n=(x-y)/2 ，容易发现 m+n=x ，m-n=y 。 设 a = gcd( m,n )，则 m%a=0,n%a=0 ， 所以 (m+n)%a=0，(m-n)%a=0 ，即 x%a=0 ，y%a=0 ， 所以a是x和y的公约数，有 gcd( m,n )<= gcd(x,y)。 再设 b = gcd( x,y )肯定为奇数，则 x%b=0,y%b=0 ， 所以 (x+y)%b=0 ，(x-y)%b=0 ， 又因为x+y和x-y都是偶数，跟前面一奇一偶时证明a是x的约数的方法相同， 有 ((x+y)/2)%b=0,((x-y)/2)%b=0 ，即 m%b=0 ，n%b=0 ， 所以b是m和n的公约数，有 gcd( x,y ) <= gcd( m,n )。 所以 gcd( x,y ) = gcd( m,n ) = gcd( (x+y)/2,(x-y)/2 )。 *整理一下，对两个正整数 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 using namespace std; int Stein( unsigned int x, unsigned int y ) //函数非递归调用 { int factor = 0; //返回最大公约数x和y 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 m,n,t1; printf("请输入两个整形数字："); scanf("%d%d",&m,&n); if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0) //判断输入两数字是否小于零或为小数 { printf("请重新输入正确整数："); cin.clear(); //清除错误标记，重新打开输入流 cin.sync (); scanf("%d%d",&m,&n); } t1=Stein(m,n); printf("最大公因数为：%d\n",t1); return 0; } 测试及测试代码与平均运行时间： 测试代码： #include #include #include 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 ); } void main() { int m[2000],n[2000],t1,i; clock_t start,finish; double duration; time_t t=time(NULL); srand(t); for(i=0;i<2000;i++) { m[i]=rand()%100; n[i]=rand()%100; } start=clock(); for(i=0;i<2000;i++) { t1=Stein(m[2000],n[2000]); printf("%d %d %d %d\n",m[i],n[i],t1); } finish=clock(); duration=(double)(finish-start)/20000; //平均运行时间 printf("%f seconds\n",duration); } ②函数递归调用 #include using namespace std; int gcd(int u,int v) { if (u == 0) return v; if (v == 0) return u; // 寻找两个数的最大公约数 if (~u & 1) // u是偶数 { if (v & 1) // v是奇数 return gcd(u >> 1, v); else // u和v都是偶数 return gcd(u >> 1, v >> 1) << 1; } if (~v & 1) // u是奇数, v是偶数 return gcd(u, v >> 1); // 减少较大的变量 if (u > v) return gcd((u - v) >> 1, v); return gcd((v - u) >> 1, u); } int main() { int m,n,t1; printf("请输入两个整形数字："); scanf("%d%d",&m,&n); if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0) //判断输入两数字是否小于零或为小数 { printf("请重新输入正确整数："); cin.clear(); //清除错误标记，重新打开输入流 cin.sync (); scanf("%d%d",&m,&n); } t1=gcd(m,n); printf("最大公因数为：%d\n",t1); return 0; } 测试及测试代码与平均运行时间： 测试代码： #include #include #include int gcd(int u,int v) { if (u == 0) return v; if (v == 0) return u; if (~u & 1) { if (v & 1) return gcd(u >> 1, v); else return gcd(u >> 1, v >> 1) << 1; } if (~v & 1) return gcd(u, v >> 1); if (u > v) return gcd((u - v) >> 1, v); return gcd((v - u) >> 1, u); } void main() { int m[5000],n[5000],t1,i; clock_t start,finish; double duration; time_t t=time(NULL); srand(t); for(i=0;i<5000;i++) { m[i]=rand()%100; n[i]=rand()%100; } start=clock(); for(i=0;i<5000;i++) { t1=gcd(m[i],n[i]); printf("%d %d %d\n",m[i],n[i],t1); } finish=clock(); duration=(double)(finish-start)/5000; //平均运行时间 printf("%f seconds\n",duration); } 流程图：
友情链接：
Copyright © 2022 战国无双-策略国战活动站 All Rights Reserved.