Problem1033--斐波那契数列Fibonacci问题

1033: 斐波那契数列Fibonacci问题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2846  Solved: 1473
[Submit] [Status] [Web Board] [Creator:]

Description

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。
现在请你编程计算一下这个数列
已知 f(0) = f(1) = 1, f(n) = f(n - 1) + f(n - 2) (n ≥ 2)。
现在给定一个数 n, 请求出 f(n) 。

Input

输入第一行包含一个正整数 T, 表示数据的组数。
之后 T 行,每行一个正整数 n 。
保证 1 ≤ T ≤ 1000, 1 ≤ n ≤ 40。
此题如果超时可以看看提示信息

Output

对于每个输入,输出一行一个数,表示 f(n)。

Sample Input

4
1
2
3
4

Sample Output

1
2
3
5

HINT

递归运算算法虽然简单,但很消耗时间,有些属于重复计算,可以考虑如何优化递归算法,例如利用全局变量来存储一些计算过的f(n),一定可以提高运算速度。
注意以下文章代码都不是python自己改成python的
斐波那契数列的各种优化:尾递归(递归不爆栈),记忆化搜索,动态规划 - YY-帆S的博客 - CSDN博客 
https://blog.csdn.net/u010365335/article/details/86408252

白话算法-递归算法以及斐波那契数列递归优化算法 - Howzit - CSDN博客 
 https://blog.csdn.net/c_he_n/article/details/83053746
斐波那契数—递归方法的优化 - YGLeeeon的博客 - CSDN博客 
 https://blog.csdn.net/YGLeeeon/article/details/101792084
斐波那契数列 --- 四层优化 - zkfopen - 博客园 
 https://www.cnblogs.com/zkfopen/p/11245857.html
斐波那契数列_百度百科 
https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin

 

Source/Category


[Submit] [Status]