坑爹的斐波那契——递推
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 100 Accepted Submission(s) : 41
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
用上一题的递归斐波那契代码，输入41 43 45，看看程序要跑多久，再输入80呢
想办法修改函数，看看在求fib(41)的时候，fib(5)被调用了多少次
解决这个问题的一个办法是记忆化，即用一个数组记录某个fib值是否求过，如果已经求得结果，那么直接返回这个值，否则递归求解
对于斐波那契，我们可以用更直接的递推方式求解
我们定义数组fib[]，初始化fib[1] = fib[2] = 1
那么此时我们可以求得fib[3] = fib[2] + fib[1]
继而有可以求得fib[4] = fib[3] + fib[2]
即可以通过for循环，递推求得fib数组
使用递推方式解决此题，求fib(n) , n <= 80
想办法修改函数，看看在求fib(41)的时候，fib(5)被调用了多少次
解决这个问题的一个办法是记忆化，即用一个数组记录某个fib值是否求过，如果已经求得结果，那么直接返回这个值，否则递归求解
对于斐波那契，我们可以用更直接的递推方式求解
我们定义数组fib[]，初始化fib[1] = fib[2] = 1
那么此时我们可以求得fib[3] = fib[2] + fib[1]
继而有可以求得fib[4] = fib[3] + fib[2]
即可以通过for循环，递推求得fib数组
使用递推方式解决此题，求fib(n) , n <= 80
Input
输出包含多组数据，每组数据包含一个正整数n，不超过80
Output
对于每组数据，输出fib(n)
Sample Input
1 3 5 7
Sample Output
1 2 5 13