兔子數列

標籤: 暫無標籤

11

更新時間: 2013-09-03

廣告

數列中的每一個數都叫做這個數列的項。排在第一位的數稱為這個數列的第1項(通常也叫做首項),排在第二位的數稱為這個數列的第2項……排在第n位的數稱為這個數列的第n項。

  
兔子數列

即斐波那契數列,「斐波那契數列」的發明者,是義大利數學家列昂納多·斐波那契(Leonardo Fibonacci,生於公元1170年,卒於1240年。籍貫大概是比薩)。他被人稱作「比薩的列昂納多」。1202年,他撰寫了《珠算原理》(Liber Abaci)一書。他是第一個研究了印度和阿拉伯數學理論的歐洲人。他的父親被比薩的一家商業團體聘任為外交領事,派駐地點相當於今日的阿爾及利亞地區,列昂納多因此得以在一個阿拉伯老師的指導下研究數學。他還曾在埃及、敘利亞、希臘、西西里和普羅旺斯研究數學。


  斐波那契數列指的是這樣一個數列:0,1,1,2,3,5,8,13,21……


  這個數列從第三項開始,每一項都等於前兩項之和。它的通項公式為:(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根號5】


  很有趣的是:這樣一個完全是自然數的數列,通項公式居然是用無理數來表達的。


  【該數列有很多奇妙的屬性】


  比如:隨著數列項數的增加,前一項與后一項之比越逼近黃金分割0.6180339887……


  還有一項性質,從第二項開始,每個奇數項的平方都比前後兩項之積多1,每個偶數項的平方都比前後兩項之積少1。


  如果你看到有這樣一個題目:某人把一個8*8的方格切成四塊,拼成一個5*13的長方形,故作驚訝地問你:為什麼64=65?其實就是利用了斐波那契數列的這個性質:5、8、13正是數列中相鄰的三項,事實上前後兩塊的面積確實差1,只不過後面那個圖中有一條細長的狹縫,一般人不容易注意到。


  如果任意挑兩個數為起始,比如5、-2.4,然後兩項兩項地相加下去,形成5、-2.4、2.6、0.2、2.8、3、5.8、8.8、14.6……等,你將發現隨著數列的發展,前後兩項之比也越來越逼近黃金分割,且某一項的平方與前後兩項之積的差值也交替相差某個值。


  斐波那契數列的第n項同時也代表了集合{1,2,...,n}中所有不包含相鄰正整數的子集個數。


  【斐波那契數列別名】


  斐波那契數列又因數學家列昂納多·斐波那契以兔子繁殖為例子而引入,故又稱為「兔子數列」。


  斐波那契數列


  一般而言,兔子在出生兩個月後,就有繁殖能力,一對兔子每個月能生出一對小兔子來。如果所有兔都不死,那麼一年以後可以繁殖多少對兔子?


  我們不妨拿新出生的一對小兔子分析一下:


  第一個月小兔子沒有繁殖能力,所以還是一對;


  兩個月後,生下一對小兔民數共有兩對;


  三個月以後,老兔子又生下一對,因為小兔子還沒有繁殖能力,所以一共是三對;


  ------


  依次類推可以列出下表:


  經過月數:0 1 2 3 4 5 6 7 8 9 10 11 12


  兔子對數:1 1 2 3 5 8 13 21 34 55 89 144 233


  表中數字0,1,1,2,3,5,8---構成了一個數列。這個數列有關十分明顯的特點,那是:前面相鄰兩項之和,構成了后一項。


  這個數列是義大利中世紀數學家斐波那契在<算盤全書>中提出的,這個級數的通項公式,除了具有a(n+2)=an+a(n+1)/的性質外,還可以證明通項公式為:an=1/√[(1+√5/2) n-(1-√5/2) n](n=1,2,3.....)


  【斐波那挈數列通項公式的推導】


  斐波那契數列:0,1,1,2,3,5,8,13,21……


  如果設F(n)為該數列的第n項(n∈N+)。那麼這句話可以寫成如下形式:


  F(1)=F(2)=1,F(n)=F(n-1)+F(n-2) (n≥3)


  顯然這是一個線性遞推數列。


  通項公式的推導方法一:利用特徵方程


  線性遞推數列的特徵方程為:


  X^2=X+1


  解得


  X1=(1+√5)/2, X2=(1-√5)/2.


  則F(n)=C1*X1^n + C2*X2^n


  ∵F(1)=F(2)=1


  ∴C1*X1 + C2*X2


  C1*X1^2 + C2*X2^2


  解得C1=1/√5,C2=-1/√5


  ∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根號5】


  通項公式的推導方法二:普通方法


  設常數r,s


  使得F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]


  則r+s=1, -rs=1


  n≥3時,有


  F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]


  F(n-1)-r*F(n-2)=s*[F(n-2)-r*F(n-3)]


  F(n-2)-r*F(n-3)=s*[F(n-3)-r*F(n-4)]


  ……


  F(3)-r*F(2)=s*[F(2)-r*F(1)]


  將以上n-2個式子相乘,得:


  F(n)-r*F(n-1)=[s^(n-2)]*[F(2)-r*F(1)]


  ∵s=1-r,F(1)=F(2)=1


  上式可化簡得:


  F(n)=s^(n-1)+r*F(n-1)


  那麼:


  F(n)=s^(n-1)+r*F(n-1)


  = s^(n-1) + r*s^(n-2) + r^2*F(n-2)


  = s^(n-1) + r*s^(n-2) + r^2*s^(n-3) + r^3*F(n-3)


  ……


  = s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)*F(1)


  = s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)


  (這是一個以s^(n-1)為首項、以r^(n-1)為末項、r/s為公差的等比數列的各項的和)


  =[s^(n-1)-r^(n-1)*r/s]/(1-r/s)


  =(s^n - r^n)/(s-r)


  r+s=1, -rs=1的一解為 s=(1+√5)/2, r=(1-√5)/2


  則F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}


  【C語言程序】


  main()


  {


  long fib[40] = {1,1};


  int i;


  for(i=2;i<40;i++)


  {


  fib&#91;i &#93; = fib&#91;i-1&#93;+fib&#91;i-2&#93;;


  }


  for(i=0;i<40;i++)


  {


  printf("F%d==%d\n", i, fib);


  }


  return 0;


  }


  【Pascal語言程序】


  var


  fib: array&#91;0..40&#93;of longint;


  i: integer;


  begin


  fib[0] := 1;


  fib[1] := 1;


  for i:=2 to 39 do


  fib&#91;i &#93; := fib&#91;i-1&#93; + fib&#91;i-2&#93;;


  for i:=0 to 39 do


  write(&#039;F&#039;, i, &#039;=&#039;, fib&#91;i &#93;);


  end.


  【數列與矩陣】


  對於斐波那契數列0.1,1,2,3,5,8,13…….有如下定義


  F(n)=f(n-1)+f(n-2)


  F(1)=1


  F(2)=1


  對於以下矩陣乘法


  F(n+1) = 1 1 * F(n)


  F(n) 1 0 F(n-1)


  它的運算就是


  F(n+1)=F(n)+F(n-1)


  F(n)=F(n)


  可見該矩陣的乘法完全符合斐波那契數列的定義


  設1 為B,1 1為C


  1 1 0


  可以用迭代得到:


  斐波那契數列的某一項F(n)=(BC^(n-2))1


  這就是斐波那契數列的矩陣乘法定義.


  另矩陣乘法的一個運演算法則A&not;^n(n為偶數)=A^(n/2)* A^(n/2).


  因此可以用遞歸的方法求得答案.


  時間效率:O(logn),比模擬法O(n)遠遠高效。


  代碼(PASCAL)


  {變數matrix是二階方陣, matrix是矩陣的英文}


  program fibonacci;


  type


  matrix=array&#91;1..2,1..2&#93; of qword;


  var


  c,cc:matrix;


  n:integer;


  function multiply(x,y:matrix):matrix;


  var


  temp:matrix;


  begin


  temp&#91;1,1&#93;:=x&#91;1,1&#93;*y&#91;1,1&#93;+x&#91;1,2&#93;*y&#91;2,1&#93;;


  temp&#91;1,2&#93;:=x&#91;1,1&#93;*y&#91;1,2&#93;+x&#91;1,2&#93;*y&#91;2,2&#93;;


  temp&#91;2,1&#93;:=x&#91;2,1&#93;*y&#91;1,1&#93;+x&#91;2,2&#93;*y&#91;2,1&#93;;


  temp&#91;2,2&#93;:=x&#91;2,1&#93;*y&#91;1,2&#93;+x&#91;2,2&#93;*y&#91;2,2&#93;;


  exit(temp);


  end;


  function getcc(n:integer):matrix;


  var


  temp:matrix;


  t:integer;


  begin


  if n=1 then exit(c);


  t:=n div 2;


  temp:=getcc(t);


  temp:=multiply(temp,temp);


  if odd(n) then exit(multiply(temp,c))


  else exit(temp);


  end;


  procedure init;


  begin


  readln(n);


  c&#91;1,1&#93;:=1;


  c&#91;1,2&#93;:=1;


  c&#91;2,1&#93;:=1;


  c&#91;2,2&#93;:=0;


  if n=1 then


  begin


  writeln(1);


  halt;


  end;


  if n=2 then


  begin


  writeln(1);


  halt;


  end;


  cc:=getcc(n-2);


  end;


  procedure work;


  begin


  writeln(cc&#91;1,1&#93;+cc&#91;1,2&#93;);


  end;


  begin


  init;


  work;


  end.


  【數列值的另一種求法】


  F(n) = &#91; (( sqrt ( 5 ) + 1 ) / 2) ^ n &#93;


  其中&#91; x &#93;表示取距離 x 最近的整數。


  【數列的前若干項】


  0 1


  1 1


  2 2


  3 3


  4 5


  5 8


  6 13


  7 21


  8 34


  9 55


  10 89


  11 144


  12 233


  13 377


  14 610


  15 987


  16 1597


  17 2584


  18 4181


  19 6765


  20 10946


  該數列有很多奇妙的屬性


  比如:隨著數列項數的增加,前一項與后一項之比越逼近黃金分割0.6180339887……


  還有一項性質,從第二項開始,每個奇數項的平方都比前後兩項之積(請自己驗證后自己確定)1,每個偶數項的平方都比前後兩項之積(請自己驗證后自己確定)1。


  如果你看到有這樣一個題目:某人把一個8*8的方格切成四塊,拼成一個5*13的長方形,故作驚訝地問你:為什麼64=65?其實就是利用了斐波那契數列的這個性質:5、8、13正是數列中相鄰的三項,事實上前後兩塊的面積確實差1,只不過後面那個圖中有一條細長的狹縫,一般人不容易注意到。


  如果任意挑兩個數為起始,比如5、-2.4,然後兩項兩項地相加下去,形成5、-2.4、2.6、0.2、2.8、3、5.8、8.8、14.6……等,你將發現隨著數列的發展,前後兩項之比也越來越逼近黃金分割,且某一項的平方與前後兩項之積的差值也交替相差某個值。如果所有的數都要求是自然數,能找出被任意正整數整除的項的此類數列,必然是斐波那契數列的某項開始每一項的倍數,如4,6,10,16,26……(從2開始每個數的兩倍)。


  斐波那契數列的第n項同時也代表了集合{1,2,...,n}中所有不包含相鄰正整數的子集個數。


  斐波那契數列(f(n),f(0)=0,f(1)=1,f(2)=1,f(3)=2……)的其他性質:


  1.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1


  2.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)-1


  3.f(0)+f(2)+f(4)+…+f(2n)=f(2n+1)-1


  4.&#91;f(0)&#93;^2+&#91;f(1)&#93;^2+…+&#91;f(n)&#93;^2=f(n)·f(n+1)


  5.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·&#91;f(n+1)-f(n)&#93;+1


  6.f(m+n)=f(m-1)·f(n-1)+f(m)·f(n)


  7.&#91;f(n)&#93;^2=(-1)^(n-1)+f(n-1)·f(n+1)


  8.f(2n-1)=&#91;f(n)&#93;^2-&#91;f(n-2)&#93;^2


  在楊輝三角中隱藏著斐波那契數列


  1


  1 1


  1 2 1


  1 3 3 1


  1 4 6 4 1


  ……


  過第一行的「1」向左下方做45度斜線,之後做直線的平行線,將每條直線所過的數加起來,即得一數列1、1、2、3、5、8……


  (1)細察下列各種花,它們的花瓣的數目具有斐波那契數:延齡草、野玫瑰、南美血根草、大波斯菊、金鳳花、耬斗菜、百合花、蝴蝶花。


  (2)細察以下花的類似花瓣部分,它們也具有斐波那契數:紫宛、大波斯菊、雛菊。


  斐波那契數經常與花瓣的數目相結合:


  3………………………百合和蝴蝶花


  5………………………藍花耬斗菜、金鳳花、飛燕草


  8………………………翠雀花


  13………………………金盞草


  21………………………紫宛


  34,55,84……………雛菊


  (3)斐波那契數還可以在植物的葉、枝、莖等排列中發現。例如,在樹木的枝幹上選一片葉子,記其為數0,然後依序點數葉子(假定沒有折損),直到到達與那息葉子正對的位置,則其間的葉子數多半是斐波那契數。葉子從一個位置到達下一個正對的位置稱為一個循回。葉子在一個循回中旋轉的圈數也是斐波那契數。在一個循回中葉子數與葉子旋轉圈數的比稱為葉序(源自希臘詞,意即葉子的排列)比。多數的葉序比呈現為斐波那契數的比。


  (4)斐波那契數列與黃金比值


  相繼的斐波那契數的比的數列:


  它們交錯地或大於或小於黃金比的值。該數列的極限為。這種聯繫暗示了無論(尤其在自然現象中)在哪裡出現黃金比、黃金矩形或等角螺線,那裡也就會出現斐波那契數,反之亦然。


  可它的每一項卻都是整數。而且這個數列中相鄰兩項的比值,越靠後其值越接近0.618。這個數列有廣泛的應用,如樹的年分枝數目就遵循斐波那契數列的規律;而且計算機科學的發展,為斐波那契數列提供了新的應用場所。

廣告

廣告