資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式計算最大公因數
最大公因數（HCF）或最大公約數（GCD）是可以最大程度地整除兩個或多個值的因數，並且不會產生任何餘數。在本文中，我們將討論在 C++ 中計算兩個數字之間 HCF/GCD 的幾種方法。
這僅僅是一個數學解法，並且存在多種演算法可以找到 GCD。用於查詢 GCD 的歐幾里得演算法很常見。我們將使用相同的演算法以迭代模式和遞迴模式。
使用迭代方法
歐幾里得 gcd 查詢演算法的迭代解法在演算法部分顯示。
演算法
- 將兩個數字 a 和 b 作為輸入。
- 如果 a 為 0，則返回 b。
- 如果 b 為 0，則返回 a。
- 當 a 和 b 不相等時，執行以下操作。
- 如果 a > b，則 a := a – b。
- 否則 b := b - a。
- 結束迴圈。
- 返回 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
結論
在解決不同的數學問題時，獲取最大公因數（HCF）或最大公約數（GCD）是一件非常有用的事情。歐幾里得演算法可以用來計算它。相同的方法既可以迭代地應用，也可以遞迴地應用。這裡我們展示了這兩種方法。另一方面，我們可以用最小公倍數（LCM）來計算 GCD/HCF。兩個數字的 GCD 和 LCM 等於這兩個數字的乘積。因此，根據這個原理，如果我們知道 LCM 和這兩個數字的乘積，就可以很容易地計算出 GCD。
更新於: 2023年4月4日
2K+ 瀏覽量
廣告