關(guān)于“斐波那契數(shù)列”的編程

關(guān)于“斐波那契數(shù)列”的編程

       今天上網(wǎng)看到一個有關(guān)“斐波那契數(shù)列”的數(shù)學(xué)概念。自己學(xué)習(xí)編程時間也不短了，就借這個東東練習(xí)一下。

       斐波那契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）（來自百度）

       一開始，我編程的代碼如下：

function fbnq($num) {

     if ($num == 0) {

         return 0;

     }elseif ($num== 1) {

         return 1;

     }else {

         return fbnq($num-2) + fbnq($num-1);

     }

}

$total = 10;

$arr = array();

for ($i=0;$i <$total ;$i++) {

     $arr[$i] = fbnq($i);

     echo  $i. '--->' .  $arr[$i] . '<br>';

}

編好以后，我想OK了，結(jié)果把$tatal改到25以后就發(fā)現(xiàn)運(yùn)行越來越慢了。運(yùn)行到30秒程序就提示運(yùn)行時間太長了?？赡苁呛瘮?shù)設(shè)計的效率問題。因為一開始我考慮用遞歸，n大于3以后，每個數(shù)都要通過遞歸來獲得。越往后，遞歸次數(shù)越多。實際上，根本不需要用到遞歸。只需要取前面已經(jīng)做好的運(yùn)算結(jié)果相加就好了。于是，改為以下代碼，$tata改為100也沒問題了：

function fbnq($num) {

     global $arr;

     if ($num == 0) {

         return 0;

     }elseif ($num== 1) {

         return 1;

     }else {

         return $arr[$num-2]  + $arr[$num-1];

     }

}

$total = 100;

$arr = array();

for ($i=0;$i <$total ;$i++) {

     $arr[$i] = fbnq($i);

     echo  $i. '--->' .  $arr[$i] . '<br>';

}