資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用遞迴查詢最大公約數的C++程式
兩個數的最大公約數（GCD）是同時能整除這兩個數的最大數。
例如：假設我們有以下兩個數：45 和 27
63 = 7 * 3 * 3 42 = 7 * 3 * 2 So, the GCD of 63 and 42 is 21
以下是使用遞迴查詢兩個數的GCD的程式。
示例
#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 = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}輸出
GCD of 63 and 42 is 21
在上面的程式中，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);
}另一種使用遞迴查詢兩個數的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 = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}輸出
GCD of 63 and 42 is 21
在上面的程式中，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);
}
更新於：2020年6月24日
9K+ 次瀏覽
廣告