您现在的位置是：自如初>PHP算法题PHP算法题

PHP两种方式实现斐波纳契数列

温新 2020-04-07 14:41:03 【PHP算法题】 1284人已围观

简介php实现斐波纳契数列。假设笫l个月有1对刚诞生的兔子，笫2个月进入成熟期，笫3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生兔子开始，12个月后会有多少对兔子呢？

神奇的兔子数列假设笫l个月有1对刚诞生的兔子，笫2个月进入成熟期，笫3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生兔子开始，12个月后会有多少对兔子呢？

(1) 问题分析

第 l个月，小兔子1没有繁殖能力，所以还是 l对。

第2个月，小兔子1进入成熟期，仍然是l对。

第3个月，兔子1生了1对小兔子2，于是这个月共有2 (1+1=2)对兔子。

第4个月，兔子1又生了1对小兔子3。因此共有3 (1+2=3)对兔子。

第5个月，兔子1又生了1对小兔子4，而在第3个月出生的兔子3也生下了1对小兔子2。共有5 (2+3=5)对兔子。

第6个月，兔子1，2，3各生下了1对小兔子。新生3对兔子加上原有的5对兔子这个月共有8 (3+5=8)对兔子。

兔子数列也就是斐波那契数列，即：1、1、2、3、5、8、13、21、34、55、89、144、233 ......

斐波那契数列从第3项开始，每一项都等于前两项之和。

F0=0，F1=1，Fn=F(n-1)+F(n-2) Fn = F(n-1) + F(n+1) F：指当前这个数列 n：指数列的下标

非递归实现

/**
 * 斐波那契数列 非递归实现
 *
 * @param int $n  斐波那契数列个数
 * @return array
 */
function fib($n){
    // 判断传入的数字是否小于0
    if($n <= 0){
        return 0;
    }

    // 设置数列前两个值
    if($n == 1 || $n == 2){
        return 2;
    }

    $array = [];
    $array[0] = 1;      // 数量第一个数
    $array[1] = 1;      // 数列第二个数

    // 从数列第三值开始循环
    for($i=2; $i<$n; $i++){
        // 后面的值等于前两个值的和
        $array[$i] = $array[$i-1] + $array[$i-2];
    }

    return $array;
}

print_r(fib(10));

// Array ( [0] => 1 [1] => 1 [2] => 2 [3] => 3 [4] => 5 [5] => 8 [6] => 13 [7] => 21 [8] => 34 [9] => 55 )

递归实现

function fib_recursive($n){ 
    // 判断传入的数字是否小于0
    if($n <= 0){
        return 0;
    }

    if($n == 1 || $n == 2){
        return 1;
    }

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

  } 

// 输出数列个数
$total = 10;
// 循环输出数列中的值
for($i = 1; $i<=$total;$i++){
    echo fib_recursive($i) . ' ';
}

// 1 1 2 3 5 8 13 21 34 55