斐波那契数列

斐波那契数列在数学和生活以及自然界中都非常有用。斐波那契数列最早被提出是印度数学家 Gopala，他在研究箱子包装物件长度恰好为 1 和 2 时的方法数时首先描述了这个数列。也就是这个问题：有 n 个台阶，你每次只能跨一阶或两阶，上楼有几种方法？

最早研究这个数列的当然就是斐波那契（Leonardo Fibonacci）了，他当时是为了描述如下情况的兔子生长数目：

• 第一个月初有一对刚诞生的兔子
• 第二个月之后（第三个月初）它们可以生育
• 每月每对可生育的兔子会诞生下一对新兔子
• 兔子永不死去

斐波那契数列是编程书中讲递归必提的，因为它是按照递归定义的，所以我们就从递归开始讲起。

int Fib(int n)
{
    return n < 2 ? 1 : (Fib(n-1) + Fib(n-2));
}

这是编程最方便的解法，当然，也是效率最低的解法，原因是会出现大量的重复计算。为了避免这种情况，可以采用递推的方式。

int Fib[1000];
Fib[0] = 0;Fib[1] = 1;
for(int i = 2;i < 1000;i++) Fib[i] = Fib[i-1] + Fib[i-2];