計算最大公因數的C++程序

最高公因數或最大公約數是能夠在不產生任何餘數的情況下，能夠同時整除兩個或多個值的因數。在本文中，我們將討論在C 中執行兩個數字的HCF / GCD的幾種方法。

這只是一個數學解決方案，有幾種演算法可以找到最大公約數。歐幾裡得方法是常見的找到最大公約數的方法。我們將在迭代模式和遞歸模式下使用相同的演算法。

使用迭代方法

歐幾里德求最大公約數的迭代解法在演算法部分中展示。

演算法

• 將兩個數a和b作為輸入。
• 如果a等於0，則回傳b。
• 如果 b 為 0，則傳回 a。
• 當a和b不相同時，執行操作。
  • 如果 a > b，則 a := a – b。
  • 否則 b := b - a。
• 結束循環。
• 將最大公因數作為變數 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。

以上是計算最大公因數的C++程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！