C++求最大公约数四种方法解析
时光zz 人气:3本文着重为大家仔细讲解了C++求最大公约数四种方法,文中代码实例讲解的非常细致,希望能够帮助到您,欢迎大家阅读和收藏
C++求最大公约数的四种方法思路,供大家参考,具体内容如下
将最近学的求最大公约数的四种方法总结如下:
第一种:穷举法之一
解释:拿其中一个数出来,用一个临时变量(tem)保存,每次都把那两个数除以这个临时变量。如果能除断,直接返回tem;如果不能除断,tem- -,直到都能除断,再返回tem。tem就是它们的最大公约数。
#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; }
第二种:穷举法之二
解释:求出两数的所有公因子,再把公因子累乘得到最大公约数。
#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。(具体思想请问度娘)
#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; }
第四种:辗转相减法
解释:将两个数辗转相减直到两数相等。(具体思想请问度娘)
#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; }
加载全部内容