前言

前段時間，遇到優化計算斐波那契數列的常規遞歸方法，但是一時間并沒有及時想到很好的方法，所以后面查找了相關資料，總結了多種計算解法，所以分享出來，和大家一起交流學習。

斐波那契數是什么

斐波那契數列(Fibonacci sequence)，又稱黃金分割數列、因數學家列昂納多·斐波那契(Leonardoda Fibonacci)以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波那契數列以如下被以遞推的方法定義：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3，n ∈ N*)。

知道了斐波那契數，那么下面我們就用多種不同的方法來計算獲取第N位斐波那契數。

普通遞歸

這種方法是最常規的，直接根據定義F(n)=F(n - 1)+F(n - 2)遞歸計算即可，但是性能是最低的。

/**

* 普通遞歸

* @param int $n

* @return int

*/

function fib($n = 1)

{

// 低位處理

if ($n < 3) {

return 1;

}

// 遞歸計算前兩位

return fib($n - 1) + fib($n - 2);

}

遞歸優化

從上面的遞歸方法可以看到，進行了很多的重復計算，性能極差，如果N越大，計算的次數太可怕了，那么，既然因為重復計算影響了性能，那么優化就從減少重復計算入手，即把之前計算的存儲起來，這樣就避免了過多的重復計算，優化了遞歸算法。

/**

* 遞歸優化

* @param int $n

* @param int $a

* @param int $b

* @return int

*/

function fib_2($n = 1, $a = 1, $b = 1)

{

if ($n > 2) {

// 存儲前一位，優化遞歸計算

return fib_2($n - 1, $a + $b, $a);

}

return $a;

}

記憶化自底向上

自底向上通過迭代計算斐波那契數的子問題并存儲已計算的值，通過已計算的值進行計算。使用for循環，減少遞歸帶來的重復計算問題。

/**

* 記憶化自底向上

* @param int $n

* @return int

*/

function fib_3($n = 1)

{

$list = [];

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

// 從低到高位數，依次存入數組中

if ($i < 2) {

$list[] = $i;

} else {

$list[] = $list[$i - 1] + $list[$i - 2];

}

}

// 返回最后一個數，即第N個數

return $list[$n];

}

自底向上進行迭代

最低位初始化賦值，使用for從低位到高位迭代計算，從而得到第N個數。

/**

* 自底向上進行迭代

* @param int $n

* @return int

*/

function fib_4($n = 1)

{

// 低位處理

if ($n <= 0) {

return 0;

}

if ($n < 3) {

return 1;

}

$a = 0;

$b = 1;

// 循環計算

for ($i = 2; $i < $n; $i++) {

$b = $a + $b;

$a = $b - $a;

}

return $b;

}

公式法

通過了解斐波那契序列和黃金分割比之間的關系，使用黃金分割率計算第N個斐波那契數。

/**

* 公式法

* @param int $n

* @return int

*/

function fib_5($n = 1)

{

// 黃金分割比

$radio = (1 + sqrt(5)) / 2;

// 斐波那契序列和黃金分割比之間的關系計算

$num = intval(round(pow($radio, $n) / sqrt(5)));

return $num;

}

無敵欠揍法

這個方法，我就不多說了吧，大家都懂的，但是千萬別輕易嘗試……

/**

* 無敵欠揍法

* @param int $n

* @return int

*/

function fib_6($n = 1)

{

// 列舉了30個數

$list = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269];

return $list[$n];

}

最后

好了，我就大概寫了幾種解法，如果有不對的地方，請大家指出，我會及時修改，大家有其他計算方法，歡迎分享出來一起交流和學習，謝謝！