C++求最大公约数的四种方法思路,供大家参考,具体内容如下
将最近学的求最大公约数的四种方法总结如下:
第一种:穷举法之一
解释:拿其中一个数出来,用一个临时变量(tem)保存,每次都把那两个数除以这个临时变量。如果能除断,直接返回tem;如果不能除断,tem- -,直到都能除断,再返回tem。tem就是它们的最大公约数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>
using namespace std;
int CommFactor1( int m, int n); //函数的声明
int main()
{
int a, b;
cin >> a >> b;
cout << "这两个数的最大公约数为:" << CommFactor1(a,b)<< endl;
return 0;
}
int CommFactor1( int m, int n)
{
int tem;
for (tem = m;; tem--)
{
if (m % tem == 0 && n % tem == 0)
{
break ;
}
}
return tem;
}
|
第二种:穷举法之二
解释:求出两数的所有公因子,再把公因子累乘得到最大公约数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <iostream>
using namespace std;
int CommFactor2( int m, int n); //函数的声明
int main()
{
int a, b;
cin >> a >> b;
cout << "这两个数的最大公约数为:" << CommFactor2(a,b)<< endl;
return 0;
}
int CommFactor2( int m, int n)
{
int i;
int factor = 1;
for (i=2;i<=m&&i<<n;i++)
{
while (m % i == 0 && n % i == 0) //这里不能用if语句,因为可能会有重复的公因子
{
factor = factor * i;
m = m / i;
n = n / i;
}
}
return factor;
}
|
第三种:辗转相除法
解释:将两个数辗转相除直到余数为0。(具体思想请问度娘)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>
using namespace std;
int CommFactor3( int m, int n); //函数的声明
int main()
{
int a, b;
cin >> a >> b;
cout << "这两个数的最大公约数为:" << CommFactor2(a,b)<< endl;
return 0;
}
int CommFactor3( int m, int n)
{
int z = n;
while (m % n != 0)
{
z = m % n;
m = n;
n = z;
}
return z;
}
|
第四种:辗转相减法
解释:将两个数辗转相减直到两数相等。(具体思想请问度娘)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include <iostream>
using namespace std;
int CommFactor4( int m, int n); //函数的声明
int main()
{
int a, b;
cin >> a >> b;
cout << "这两个数的最大公约数为:" << CommFactor4(a,b)<< endl;
return 0;
}
int CommFactor4( int m, int n)
{
while (m != n)
{
if (m > n)
{
m = m - n;
}
else
{
n = n - m;
}
}
return m;
}
|
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/qq_46459874/article/details/108628942