C++ 程序计算最大公因数
c++server side programmingprogramming更新于 2024/10/10 16:36:00
最大公因数或最大公约数是最大的因数，它们可以除以两个或多个值而不产生任何余数。在本文中，我们将讨论在 C++ 中执行两个数字之间的 HCF/GCD 的几种方法。
这只是一个数学解决方案，有几种算法可以找到 GCD。欧几里得方法找到 GCD 很常见。我们将在迭代模式和递归模式下使用相同的算法。
使用迭代方法
欧几里得 gcd 查找算法的迭代解决方案显示在算法部分中。
算法
- 以两个数字 a 和 b 作为输入。
- 如果 a 为 0，则返回 b。
- 如果 b 为 0，则返回 a。
- 当 a 和 b 不相同时，执行。
- 如果 a > b，则 a := a – b。
- 否则 b := b - a。
- 结束 While。
- 将 HCF 返回为变量 a。
示例
#include <iostream> using namespace std; int solve( int x, int y) { if (x == 0) return y; else if (y == 0) return x; while (x != y) { if (x > y) x = x - y; else y = y - x; } return x; } int main( int argc, char* argv[] ) { cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl; cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) << endl; cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl; cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl; }
输出
HCF of two numbers 12 and 72 is: 12 HCF of two numbers 18 and 13 is: 1 HCF of two numbers 117 and 96 is: 3 HCF of two numbers 85 and 15 is: 5
使用迭代方法
可以使用递归方法实现相同的欧几里得方法。下面我们在以下算法中描述递归方法的定义。
算法
- 定义一个函数 HCF，该函数接受两个数字 a 和 b。
- 如果 a 为 0，则返回 b
- 否则返回 HCF( b mod a, a)
示例
#include <iostream> using namespace std; int solve( int x, int y) { if (x == 0) return y; return solve( y % x, x ); } int main( int argc, char* argv[] ) { cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl; cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) << endl; cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl; cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl; }
输出
HCF of two numbers 12 and 72 is: 12 HCF of two numbers 18 and 13 is: 1 HCF of two numbers 117 and 96 is: 3 HCF of two numbers 85 and 15 is: 5
结论
在解决不同的数学问题时，获得最大公因数或最大公因数是非常有用的。可以使用欧几里得方法来计算。相同的方法可以迭代和递归应用。这里我们展示了它们两者。另一方面，我们可以用最小公倍数 (LCM) 计算 GCD/HCF。两个数字的 GCD 和 LCM 与这两个数字的乘积相同。因此，根据该原理，如果我们知道 LCM 和这两个数字的乘积，就可以轻松计算出 GCD。
