作者goodseeyou (好看你)
看板Grad-ProbAsk
標題Re: [理工] [資結]-台大99-資工所
時間Sun Jul 4 23:09:06 2010
※ 引述《chen1025 (小陳)》之銘言：
: 今年台大資工程式設計考題的第一題
: 考費氏數列的追蹤
: http://www.lib.ntu.edu.tw/exam/graduate/99/99405.pdf
: 題目問到當執行fib(10)
: 其中fib(10) fib(9)........fib(1)個別呼叫幾次
: 這題各位有比較有效率的算法嗎?
a10 = a9+a8
a9 = a8+a7
....
a3 = a2+a1
a2 = a1+a0
a1 = 1
a0 = 1
f(10) = 1 (沒有人需要呼叫他)
f(9) = 1 (只有a10要呼叫他)
f(8) = f(10) +f(9) (只有a10 跟 a9會呼叫a8 所以算a10,a9被呼叫次數相加 )
f(7) = f(9) + f(8) (同理只有a9跟a8會呼叫a7 所以算a9,a8被呼叫的次數相加)
....
f(2) = f(4)+f(3)
f(1) = f(3)+f(2)
f(0) = f(2)
還是一個費式數列
答案..應該是正確的吧
只是不嚴謹就是了
可惜我考試的時候是..全部畫出來
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.121.38.209
※ 編輯: goodseeyou 來自: 59.121.38.209 (07/04 23:25)
1F：推 chen1025:非常感謝，原來還是一個費氏數列，剛開始看到會嚇到 07/05 06:48
2F：推 koehie:00 01 02 03 04 05 06 07 08 09 10 02/09 20:47
3F：→ koehie:34 55 34 21 13 08 05 03 02 01 01 02/09 20:50
4F：→ koehie:FAB(10) = 89, 呼叫次數 177 02/09 20:51