当前位置:首页 > IT技术 > Web编程 > 正文

PHP 零基础入门笔记(14):编程思想
2022-04-29 13:49:34


编程思想

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

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

递推算法

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

递推算法的分类:

  • 顺推 通过最简单的条件(已知),然后逐步推演结果
  • 逆推 通过结果找到规律,然后推到已知条件

递推思想:菲波那切数列

<?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

递归算法

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

  1. 简化问题:找到最优子问题(不能再小)
  2. 自己调用自己

例如:菲波那切数列

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);
}



本文摘自 :https://blog.51cto.com/u

开通会员,享受整站包年服务立即开通 >