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

作者: 温新

分类: 【PHP算法题】

阅读: 1844

时间: 2020-04-07 06:41:03

神奇的兔子数列 假设笫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

通过 echo fib_recursive(10) 方式调用是直接输出对应的值 55

我是夕阳何处寻,期待和优秀的你一起同行!

夕阳何处寻

2020年04月07日

请登录后再评论