C++練習14：求兩個數的最大公約數gcd
- 題目
- 思路
- 代碼
題目
求兩個不相等正整數的最大公約數gcd
思路
歐幾里得法（輾轉相除法）：歐幾里得演算法又稱輾轉相除法，是指用于計算兩個非負整數a，b的最大公約數，
假如需要求 1997 和 615 兩個正整數的最大公約數,用歐幾里得演算法，是這樣進行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公約數為1
以除數和余數反復做除法運算，當余數為 0 時，取當前算式除數為最大公約數，所以就得出了 1997 和 615 的最大公約數 1，
代碼
#include <iostream>
using namespace std;
int main (){
int a,b,c,re;
cout << "這是一個求兩數最大公約數的程式！" << endl;
cout << "請輸入第一個數字：" ;
cin >> a;
cout << "請輸入第二個數字：" ;
cin >> b;
c = a; // 由于ab大小不確定，此處還做了判斷處理，以保證大資料除以小資料
if(a > b){
a = b;
b = c;
}
re = b % a;
while(re>0){
b = a;
a = re;
re = b % a;
}
cout <<"這兩個數的最大公約數為：" << a;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282619.html
標籤：其他
上一篇：學習筆記-java基礎-網路編程
下一篇：C#常見編碼方式總結