|
本人最近学习了三种求解两个数最大公因数的方法，第一种是辗转相除法，第二种是相减法，第三种是穷举法
方法一：辗转相除法：
首先判断m是否小于n，不然交换两个值，始终保持m永远是最大的值，求余d=m%n,判断余数是否为0如过为0，则最大公因数为n，否则m=n;n=d;接着求余直到余数d为0，此时最大公因数为n。
方法二：相减法：
如果m,n相等，最大公因数为两个数的任何一个，否则当m>n时，m=m-n，n>m时，n=n-m，一直减到m=n时输出max等于m,n两个数任何一个。
方法三：穷举法
首先保持第一个数为最大的值否则交换两个值，令i=m，开始递减，直到m和n同时除以i为0，此时输出最大公因数为max=i。
大家可以根据我的思路敲一边，不会了再看代码，哪里出错了，再寻找解决的方法，大家一起提高，一起学习。
下面有编程代码，和运行结果可以参考。
//2017年3月18日
//西安科技大学
//软工1503班
#include<iostream>
using namespace std;
class Calculate//建立一个类
{
private:
int m;
int n;
int temp; //用于两数转换
int d; //余数
int max; //最大公因数
int min; //最小公倍数
int product; //m和n的乘积
public:
void MAX_common1(); //最大公因数算法1
void MAX_common2(); //最大公因数算法2
void MAX_common3(); //最大公因数算法3
void MIN_multiple(); //最小公倍数
void cycle(); //选择方法循环
};
void Calculate::MAX_common1()//辗转相除法
{
cout<<"请输入你需要计算的两个数：(x x)"<<endl;
cin>>m>>n;
product=m*n;
if(m<n)//交换数值永远保持m是最大的值
{
temp=m;
m=n;
n=temp;
};
d=m%n; //求余
if(d==0) //
max=n;
else
while(d!=0)//直到余数为0
{
m=n;
n=d;
d=m%n;
max=n;
};
min=product/max;
cout<<"最大公因数为："<<max<<endl;
cout<<"最小公倍数为："<<min<<endl;
}
void Calculate ::MAX_common2() //相减法
{
cout<<"请输入你需要计算的两个数：(x x)"<<endl;
cin>>m>>n;
product=m*n;
while(m!=n) //大数减小数
{
if(m>n)
m=m-n;
else
n=n-m;
}
max=n;
min=product/max;
cout<<"最大公因数为："<<max<<endl;
cout<<"最小公倍数为："<<min<<endl;
}
void Calculate::MAX_common3()//穷举法
{
int i;
cout<<"请输入你需要计算的两个数：(x x)"<<endl;
cin>>m>>n;
product=m*n;
if(m<n) //保持m永远为最大的数
{
temp=m;
m=n;
n=temp;
};
for(i=m;i>1;i--) //从输入的最大一个数开始逐渐递减寻找一个数能被两个数同时整数的
{
if(m%i==0 && n%i==0)
break;
}
max=i;
min=product/max;
cout<<"最大公因数为："<<max<<endl;
cout<<"最大公倍数为："<<min<<endl;
}
void cycle()
{
int Q;
Calculate c;
cout<<"1.方法一（辗转相输法）"<<endl;
cout<<"2.方法二（相减法）"<<endl;
cout<<"3.方法三（穷举法）"<<endl;
cout<<"4. 退出本程序"<<endl;
cout<<"请选择你需要使用的方法：";
cin>>Q;
switch(Q)
{
case 1:
c.MAX_common1();cycle();
break;
case 2:
c.MAX_common2();cycle();
break;
case 3:
c.MAX_common3();cycle();
break;
case 4:
getchar();
}
}
void main()
{
int Q;
Calculate c;
cout<<"1.方法一（辗转相输法）"<<endl;
cout<<"2.方法二（相减法）"<<endl;
cout<<"3.方法三（穷举法）"<<endl;
cout<<"4. 退出本程序"<<endl;
cout<<"请选择你需要使用的方法：";
cin>>Q;
switch(Q)
{
case 1:
c.MAX_common1();cycle();
break;
case 2:
c.MAX_common2();cycle();
break;
case 3:
c.MAX_common3();cycle();
break;
case 4:
getchar();
}
}
| 
转播
