道者编程

PHP实现菲波那契数列算法

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)(n>=4,n∈N*)。这段话取之于百度百科。

上面用文字解释其实就是第1列和第2列都是1,从第3列开始,每1列的值为前面两列之和。在业内有个很简单的递归算法描述这个。

1、1、2、3、5、8、13、21……

用PHP获取N列的值:

1:递归

<?php
function fbnq($n)
{
    if($n==1||$n==2){
        return 1;
    }
    return fbnq($n-1)+fbnq($n-2); 
}
echo fbnq(10); //第10列的值是55
 2:数组递推

<?php
function fbnq($n)
{
    if($n==1||$n==2){
        return 1;
    }
    if($n>2){
        $list[1] = $list[2] = 1; #设置前面两个值 1
        for($i=3;$i<=$n;$i++){ //大于等于3的时候,值为前面2个值相加
            $list[$i] = $list[$i-1] + $list[$i-2];
        }
        return $list[$n];
    }
}
echo fbnq(10);
 3:数组递推互换

<?php
function fbnq($n)
{
    if( $n <=2){
        return 1;
    }
    $t1 = 1;$t2 = 1;
    for($i=3;$i<$n;$i++){
        $temp = $t1;
        $t1 = $t2;
        $t2 = $temp + $t2;
    }
    return $t1 + $t2;
}
echo fbnq(10);
 



最新评论:
我要评论:

看不清楚