APP
編程思想
編程思想：利用數(shù)學(xué)模式，來(lái)解決對(duì)應(yīng)的需求問(wèn)題，然后利用代碼實(shí)現(xiàn)對(duì)象的數(shù)據(jù)模型
算法：使用代碼實(shí)現(xiàn)對(duì)應(yīng)的數(shù)學(xué)模型，從而解決對(duì)應(yīng)的業(yè)務(wù)問(wèn)題
遞推算法
是一種簡(jiǎn)單的算法，即通過(guò)已知條件，利用特定關(guān)系得出中間結(jié)論，直至得到結(jié)果的算法
遞推算法的分類：
- 順推 通過(guò)最簡(jiǎn)單的條件（已知），然后逐步推演結(jié)果
- 逆推 通過(guò)結(jié)果找到規(guī)律，然后推到已知條件
遞推思想：菲波那切數(shù)列
// 1 1 2 3 5 8 13...
// 規(guī)律 第一個(gè)數(shù)為1，第二個(gè)數(shù)為1，第三個(gè)數(shù)開(kāi)始為前兩數(shù)之和
// 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}
封裝為函數(shù)
// 1 1 2 3 5 8 13...
// 規(guī)律 第一個(gè)數(shù)為1，第二個(gè)數(shù)為1，第三個(gè)數(shù)開(kāi)始為前兩數(shù)之和
// n(3) = n(2) + n(1);
function fibonacci($n){
// 判斷為第一個(gè)或第二個(gè)直接返回
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];
}
// 返回最后一個(gè)
return $f[$n];
}
echo fibonacci(7);
// 13
遞歸算法
把問(wèn)題轉(zhuǎn)化為規(guī)?？s小了的同類問(wèn)題的子問(wèn)題，然后遞歸調(diào)用函數(shù)（或過(guò)程）來(lái)表示問(wèn)題的解
- 簡(jiǎn)化問(wèn)題：找到最優(yōu)子問(wèn)題（不能再?。?/li>
- 自己調(diào)用自己
例如：菲波那切數(shù)列
F(N) = F(N - 1) + F(N - 2)
F(N - 1) = F(N - 2) + F(N - 3)
...
F(2) = F(1) = 1
重要點(diǎn)：
- 遞歸點(diǎn)：發(fā)現(xiàn)當(dāng)前問(wèn)題可以有解決當(dāng)前問(wèn)題的函數(shù)，去解決規(guī)模比當(dāng)前小一點(diǎn)的問(wèn)題來(lái)解決
F(N) = F(N - 1) + F(N - 2)
- 遞歸出口：當(dāng)問(wèn)題解決的時(shí)候，已經(jīng)到達(dá)（必須有）最優(yōu)子問(wèn)題，不能再次調(diào)用函數(shù)
沒(méi)有遞歸出口就是死循環(huán)
遞歸的本質(zhì)是利用空間換時(shí)間
function fibonacci($n){
// 遞歸出口
if($n == 1 || $n == 2){
return 1;
}
// 遞歸點(diǎn)：大問(wèn)題變?yōu)樾?wèn)題處理
return fibonacci($n - 1) + fibonacci($n + 1);
}
本文摘自 ：https://blog.51cto.com/u
