輾轉相除法| C++與演算法

輾轉相除法(Euclidean algorithm) ... 輾轉相除法是歷史上最著名的演算法之一，是求兩數的最大公因數(GCD) 極快速的方法。

... 原理是兩個數字互相減來減去，最後就會剩下構成 ... 課程介紹 0.1. 為什麼要學程式設計? 1. 關於作者 2. 程式是什麼 3. C++入門 3.1. 編輯器Dev-C++ 3.2. 基本架構與輸出 3.2.1. 除法/ 3.2.2. 取餘數% 3.3. 變數 3.3.1. 變數型態與變數宣告 3.3.2. 輸出變數值 3.3.3. 指派變數值 3.3.4. 輸入變數值 3.3.4.1. 題目-我想長高 3.3.4.1.1. 解答 3.3.4.2. 題目-剩多少錢? 3.3.4.2.1. 解答 3.3.4.3. 題目-等我一下 3.3.4.3.1. 解答 3.3.5. 重複輸入 3.3.5.1. 題目-多項式計算 3.3.5.1.1. 解答 3.3.5.2. 題目-哈囉 3.3.5.2.1. 解答 3.3.6. 思考問題：變數交換 3.3.6.1. 解答 3.4. if條件式 3.4.1. if-else條件式 3.5. 條件運算 3.5.1. 關係運算 3.5.1.1. 題目-判斷倍數 3.5.1.1.1. 解答 3.5.2. 邏輯運算 3.5.3. 題目-我能結婚嗎? 3.5.3.1. 解答 3.5.4. 題目-三角形邊長 3.5.4.1. 解答 3.5.5. 題目-上學去吧！ 3.5.5.1. 解答 3.6. 巢狀if 3.7. 迴圈 3.7.1. while迴圈 3.7.2. while與數列 3.7.3. 題目-找出所有因數 3.7.3.1. 解答 3.7.4. 題目-判斷質數 3.7.4.1. 解答 3.7.5. 題目-有幾位數 3.7.5.1. 解答 3.7.6. 跳出迴圈break 3.7.7. 題目-Feynman 3.7.7.1. 解答 3.8. 陣列 3.8.1. 題目-翻轉吧，身高！ 3.8.1.1. 解答 3.8.2. 題目-成績查詢系統 3.8.2.1. 解答 3.8.3. 題目-關注學生 3.8.3.1. 解答 3.8.4. 題目-存存提提 3.8.4.1. 解答 4. 小試身手 4.1. ZeroJudge-兩光法師占卜術 4.1.1. 解答 4.2. UVA-BacktoHighSchoolPhysics 4.2.1. 解答 4.3. 判斷閏年 4.3.1. 解答 4.4. UVA-Zapping 4.4.1. 解答 4.5. UVA-DangerousDive 4.5.1. 解答 4.6. UVA-BoxofBricks 4.6.1. 解答 4.7. ZeroJudge-Sagit's計分程式 4.7.1. 解答 4.8. 質因數分解 4.8.1. 解答 4.9. 3n+1猜想 4.9.1. 測試資料 4.9.2. 解答 4.10. UVA-3n+1 4.10.1. 解答 5. C++基礎 5.1. 單選判斷if-elseif-else 5.2. for迴圈 5.3. 運算式簡寫 5.4. 巢狀迴圈 5.4.1. 題目-直角三角形製造機 5.4.1.1. 解答 5.4.2. 題目-金字塔製造機 5.4.2.1. 解答 5.4.3. 題目-九九乘法表 5.4.3.1. 解答 5.5. 選擇排序法 5.6. 函式 5.6.1. 內建函式 5.6.2. 自訂函式 5.7. 遞迴 5.7.1. 費氏數列 5.7.2. 輾轉相除法 5.8. 文字處理-字元與字串 5.8.1. 字元(char) 5.8.1.1. 跳脫字元 5.8.2. 字串(string) 5.8.3. 文字處理函式 5.9. 貪婪演算法(Greedy) 5.10. 堆疊(stack)資料結構 5.10.1. 題目-小呆的決心 5.10.1.1. 解答 PublishedusingGitBook A A Serif Sans White Sepia Night Twitter Google Facebook Weibo Instapaper C++與演算法 輾轉相除法(Euclideanalgorithm) 輾轉相除法是歷史上最著名的演算法之一，是求兩數的最大公因數(GCD)極快速的方法。

維基百科-輾轉相除法 原理是兩個數字互相減來減去，最後就會剩下構成兩個數字的共通單位，也就是最大公因數。

圖片來源:昌爸工作坊 [輸入說明] 兩個正整數a、b [輸出說明] 兩數的最大公因數 [input] 3410 2030 3020 7296 [output] 2 10 10 24 code1.0-模擬紙上的運算 總是拿較大的數除以較小的數 當其中一數變成0，另外一個數就是最大公因數 #include usingnamespacestd; intmain() { inta,b; while(cin>>a>>b) { while(a!=0andb!=0) { if(a>=b) { a=a%b; } elseif(b>a) { b=b%a; } } if(a>=b) { cout< usingnamespacestd; intmain() { inta,b,t; while(cin>>a>>b) { while(b!=0) { t=b; b=a%b; a=t; } cout< usingnamespacestd; intf(inta,intb) { if(b==0) returna; returnf(b,a%b); } intmain() { inta,b; while(cin>>a>>b) { cout<