3.4斐波那契数列
“斐波那契数列（Fibonacci）”是由意大利数学家列昂纳多·斐波那契发明的，因此取名为斐波那契数列。在自然界中，很多现象都符合斐波那契数列，例如，植物的叶、鳞片、花、茎等排列中，都可发现这种规律。那么，斐波那契数列有什么规律？让我们先从兔子的繁殖说起。
3.4.1 兔子的家族
先来看著名斐波那契数列的例子：兔子家族。
意大利数学家列昂纳多·斐波那契在所写的《算盘书》中提出了下面的问题：
有小兔一对，如果它们第2个月成年，第3个月生下一对小兔，以后每月生产小兔一对，而所生的小兔亦在第2个月成年，第3个月生产另一对小兔，此后也每个月生一对小兔。问一年后共有多少对兔子（假设每产一对兔子必须为一雌一雄，而所有兔子都可以相互交配，并且没有死亡）。
要计算出一年后共有多少对兔子，没有公式可直接计算出来。根据题意，每月兔子的数量与上月兔子和上上月兔子的数量有很大关系，可通过前两个月的兔子数量推算出当月兔子的数量。
3.4.2 从最初几月数据中找规律
从第1个月开始向后推算：
第1个月，只有一对小兔子。
第2个月，小兔子成年，仍然只有一对兔子。
第3个月，有一对成年的兔子，成年的兔子生产一对小兔子，共有两对兔子。
第4个月，有两对成年的兔子，以及第3月1对成年兔子所生产的一对小兔子，共有三对兔子。
第5个月，有三对成年兔子，以及第4个月的两对成年兔子所生产的两对小兔子，共有5对兔子。
前面5个月兔子繁殖的过程如图3-23所示。
图3-23
设F(n)表示第n个月兔子的总数，则图3-23所示各月兔子数量可用以下算式来表示：
按上面列出的算式，可以很快推导出1年（共12个月）后兔子的总数，具体算式如下：
也就是说，1年后兔子的总数为144对。
也可将各月的成年兔子与小兔子的数量制作成一个表格，如下所示。
各月兔子的总数量组成一个列表，如下所示。
3.4.3 斐波那契数列
在上面列出的兔子繁殖过程中，每月兔子的数量组成一个序列，这个序列就称为斐波那契数列。这个数列从第3项开始，每一项都等于前两项之和。在数学上，斐波那契数列可以用递归的方法来定义：
在上面的算式中F0不是第一项，而是第0项，只是递归而定义的一个结束项。
在前面计算兔子总数时，我们是从第1个月开始逐月向后推导，如果要计算的项n的数据很多，就需要很多个步骤进行推导。好在我们找到了斐波那契数列的递归定义方式，在上面的3个算式中，Fn的值由Fn－1和Fn－2得出，而Fn－1和Fn－2又可由它们的前两项得出。也就是说，每次递归调用，都将问题规模缩小，当递归到第1项和第0项时，返回确定的值，这就可使递归调用结束。
只是，在这里的递归调用与本章前面例子中不一样，当计算第n项数据时，需要递归调用（n－1）项和（n－2）项。
根据以上分析，可用C语言编写如下程序计算出斐波那契数列中的前n项数据：
执行以上程序，输入12，表示生成12项斐波那契数列，得到如图3-24所示的结果。
图3-24
使用上面的程序，用递归方式推导出第n项的斐波那契数，如果n的值很大，这个推导过程就比较繁琐。其实，用初等代数解法也可推导出计算第n项斐波那契数的公式，具体推导过程这里就不列出来了，具体计算公式如下：
通过上面的公式就可以计算第n项斐波那契数。
如果觉得以上公式计算起来还是比较麻烦的话，可以使用以下公式得到一个大约数值：
例如，若取n＝12，则：
3.4.4 神奇的魔八方
最后，来看一个斐波那契数在魔术中的应用：“魔八方”。
一位魔术师拿着一块边长为8分米的正方形地毯，对观众朋友说：“我能把这块地毯分成4小块，再重新缝成一块长13分米，宽5分米的长方形地毯，你相信吗？”
观众中有人开始计算了：边长8分米的正方形，其面积为64平方分米；而边长13分米，宽5分米的长方形，其面积为65平方分米。两者面积相关1平方分米，肯定不行啊。
魔术师之所以称为魔术师，肯定有他的绝活，结果他还真的拼出了长13分米、宽5分米的地毯。如图3-25所示，就是魔术师的裁剪及拼接过程，左图将正方形裁剪成了4部分，右图是由这4部分拼接而成。
图3-25
为什么经过一裁一拼，地毯的面积就增加了1平方分米呢？为了分析这个问题，将图3-25右图所示的长方形以左下角为原点制作一个坐标系，如图3-26所示。
图3-26
在图3-26所示坐标系中，O点为原点，则A点的坐标为（50，20），B点的坐标为（80，30），则∠AOC的正切为2/5，而∠BOC的正切为3/8，显然OA与OB不在一条直线上。也就是说，实际上后来缝成的地毯有条细缝，面积刚好就是1平方分米。
那么，是不是所有正方形都可以进行这种方式的变化呢？
先来计算一下，设边长为n的正方形是否可以进行这种魔八方的变化。
根据图3-25所示的裁剪和拼接方式，可知道拼接后的矩形的长度为：
由于拼接后的长方形面积比正方形的面积多1，则可得到以下公式：
设：
代入上面的方程，可得到如下方程：
对于这个二元二次方程，由于只有一个方程式，属于不定方程，将这个不定方程中的x、y的值求出来，即可得到正方形的边长。对于不定方程，我们可以先计算出y的值在100以内时的各种整数解，如下表所示。
可以看出，x、y的值构成了斐波那契数列：1、2、3、5、8、13、21、34、55、89、……，也就是说，正方式的边长n应为斐波那契数列的前两项之和。例如，边长为8、13、21这些正方形都可以按魔八方的形式对图形进行裁剪和拼接，以使其面积增大。