資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時裝學
法律研究使用遞迴歐幾里得演算法求兩個數的最大公約數的 C++ 程式
兩個數的最大公約數 (GCD) 是能夠同時整除這兩個數的最大數。
例如：假設有兩個數為 63 和 21。
63 = 7 * 3 * 3 21 = 7 * 3
因此，63 和 21 的 GCD 為 21。
遞迴歐幾里得演算法透過使用一對正整數 a 和 b 來計算 GCD，並在 b 為零之前返回 b 和 a%b。
以下是一個使用遞迴歐幾里得演算法求兩個數的 GCD 的程式 −
示例
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}輸出
以上程式的輸出如下 −
Enter the values of a and b: 105 30 GCD of 105 and 30 is 15
在以上程式中，gcd() 是一個遞迴函式。它有兩個引數，即 a 和 b。如果 b 等於 0，則將 a 返回到 main() 函式。否則 gcd() 函式使用 b 和 a%b 的值遞迴呼叫自身。以下程式碼片段演示了這一點 −
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}在 main() 函式中，從使用者請求 a 和 b 的值。然後呼叫 gcd() 函式，並顯示 a 和 b 的 GCD 值。這在下面可見 −
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}
更新於：2020-06-25
5 千次以上瀏覽
廣告