作者LPH66 (f0VMRgEBA)
看板C_and_CPP
標題Re: [問題] 關於遞迴加快速度的迷思？
時間Fri Sep 6 10:00:22 2013
: → s3748679:(頭暈.. 會不會有點太不直覺了?) 09/05 23:36
: → LPH66:其實不會喔 你可以想一想最大公因數(歐幾里得算法)的遞迴版 09/05 23:37
: → LPH66:它的型式跟這篇的 fibb 非常之像 09/05 23:37
: → LPH66:(雖然計算方向上是一個向上一個向下就是了 XD) 09/05 23:38
: 推 s3748679:圖解了下運算過程.. : http://ppt.cc/xhYp 09/06 00:07
: → s3748679:從計算過程上來看 fibb 已經不是遞迴關係式了說 09/06 00:10
: → s3748679:反而比較像是用程式語言的遞迴程序(函數)實現遞迴關係式 09/06 00:11
: → s3748679:的計算過程~ (心得) 09/06 00:13
: → s3748679:咳咳.. 補一下: 所以才會覺得不太直覺就是了~ 09/06 00:14
: → drm343:尾遞迴基本上需要計算參數，所以才讓樓上覺得不像遞迴吧， 09/06 00:24
: → Feis:改法是有規律的，是DP常見手法 09/06 00:35
: → Feis:就是把要記憶的快取空間壓縮後放在參數，迴圈則是放在區域變 09/06 00:51
: 推 xvid:在函式引數寫賦值 第一次看到這種寫法... 09/06 01:25
: 推 ck574b027:參數預設值啊，比 overload 有用 09/06 01:43
: 推 descent:s3748679: 圖解真清楚 09/06 08:14
: 推 adrianshum:給個讚。我自己太笨了，被原本的遞迴限制了想法 09/06 09:05
我還是覺得這個寫法可以拿來跟 GCD 類比...
int fibb(int n, int a = 1, int b = 0) int GCD(int a, int b)
{ {
if(n <= 0) if(b == 0)
return a; return a;
else else
return fibb(n-1, a+b, a); return GCD(b,a%b);
} }
這種寫法的費氏數列似乎可以解釋成
"以 [-1]=b,[0]=a 開始的費氏數列第 n 項
即為 [-1]=a,[0]=a+b 開始的費氏數列第 n-1 項"
雖然有點像在模仿 GCD 的 "GCD(a,b) = GCD(b,a%b)"
不過確實是另一條思路...
--
'Oh, Harry, don't you
see?' Hermione breathed. 'If she could have done
one thing to make
absolutely sure that every single person in this school
will read your interview, it was
banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.69.49.38
推 yvb:gcd() 的終止條件似乎有問題... 09/06 10:31
→ LPH66:啊囧, 我改一下 @@ 有點久沒寫所以記錯了... 09/06 10:55
※ 編輯: LPH66 來自: 210.69.49.38 (09/06 10:55)
推 s3748679:@@".. (一整個沒有想到這樣類比的說) 09/06 11:50
→ s3748679:剛弄了老半天 發現 a(n, a0, a1) = a(n-1, a1, a0+a1) 這 09/06 11:53