作者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