大家好，又见面了，我是你们的朋友全栈君。
一、题目要求
利用辗转相除法、穷举法、更相减损术、Stein算法求出两个数的最大公约数或者/和最小公倍数。
最大公约数：指两个或多个整数共有约数中最大的一个。
例如：【12和24】12的约数有：1、2、3、4、6、12；24的约数有：1、2、3、4、6、8、12、24。它们共有的约数为：1、2、3、4、6、12，则12和24的最大公约数为12
最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。
例如：【3和4】3的倍数有6、9、12、15、18、21、24……；4的倍数有4、8、12、16、20、24……。它们公有的倍数有12、24……，则3和4的最小公倍数为12
运行时间：求每个函数运行时间，进行比较获得最长及最短平均运行时间。
二、算法构建
【辗转相除法】
具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
实质上是以下式子：
根据这一定理可以采用函数嵌套调用和递归调用进行求两个数的最大公约数和最小公倍数,现分别叙述如下：
①函数嵌套调用
求最大公约数：
其算法过程为：设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给b；
5、返回第二步；
求最小公倍数：
一个简单的方法直接求：a*b/最大公约数
//辗转相除法函数嵌套求两数的最大公约数
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; //返回最大公约数到调用函数处
}
//辗转相除法函数嵌套求两数的最小公倍数
int multiple (int a,int b)
{
int divisor (int a,int b);
int temp;
temp=divisor(a,b); //再次调用自定义函数，求出最大公约数
return (a*b/temp); //返回最小公倍数到主调函数处进行输出
}②函数递归调用
int gcd_1 (int a,int b)
{
if(a%b==0)
return b;
else
return gcd_1(b,a%b);
}【流程图】
ps：在此仅给出辗转相除法函数嵌套的流程图，如果需要其余算法的流程图可以下载：流程图下载
【n-s盒图】
ps：在此仅给出辗转相除法函数嵌套的n-s盒图，如果需要其余算法的图可以下载n-s盒图：
【穷举法】
穷举法（也叫枚举法）的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。若某个情况验证符合题目的全部条件，则为本问题的一个解；若全部情况验证后都不符合题目的全部条件，则本题无解。
解题思想：从两个数中较小数开始由大到小列举约数，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。
解题步骤：
1、求最大公约数
对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
2、求最小公倍数
对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。
//穷举法求两数的最大公约数
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;
}
【更相减损术】
更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
解题步骤：
1、任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行2。
2、以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则1中约掉的若干个2与2中等数的乘积就是所求的最大公约数。
//更相减损术求最大公约数
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算法】
Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。来研究一下最大公约数的性质，发现有 gcd( k*x,k*y ) = k*gcd( 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=n*a，因为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 )；
3、x奇y偶 gcd( x,y ) = gcd( x,y/2 )；
4、x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 )；
现在已经有了递归式，还需要再找出一个退化情况。注意到 gcd( x,x ) = x ，就用这个。
//Stein算法非递归调用求最大公约数
int Stein(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 ){
if ( x & 0x1 ){ //x为奇数
if ( y & 0x1 ){ //x和y都为奇数
y = ( x - y ) >> 1;
x -= y;
}
else{ //x为奇数y为偶数
y >>= 1;
}
}
else{ //x为偶数
if ( y & 0x1 ){ //x为偶数y为奇数
x >>= 1;
if ( x < y ){
temp = x;
x = y;
y = temp;
}
}
else{ //x和y都为偶数
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;
//找2的因素
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);
}三、算法运行时间
记录每次运行并乘以一个很大的数（因为一次运行时间极短接近于0）。
头文件：
#include <windows.h>代码部分：
//求辗转相除法函数嵌套算法运行时间
float run_time_1;
_LARGE_INTEGER time_start; //算法开始时间
_LARGE_INTEGER time_over; //算法结束时间
double dqFreq; //计时器频率
LARGE_INTEGER f; //计时器频率
QueryPerformanceFrequency(&f);
dqFreq=(double)f.QuadPart;
int s=100000; //运行次数以记录每次运行时间
QueryPerformanceCounter(&time_start); //计时开始
while(s--)
t1=divisor_1(m,n); //辗转相除法函数嵌套求最大公约数 此处写运行函数
QueryPerformanceCounter(&time_over); //计时结束
run_time_1=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq; //乘以 1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
printf("辗转相除法函数嵌套求最大公约数函数平均运行时间为：%fus\n\n",run_time_1);四、心得体会及源码
整个程序的源代码请见：百度网盘-链接不存在 提取码：h353 ，可能提示格式无法显示，直接下载就可以了，cpp格式的
中途遇到的最大问题可能就是运行时间了吧，一开始跑出来总是零，后面经过大佬的提醒才想到可以通过乘以一个很大的数来转换，因此也解决了问题XDDD
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/145217.html原文链接：https://javaforall.net
