Re: [理工] [資結]-台大99-資工所
※ 引述《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)
推
07/05 06:48, , 1F
07/05 06:48, 1F
推
02/09 20:47, , 2F
02/09 20:47, 2F
→
02/09 20:50, , 3F
02/09 20:50, 3F
→
02/09 20:51, , 4F
02/09 20:51, 4F
討論串 (同標題文章)