PHP算法斐波那契数列的N种算法

来源：邢台IT培训学院时间：2020/7/16 14:03:47

斐波那契数是什么
斐波那契数列（Fibonaccisequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（LeonardodaFibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：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)递归计算即可，但是性能是低的。
/***普通递归*@paramint$n*@returnint*/functionfib($n=1){//低位处理if($n<3){return1;}//递归计算前两位returnfib($n-1)+fib($n-2);}递归优化
从上面的递归方法可以看到，进行了很多的重复计算，性能极差，如果N越大，计算的次数太可怕了，那么，既然因为重复计算影响了性能，那么优化就从减少重复计算入手，即把之前计算的存储起来，这样就避免了过多的重复计算，优化了递归算法。

/***递归优化*@paramint$n*@paramint$a*@paramint$b*@returnint*/functionfib_2($n=1,$a=1,$b=1){if($n>2){//存储位，优化递归计算returnfib_2($n-1,$a+$b,$a);}return$a;}记忆化自底向上

邢台IT培训学校

自底向上通过迭代计算斐波那契数的子问题并存储已计算的值，通过已计算的值进行计算。使用for循环，减少递归带来的重复计算问题。
/***记忆化自底向上*@paramint$n*@returnint*/functionfib_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个数。/***自底向上进行迭代*@paramint$n*@returnint*/functionfib_4($n=1){//低位处理if($n<=0){return0;}if($n<3){return1;}$a=0;$b=1;//循环计算for($i=2;$i<$n;$i++){$b=$a+$b;$a=$b-$a;}return$b;}公式法
通过了解斐波那契序列和黄金分割比之间的关系，使用黄金分割率计算第N个斐波那契数。
/***公式法*@paramint$n*@returnint*/functionfib_5($n=1){//黄金分割比$radio=(1+sqrt(5))/2;//斐波那契序列和黄金分割比之间的关系计算$num=intval(round(pow($radio,$n)/sqrt(5)));return$num;}欠揍法
这个方法，我就不多说了吧，大家都懂的，但是千万别轻易尝试……
/***欠揍法*@paramint$n*@returnint*/functionfib_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];}

领取试听课

每天限量名额，先到先得

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/2331/news/219310/违者必究！以上就是邢台IT培训学院小编为您整理 PHP算法斐波那契数列的N种算法的全部内容。