前言
#前段時間，遇到最佳化計算斐波那契數列的常規遞歸方法，但是一時間並沒有及時想到很好的方法，所以後面查找了相關資料，總結了多種計算解法，所以分享出來，和大家一起交流學習。
推薦：《PHP影片教學》
斐波那契數是什麼
#斐波那契數列（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];
}最後
#好了，我就大概寫了幾種解法，如果有不對的地方，請大家指出，我會及時修改，大家有其他計算方法，歡迎分享出來一起交流和學習，謝謝！
以上是PHP之斐波那契數列的N種演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！
