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