推 hilorrk:簽名檔與標題相互輝映 11/06 03:38
推 Monsoon:恩謝謝!我已經寫出來了~ 11/06 11:53
推 monyen:推~寫得很清楚 11/06 12:45
我們想一想最大公因數要怎麼求……
假設今天我們手上有兩個很大的數字 a 跟 b，
我們很難直接知道這兩個數字的最大公因數是多少，太悲傷了，
但是我們知道一件事，就是 a 和 b 的最大公因數，
會跟 b 和 a%b (餘數)的最大公因數一樣。
這樣有什麼好處？
仔細想一下，我們知道 a%b 一定比 b 小，
所以當我們求 gcd(b, a%b) 來代替 gcd(a, b)，
而數字變小的話，我們就有比較有辦法求出答案是多少，
反正 gcd(a, b) = gcd(b, a%b) 嘛，我們就解 gcd(b, a%b) 就好了。
所以我們是不是可以這樣寫…
int gcd(a, b) {
return gcd(b, a%b) ;
}
看到沒有，我們在 gcd 裡面呼叫 gcd，
利用自己來解自己，而這種自己呼叫自己的模式，就叫做遞迴。
但是光這樣寫還不完整…因為我們並沒有真的去解 gcd 是多少，
我們只是寫出一個關係式，可以把比較困難的問題轉成比較簡單的問題，
但是我們還是要去把那個簡單的問題的解掉。
所以比較完整程式應該是長成這樣……
int gcd(a, b) {
if ( ...... ) {
return ......;
}
return gcd(a, a%b) ;
}
如果 a 跟 b 簡單到我們可以輕鬆解出答案，
那我們就知道 ...... 的地方要寫什麼，
好吧，但是怎樣叫做簡單的問題？多簡單算是簡單？
假設我給你兩個數字，比方說：
(132, 22) 你知道很簡單的算出最大公因數是多少嗎？應該不能。
( 22, 16) 可以嗎？是比較簡單了，但是大概也沒辦法一眼看出來。
( 2, 4) 可以嗎？簡單，2 嘛。
( 5, 40) 可以嗎？簡單，5，智障也會。
(100,200) 可以嗎？100。
( 12, 48) 可以嗎？12 阿，加油好嗎。
我猜看到這你大概有點 idea 那邊那填些什麼，
不確定也沒關係，下去試試看就好了。
+u 吧。
--
To iterate is human, to recurse, divine.
遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.110.111