什么是费波那契级数

费波那契数的递回展开
输入档: fib.in / 输出档: fib.out
费波那契数是一种数学级数,我们定义此级数:
前十个费波那契数f(0)~f(9) 分别是1, 1, 2, 3, 5, 8, 13, 21, 34, 55.
而费波那契数的计算常常是递回演算中的基础应用练习题,以下是一段简单的费波那契数递回函式(用c语言来表示).
int fibonacci(int n) {
if(n<=1) return 1;
else return fibonacci(n-2)+fibonacci(n-1);
}
我们来看看呼叫 fibonacci(4)的递回展开(以下简称f(4))的情形,来分析递回计算费波那契数所需要呼叫函数的次数.
由上图可以发现,由於递回展开常常要计算已计算过的费波那契数,因此需要呼叫函数的次数会成长的很快.上图中可见f(4)一共呼叫了9次函数,而其他例如:
f(0), f(1), f(2), f(3) 分别呼叫了1, 1, 3, 5次函数.
这个题目所要问的就是,给定1数字n,找出利用递回展开解fibonacci(n) 所需递回呼叫函数的次数.
输入档说明
测试资料的开头有1个数字n,接下来一共有n行,每1行1个数字(a1, a2, a3,…, an), (0 a1, a2, a3,…., an 45) 表示欲计算的费波那契数.
输出档说明
对於每1个数字,输出递回展开该数,所需递回呼叫函数的次数.

费波那契是一个伟大的数学家。费波那契数列就是

1、1、2、3、5、8、13、21、34、55、89、144、233...

其规律是从第3项起，每一项都是前两项之和，
比如：
2＝1+1
3＝2+1
5＝2+3
8＝3+5

该数列有许多有趣的性质，

在自然界中，也可以找到许多天然生成的数字序列．例如松树球果，果鳞的排列呈螺旋状，数一数各螺旋线上果鳞的数目，你会发现非常类似于费波那契数列．向日葵花冠中的种子也是排成螺旋状，各螺旋线上的种子