文理学院程序设计在线练习


Fibonacci数列

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 416   Accepted Submission(s): 249
Problem Description

无穷数列1, 1, 2, 3, 5, 8,...称为Fibonacci数列,它可以递归地定义为:
F(n)=1(对于n=0,1),F(n)=F(n-1) + F(n-2)(对于n>1)

编程实现求第n项Fibonacci数。

Input

输入有多行,每行为一个测试数据n(n为非负整数)。

Output

对于每个测试数据,输出Fibonacci数列中的第n项(可以认为不会超过32位整数的表示范围)。每个输出1行。

Sample Input
2
4
1
Sample Output
2
5
1