|
從兔子說起 一般而言，兔子在出生兩個月后，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔子都不死，起初有一對小兔子，那么一年以后可以繁殖多少對兔子？ 舉個例子，第一個月小兔子沒有繁殖能力，所以還是一對，兩個月后，生下一對小兔對數(shù)共有兩對，三個月以后，老兔子又生下一對，因為小兔子還沒有繁殖能力，所以一共是三對...... 以此類推我們得到下表
這個數(shù)列是意大利中世紀數(shù)學家斐波那契在《算盤全書》中提出的，這就是著名的斐波那契數(shù)列。如果設(shè)F(n）為該數(shù)列的第n項（n∈N*），那么這句話可以寫成如下形式： F(1)=1，F(xiàn)(2)=1 F(n)=F(n-1)+F(n-2)（n≥3，n∈N*） 通項公式 我們除了可以用上面的遞推式計算出斐波那契數(shù)列的每一項，我們還可以直接使用通項公式 至于有關(guān)它的推導主要有兩種，一種是利用特征方程，另一種是待定系數(shù)法構(gòu)建等比數(shù)列。具體的推導過程在這里就不贅述了。 生活中隨處可見 斐波那契數(shù)列中的斐波那契數(shù)會經(jīng)常出現(xiàn)在我們的眼前——比如松果、鳳梨、樹葉的排列、某些花朵的花瓣數(shù)（典型的有向日葵花瓣），蜂巢，蜻蜓翅膀等等。斐波那契數(shù)還可以在植物的葉、枝、莖等排列中發(fā)現(xiàn)。 大自然里一些花草長出的枝條經(jīng)常會出現(xiàn)斐波那契數(shù)，新的一枝從葉腋長出，而另外的新枝又從舊枝長出來，老枝條和新枝條的數(shù)目的和就像那兔子問題一樣。 （下面兩段內(nèi)容選擇閱讀） 仔細觀察向日葵的花，可以看到，向日葵花盤內(nèi)，種子是按對數(shù)螺線排列的，有順時針轉(zhuǎn)和逆時針轉(zhuǎn)的兩組對數(shù)螺線。兩組螺線的條數(shù)往往成相繼的兩個斐波那契數(shù)，一般是34和55，大向日葵是89和144，還曾發(fā)現(xiàn)過一個更大的向日葵有144和233條螺線，它們都是相繼的兩個斐波那契數(shù)。 常見的花瓣還有3瓣的鳶尾花（看上去是6片花瓣，實際上是兩組3瓣），8瓣的飛燕草，13瓣的翠雀花等等。 數(shù)學問題 斐波那契數(shù)列有關(guān)的數(shù)學問題可有點多，比如楊輝三角、黃金分割、排列組合、矩形面積、質(zhì)數(shù)數(shù)量、尾數(shù)循環(huán)等等。 其中黃金分割比較簡單，在這里說一下，隨著數(shù)列項數(shù)的增加，前一項與后一項之比越來越逼近黃金分割的數(shù)值0.6180339887..… 今天我們只考慮一個楊輝三角問題（原因是這個問題似乎比起其他幾個好像更接近程序設(shè)計）。這一期主要還是說斐波那契數(shù)列的，所以楊輝三角我們只說一下他們之間的聯(lián)系。 楊輝三角的第一行只有一個數(shù)為1，接下來每一行都比上一行要多一個數(shù)，每個數(shù)等于它上方兩數(shù)之和。 在這張圖里相信大家已經(jīng)發(fā)現(xiàn)了斐波那契數(shù)列，就是每條虛線上數(shù)字的和，但這樣似乎不夠明顯，那我們把楊輝三角每一行的左端對齊。 這次是不是思路清晰多了。 例題 1.一般而言，兔子在出生兩個月后，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔子都不死，起初有一對小兔子，那么X個月以后可以繁殖多少對兔子？ 這個就是開篇的兔子數(shù)列，我們就直接略過了吧。 2.蜜蜂路線 3.爬樓梯 樓梯有n階，上樓可以一步上1階，也可以一步上2階。請問一共有多少種方案從樓梯底上到第n階上。 這道題和蜜蜂路線就比較相似了，如果想要上到第n階，只能從第n-1階或n-2階爬一步之后上到第n階上。那么我們是需要算好上到第1階只有一種方案，第2階有兩種方案，之后從第3階開始，每階的方案數(shù)就等于前兩階方案數(shù)的和，一直算到第n階就好了。 幾種變形
如果上面的爬樓梯問題每步可以上1-3階呢？那1-4階呢？同樣的我們只需要數(shù)好前幾階共有幾種方案，之后的每階的方案數(shù)就是這階前3或4方案數(shù)之和。 2.二維變形 過河卒（NOIP2002普及組）（洛谷P1002） 類似地，想要走到一個格子里只能從這個格子的上方或左方進入，依次遞推出結(jié)果就好了。 求斐波那契數(shù)列第N項 1.遞歸
2.遞推
3.迭代（模擬）
|
|
|
可以看出幼仔對數(shù)（從2月起）、成兔對數(shù)、總體對數(shù)都構(gòu)成了一個數(shù)列。這個數(shù)列有關(guān)十分明顯的特點，那就是：
