PHP 零基础入门笔记(14):编程思想

编程思想

编程思想:利用数学模式,来解决对应的需求问题,然后利用代码实现对象的数据模型

算法:使用代码实现对应的数学模型,从而解决对应的业务问题

递推算法

是一种简单的算法,即通过已知条件,利用特定关系得出中间结论,直至得到结果的算法

递推算法的分类:

顺推 通过最简单的条件(已知),然后逐步推演结果

逆推 通过结果找到规律,然后推到已知条件

递推思想:菲波那切数列

<?php
// 1 1 2 3 5 8 13...
// 规律 第一个数为1,第二个数为1,第三个数开始为前两数之和
// n(3) = n(2) + n(1);
$f[1] = 1;
$f[2] = 1;
$n = 5;
for($i = 3; $i <= $n; $i++){
    $f[$i] = $f[$i - 1] + $f[$i - 2];
}
echo json_encode($f);
// {"1":1,"2":1,"3":2,"4":3,"5":5}

封装为函数

<?php
// 1 1 2 3 5 8 13...
// 规律 第一个数为1,第二个数为1,第三个数开始为前两数之和
// n(3) = n(2) + n(1);
function fibonacci($n){
    // 判断为第一个或第二个直接返回
    if($n == 2 || $n == 2){return 1;}
    $f[1] = 1;
    $f[2] = 1;
    for($i = 3; $i <= $n; $i++){
        $f[$i] = $f[$i - 1] + $f[$i - 2];
    }
    // 返回最后一个
    return $f[$n];
}
echo fibonacci(7);
// 13

递归算法

把问题转化为规模缩小了的同类问题的子问题,然后递归调用函数(或过程)来表示问题的解

简化问题:找到最优子问题(不能再小)

自己调用自己

例如:菲波那切数列

F(N) = F(N - 1)  + F(N - 2)
F(N - 1) = F(N - 2) + F(N - 3)
...
F(2) = F(1) = 1

重要点:

递归点:发现当前问题可以有解决当前问题的函数,去解决规模比当前小一点的问题来解决

F(N) = F(N - 1)  + F(N - 2)

递归出口:当问题解决的时候,已经到达(必须有)最优子问题,不能再次调用函数

没有递归出口就是死循环

递归的本质是利用空间换时间

<?php
function fibonacci($n){
    // 递归出口
    if($n == 1 || $n == 2){
        return 1;
    }
    // 递归点:大问题变为小问题处理
    return fibonacci($n - 1) + fibonacci($n + 1);
}