3051: 05-13-C03-兔子问题—Fibonacci数列(1)(L4)

# 05-13-C03-兔子问题—Fibonacci数列(1)(L4) ## 题目背景 意大利数学家斐波那契(Fibonacci)在他的名著《算法之书》(1202年)提出了一个问题：假设一对刚出生的小兔一个月后就能长成大兔，再过一个月就能生下一对小兔，并且此后每个月都生下一对小兔，一年内没有发生死亡，那么一对刚出生的兔子，在一年内繁殖成多少对兔子？由该繁衍规律得到的每个月兔子的数量组成了斐波那契数列，因此也称为“兔子数列”，如下图所示。 Fibonacci数列增长速度非常快。发生在18世纪中期的澳大利亚野兔成灾的故事体现了真实版的“兔子数列”惊人的增长速度。当时英国殖民者为了满足自己的狩猎爱好把欧洲野兔引进了澳大利亚，由于澳大利亚气候温暖、牧草丰富，为兔子提供了良好的生存条件，加上澳大利亚本土缺乏猛禽、黄鼠狼等兔子的天敌，兔子开启了斐波那契数列式的增长，当时澳大利亚的生态遭到了严重破坏，继而开始了人兔大战……  图 Fibonacci兔子 Fibonacci数列的前几项为：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89。仔细观察这个数列发现，第1项和第2项为1，此后每一项都是前2项的和。 ## 题目描述 输入n值，输出Fibonacci数列第n项，该数列前5项为1, 1, 2, 3, 5。 ## 输入格式 输入占一行，为n的值，1≤n≤40。 ## 输出格式 输出占一行。为Fibonacci数列第n项的值。 ## 样例 #1 ### 样例输入 #1 ``` 40 ``` ### 样例输出 #.1 ``` 102334155 ``` ## 注意 Fibonacci数列增长速度非常快，第46项为1836311903，第47项就超出int型范围了。