|
从兔子说起 一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，起初有一对小兔子，那么一年以后可以繁殖多少对兔子？ 举个例子，第一个月小兔子没有繁殖能力，所以还是一对，两个月后，生下一对小兔对数共有两对，三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对...... 以此类推我们得到下表
这个数列是意大利中世纪数学家斐波那契在《算盘全书》中提出的，这就是著名的斐波那契数列。如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式： F(1)=1，F(2)=1 F(n)=F(n-1)+F(n-2)（n≥3，n∈N*） 通项公式 我们除了可以用上面的递推式计算出斐波那契数列的每一项，我们还可以直接使用通项公式 至于有关它的推导主要有两种，一种是利用特征方程，另一种是待定系数法构建等比数列。具体的推导过程在这里就不赘述了。 生活中随处可见 斐波那契数列中的斐波那契数会经常出现在我们的眼前——比如松果、凤梨、树叶的排列、某些花朵的花瓣数（典型的有向日葵花瓣），蜂巢，蜻蜓翅膀等等。斐波那契数还可以在植物的叶、枝、茎等排列中发现。 大自然里一些花草长出的枝条经常会出现斐波那契数，新的一枝从叶腋长出，而另外的新枝又从旧枝长出来，老枝条和新枝条的数目的和就像那兔子问题一样。 （下面两段内容选择阅读） 仔细观察向日葵的花，可以看到，向日葵花盘内，种子是按对数螺线排列的，有顺时针转和逆时针转的两组对数螺线。两组螺线的条数往往成相继的两个斐波那契数，一般是34和55，大向日葵是89和144，还曾发现过一个更大的向日葵有144和233条螺线，它们都是相继的两个斐波那契数。 常见的花瓣还有3瓣的鸢尾花（看上去是6片花瓣，实际上是两组3瓣），8瓣的飞燕草，13瓣的翠雀花等等。 数学问题 斐波那契数列有关的数学问题可有点多，比如杨辉三角、黄金分割、排列组合、矩形面积、质数数量、尾数循环等等。 其中黄金分割比较简单，在这里说一下，随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..… 今天我们只考虑一个杨辉三角问题（原因是这个问题似乎比起其他几个好像更接近程序设计）。这一期主要还是说斐波那契数列的，所以杨辉三角我们只说一下他们之间的联系。 杨辉三角的第一行只有一个数为1，接下来每一行都比上一行要多一个数，每个数等于它上方两数之和。 在这张图里相信大家已经发现了斐波那契数列，就是每条虚线上数字的和，但这样似乎不够明显，那我们把杨辉三角每一行的左端对齐。 这次是不是思路清晰多了。 例题 1.一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，起初有一对小兔子，那么X个月以后可以繁殖多少对兔子？ 这个就是开篇的兔子数列，我们就直接略过了吧。 2.蜜蜂路线 3.爬楼梯 楼梯有n阶，上楼可以一步上1阶，也可以一步上2阶。请问一共有多少种方案从楼梯底上到第n阶上。 这道题和蜜蜂路线就比较相似了，如果想要上到第n阶，只能从第n-1阶或n-2阶爬一步之后上到第n阶上。那么我们是需要算好上到第1阶只有一种方案，第2阶有两种方案，之后从第3阶开始，每阶的方案数就等于前两阶方案数的和，一直算到第n阶就好了。 几种变形
如果上面的爬楼梯问题每步可以上1-3阶呢？那1-4阶呢？同样的我们只需要数好前几阶共有几种方案，之后的每阶的方案数就是这阶前3或4方案数之和。 2.二维变形 过河卒（NOIP2002普及组）（洛谷P1002） 类似地，想要走到一个格子里只能从这个格子的上方或左方进入，依次递推出结果就好了。 求斐波那契数列第N项 1.递归
2.递推
3.迭代（模拟）
|
|
|
可以看出幼仔对数（从2月起）、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点，那就是：
