最高公因数或最大公约数是能够在不产生任何余数的情况下，能够同时整除两个或多个值的因数。在本文中，我们将讨论在C++中执行两个数字的HCF / GCD的几种方法。
这只是一个数学解决方案，有几种算法可以找到最大公约数。欧几里得方法是常见的找到最大公约数的方法。我们将在迭代模式和递归模式下使用相同的算法。
使用迭代方法
欧几里德求最大公约数的迭代解法在算法部分中展示。
算法
将两个数a和b作为输入。如果a等于0，则返回b。如果 b 为 0，则返回 a。当a和b不相同时，执行操作。如果 a > b，则 a := a – b。否则 b := b – a。结束循环。将最大公因数作为变量 a 返回。
示例
#include 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: 12HCF of two numbers 18 and 13 is: 1HCF of two numbers 117 and 96 is: 3HCF of two numbers 85 and 15 is: 5
使用迭代方法
可以使用递归方法来实现相同的欧几里得方法。下面我们将描述递归方法的定义，如下所示的算法。
立即学习“C++免费学习笔记（深入）”；
算法
定义一个名为HCF的函数，该函数接受两个数字a和b。如果a为0，则返回b否则返回 HCF( b mod a, a)
示例
#include 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: 12HCF of two numbers 18 and 13 is: 1HCF of two numbers 117 and 96 is: 3HCF of two numbers 85 and 15 is: 5
结论
在解决不同数学问题时，求最大公因数或最大公约数是非常有用的。可以使用欧几里得方法来计算。这个方法可以迭代地应用，也可以递归地应用。这里我们展示了两种方法。另一方面，我们可以通过最小公倍数（LCM）来计算GCD/HCF。两个数的GCD和LCM与这两个数的乘积相同。因此，根据这个原理，如果我们知道这两个数的LCM和乘积，就可以很容易地计算出GCD。
以上就是计算最大公因数的C++程序的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445442.html
微信扫一扫 
支付宝扫一扫 
