首页分享斐波那契数列

斐波那契数列

来源：花匠小妙招时间：2024-09-17 19:16

之前经常会遇见让实现斐波那契数列的编程题，但是一直不知道为什么要实现这个数列，这个数列又有什么作用，为什么数列的定义是哪样的？后来在上组合数学课程的时候，才发现了关于斐波那契数列的一些具体应用示例，现将之记录下来。

斐波那契数列

(1)斐波那契数列的定义

斐波那契数列是指前两项为1，从第三项起后每一项项是前两项之和的一个数列，即斐波那契数列的实例为：1，1，2，3，5，8，13，21，34，55，89，144…

斐波那契数列数列的递推公式可由下式进行描述：
{ F 0 = 1 F 1 = 1 F n = F n − 1 + F n − 2 , n ≥ 2

{F0=1F1=1Fn=Fn−1+Fn−2,amp;n≥2" role="presentation">{F0=1F1=1Fn=Fn−1+Fn−2,amp;n≥2

⎩⎪⎨⎪⎧F0=1F1=1Fn=Fn−1+Fn−2,n≥2

斐波那契数列的通项公式可描述为：
F n = 5 5 ∗ [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] F_n = frac{sqrt{5}}{5}*[{(frac{1+sqrt{5}}{2})}^n-{(frac{1-sqrt{5}}{2})}^n] Fn=55

∗[(21+5

)n−(21−5

)n]

(2)斐波那契数列的实际应用

上楼梯问题：
某人欲登上 n n n级楼梯，若每次只能跨一级或者两级，则从地面到第 n n n级楼梯，共有多少种不同的方法？

求解这个问题时，可以从第 n n n级开始，以自顶向下的思想进行求解。首先假设上到第 n n n级楼梯的方法数有 a n a_n an种，则最后一步有两种可能：

1.跨一步，则剩下的n-1级楼梯有an-1种上法
2.跨两步，则剩下的n-2级楼梯有an-2种上法

所以第 a n = a n − 1 + a n − 2 a_n = a_{n-1} + a_{n-2} an=an−1+an−2，从 a n a_n an开始递归求解，直到 a 3 a_3 a3都可使用上式进行求解。当求 a 2 a_2 a2时，根据规则限制，只有两种方法，第一种为直接一步上两级，第二种为每次上一级，所以 a 2 = 2 a_2 = 2 a2=2。 a 1 a_1 a1因为所求得第一级的上法，限于规则只有一种方法。所以整个过程可用下式描述：
{ a n = a n − 1 + a n − 2 , n = ≥ 3 a 1 = 1 , a 2 = 2

{an=an−1+an−2,n=≥3a1=1,a2=2" role="presentation">{an=an−1+an−2,n=≥3a1=1,a2=2

{an=an−1+an−2,n=≥3a1=1,a2=2
假设 a 0 = 1 a_0 =1 a0=1，则上式为斐波那契数列，根据斐波那契数列的规则可以很轻易的求解出第 n n n级的上法。

棋盘染色问题：
给定一个具有1行 n n n列的 1 ∗ n 1*n 1∗n棋盘的每一个方块涂以红、蓝二色之一，要求相邻的两块不能都染成红色，设不同的染色共有 a n a_n an种，求 a n a_n an。

首先针对 a n a_n an进行分析，此时需要分情况考虑：
1.当第 n n n号棋盘染红色时，则 n − 1 n-1 n−1号棋盘只能染蓝色，则满足题目的染色方法共有 a n = a n − 2 a_n = a_{n-2} an=an−2种。
2.当第 n n n号棋盘染蓝色时，则 n − 1 n-1 n−1号棋盘既可以染红色也可以染蓝色，则$a_n = a_{n-1}种。

综上可得 a n = a n − 1 + a n − 2 a_n = a_{n-1} + a_{n-2} an=an−1+an−2 。

下面继续分析 n = 2 n=2 n=2和 n = 1 n=1 n=1的情况，当 n = 2 n=2 n=2时，红蓝、蓝蓝、蓝红三种染色方法。当 n = 1 n=1 n=1时，有红、蓝两种染色方法。所以可以用如下公式描述：
{ a n = a n − 1 + a n − 2 , n = ≥ 3 a 1 = 2 , a 2 = 3

{an=an−1+an−2,n=≥3a1=2,a2=3" role="presentation">{an=an−1+an−2,n=≥3a1=2,a2=3

{an=an−1+an−2,n=≥3a1=2,a2=3
上式可以看做是从第三项开始的斐波那契数列。

F 1 F_1 F1 F 2 F_2 F2 F 3 F_3 F3 F 4 F_4 F4 F 5 F_5 F5 F 6 F_6 F6…112358… a 1 a_1 a1 a 2 a_2 a2 a 3 a_3 a3 a 4 a_4 a4… (三)斐波那契数列的其他有趣故事

自然界中的’‘巧合’'
斐波那契数列在自然科学的其他分支，有许多应用。例如，树木的生长，由于新生的枝条，往往需要一段“休息”时间，供自身生长，而后才能萌发新枝。所以，一株树苗在一段间隔，例如一年，以后长出一条新枝；第二年新枝“休息”，老枝依旧萌发；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则次年“休息”。这样，一株树木各个年份的枝桠数，便构成斐波那契数列。这个规律，就是生物学上著名的“鲁德维格定律”。

另外，观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花的花瓣，可以发现它们花瓣数目具有斐波那契数：3、5、8、13、21、……

这些植物懂得斐波那契数列吗？应该并非如此，它们只是按照自然的规律才进化成这样。这似乎是植物排列种子的“优化方式”，它能使所有种子具有差不多的大小却又疏密得当，不至于在圆心处挤了太多的种子而在圆周处却又稀稀拉拉。叶子的生长方式也是如此，对于许多植物来说，每片叶子从中轴附近生长出来，为了在生长的过程中一直都能最佳地利用空间（要考虑到叶子是一片一片逐渐地生长出来，而不是一下子同时出现的），每片叶子和前一片叶子之间的角度应该是222.5度，这个角度称为“黄金角度”，因为它和整个圆周360度之比是黄金分割数0.618033989……的倒数，而这种生长方式就决定了斐波那契螺旋的产生。向日葵的种子排列形成的斐波那契螺旋有时能达到89，甚至144条。1992年，两位法国科学家通过对花瓣形成过程的计算机仿真实验，证实了在系统保持最低能量的状态下，花朵会以斐波那契数列长出花瓣。

与黄金分割的关系
开普勒发现数列前、后两项之比1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ,… ,也组成了一个数列，会趋近黄金分割： f n + 1 f n ≈ a = 1 2 ( 1 + 5 ) = φ ≈ 1.618... frac{f_{n+1}}{f_n} approx a = frac{1}{2}(1+sqrt5) = varphi approx 1.618... fnfn+1≈a=21(1+5

)=φ≈1.618...
斐波那契数列可以用连分数来表示：
1 1 = 1 ， 2 1 = 1 + 1 1 ， 3 2 = 1 + 1 1 + 1 1 ， 5 3 = 1 + 1 1 + 1 1 + 1 1 ， 8 5 = 1 + 1 1 + 1 1 + 1 1 + 1 1 frac{1}{1} = 1，frac{2}{1} = 1+frac{1}{1}，frac{3}{2} =1+frac{1}{1+frac{1}{1}}，frac{5}{3} = 1+frac{1}{1+frac{1}{1+frac{1}{1}}}，frac{8}{5} = 1+ frac{1}{1+frac{1}{1+frac{1}{1+frac{1}{1}}}} 11=1，12=1+11，23=1+1+111，35=1+1+1+1111，58=1+1+1+1+11111
F n = 1 5 ∗ [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] = φ n 5 − ( 1 − φ ) n 5 F_n = frac{1}{sqrt{5}}*[{(frac{1+sqrt{5}}{2})}^n-{(frac{1-sqrt{5}}{2})}^n] = frac{varphi^n}{sqrt{5}}-frac{{(1-varphi)}^n}{sqrt{5}} Fn=5

1∗[(21+5

)n−(21−5

)n]=5

φn−5

(1−φ)n
而黄金分割数也可以用无限多重根号表示：
φ = 1 + 1 1 + 1 1 + 1 1 + 1 1 + 1 1 + 1 . . . varphi=1+frac{1}{1+frac{1}{1+frac{1}{1+frac{1}{1+frac{1}{1+frac{1}{...}}}}}} φ=1+1+1+1+1+1+...111111
斐波那契数列第 n n n项与第 n − 1 n-1 n−1项比值的极限即为黄金分割比。