​​​​ 斐波那契数列 | 苏生不惑的博客

斐波那契数列

发表于 | 次
| 字数统计: 421 字 | 阅读时长 ≈ 2 分钟

本来来自laravel-chinar

普通递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function fibonacci_recursive($n) {
    if ($n <= 1) {
        return 1;
    }

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

for ($i = 1; $i <= 30; $i++) {
   echo fibonacci_recursive($i) . "  ";
}

耗时
3.52s user 0.00s system 99% cpu 3.521 total

递归优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function fibonacci_recursive_optimization($n) {
    static $caches_arr = [];

    if (isset($caches_arr[$n])) {
        return $caches_arr[$n];
    }

    if ($n <= 1) {
        $res = 1;
    } else {
        $res = fibonacci_recursive_optimization($n - 1) + fibonacci_recursive_optimization($n - 2);
    }

    $caches_arr[$n] = $res;

    return $res;
}

for ($i = 1; $i <= 30; $i++) {
    echo fibonacci_recursive_optimization($i) . "  ";
}

耗时
0.01s user 0.01s system 98% cpu 0.022 total

闭包实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function fibonacci_closure() {
    static $x = 0;
    static $y = 1;
    return function () use (&$x, &$y) {
        [$x, $y] = [$y, $x + $y];
        return $y;
    };
}

$f = fibonacci_closure();
for ($i = 1; $i <= 30; $i++) {
    echo $f() . " ";
}

耗时
0.02s user 0.01s system 99% cpu 0.030 total

while循环

1
2
3
4
5
6
7
8
9
function getNum($n) {
    $num = 0;
    $pre = 1;
    while ($n--) {
        $num += $pre;
        $pre = $num - $pre;
    }
    return $num;
}

上台阶问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
有个人想上一个 50 级的台阶，每次只能迈 1 级或者迈 2 级台阶，问：这个人有多少种方法可以把台阶走完？例如：总共 3 级台阶，可以先迈 1 级再迈 2 级，或者先迈 2 级再迈 1 级，或者迈 3 次 1 级总共 3 中方式。

当我们走到第 50 层的时候，最后有两种选择，从 49 开始迈 1 级或者从 48 开始迈 2 级。那么到达 50 层的走法等于到达 49 层的走法 + 到达 48 层的走法，以此类推，可以得到总的走法符合斐波那契数列，我们的代码就好写了

function digui($int)
{
    if ($int == 1) {
        return $int;
    }
    if ($int == 2) {
        return $int;
    }
    return digui($int - 1) + digui($int - 2);
}
dump(digui(50));
https://learnku.com/articles/29920

算法网精品文