PHP实现斐波那契数列

斐波那契数列形式

[1,1,2,3,5,8,13,21,34,55 ...]

概念

前两个数都是1，从第三个数开始，当前数的值等于前两个数的和。
Fn = F(n-1) + F(n-2)

代码展示

<?php
/**
 * Created by PhpStorm.
 * User: liufeng
 * Date: 2019/12/4
 * Time: 11:14
 */

function fbnq0($n)
{
    if ($n < 3) return 1;

    $arr[0] = $arr[1] = 1;

    for ($i = 2; $i < $n; $i++) {
        $arr[$i] = $arr[$i - 1] + $arr[$i - 2];
    }

    return $arr;
}

function fbnq1($n)
{
    if ($n < 3) return 1;

    $i = $j = 1;

    for ($k = 3; $k <= $n; $k++) {
        $value = $i + $j;
        $i = $j;
        $j = $value;
    }
    return $value;
}

function fbnq2($n)
{
    if ($n < 3) return 1;

    return fbnq2($n - 1) + fbnq2($n - 2);
}

// 尾递归
function fbnq3($first, $second, $n)
{
    if ($n < 3) return 1;

    if ($n == 3)
        return $first + $second;

    return fbnq3($second, $first + $second, $n - 1);
}

echo '<pre>';

/**************  计算使用时间  ******************/
$start_time = microtime(true);

$num = 10;
print_r(fbnq0($num));
echo '<br>';
echo fbnq1($num);
echo '<br>';
echo fbnq2($num);
echo '<br>';
echo fbnq3(1, 1, $num);

$end_time = microtime(true);

echo '<hr>脚本执行时间 = ' . (($end_time - $start_time) * 1000 * 1000) . ' 微秒';