[問題] 遞迴寫最大公因數

看板C_and_CPP作者 (Formosa)時間9年前 (2014/11/13 11:00), 編輯推噓4(4推 0噓 8→)
留言12則, 10人參與, 最新討論串1/1
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) C 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 問題(Question)： 第一次發文就是來問剛剛期中考的題目 跪求各位大大了 很想知道 用遞迴寫最大公因數 餵入的資料(Input)： 預期的正確結果(Expected Output)： 錯誤結果(Wrong Output)： 程式碼(Code)：(請善用置底文網頁, 記得排版) int gcd(int a ,int b)｛｝ 補充說明(Supplement)： 目前想到用輾轉相除法去解但想不到怎麼變程式碼 -- Sent from my Android -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.249.192.21 ※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1415847614.A.A8F.html
→
11/13 11:08, , 1F
想一想輾轉相除法每一步裡面有做什麼
11/13 11:08, 1F
→
11/13 11:11, , 2F
餘數嗎？
11/13 11:11, 2F
推
11/13 13:15, , 3F
輾轉相除法啊
11/13 13:15, 3F
推
11/13 13:36, , 4F
設a>b 則gcd(a,b)=gcd(b,a mod b) 再想最後一步要怎麼做
11/13 13:36, 4F
→
11/14 03:08, , 5F
不然最基本方法，先分別把因數求出來，然後用兩個for
11/14 03:08, 5F
→
11/14 03:09, , 6F
去比對公因數，這樣就可以做出來了，只是比較慢而已
11/14 03:09, 6F
→
11/14 10:40, , 7F
用手推導輾轉相除法 一一對應到程式碼就可以收工了
11/14 10:40, 7F
→
11/14 11:02, , 8F
return a>b?gcd(b,a mod b):gcd(a,b mod a)
11/14 11:02, 8F
→
11/14 11:02, , 9F
結果就無窮迴圈了X
11/14 11:02, 9F
推
11/15 06:14, , 10F
return(a%b)?gcd(b,a%b):b;
11/15 06:14, 10F
→
11/16 15:29, , 11F
11/16 15:29, 11F
推
11/23 18:39, , 12F
把輾轉相除法用筆做一次 就寫出來了
11/23 18:39, 12F
‣ 更多 pilor 的文章
文章代碼(AID): #1KP1w-gF (C_and_CPP)