資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式查詢最大公約數
兩個數的最大公約數 (GCD) 是可以同時整除這兩個數的最大數。
例如：假設我們有兩個數 45 和 27。
45 = 5 * 3 * 3 27 = 3 * 3 * 3
那麼，45 和 27 的最大公約數是 9。
查詢兩個數的最大公約數的程式如下所示。
示例
#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 = 105, b = 30;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}輸出
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);
}另一個查詢兩個數的最大公約數的程式如下所示：
示例
#include<iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
}
int main() {
int a = 105, b =30;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}輸出
GCD of 105 and 30 is 15
在上面的程式中，gcd() 是一個遞迴函式。它有兩個引數，即 a 和 b。如果 a 或 b 為 0，則函式返回 0。如果 a 或 b 相等，則函式返回 a。如果 a 大於 b，則函式會使用 a-b 和 b 的值遞迴呼叫自身。如果 b 大於 a，則函式會使用 a 和 (b - a) 的值遞迴呼叫自身。這由以下程式碼片段演示。
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a - b, b);
else return gcd(a, b - a);
}
更新於： 2020年6月24日
14K+ 瀏覽量
廣告