第一次瀏覽的時(shí)候剛開(kāi)始學(xué)C++的時(shí)候，當(dāng)時(shí)的課設(shè)是《C++ & SQL 2008的學(xué)生管理系統(tǒng)》，C++作前段界面、邏輯處理，SQL作為后端服務(wù)器支持的題目，當(dāng)時(shí)不太認(rèn)真學(xué)習(xí)，上課只顧著玩手機(jī)，快結(jié)課了才想著趕作業(yè)，當(dāng)時(shí)就百度了這個(gè)課設(shè)題目，恰好點(diǎn)進(jìn)了一個(gè)博主的文章（具體是哪篇已經(jīng)不太記得了，只記得是Visual Studio 2010 + (C++) + SQL的開(kāi)發(fā)環(huán)境）。在此之前感覺(jué)寫(xiě)代碼好像也就是把人算數(shù)學(xué)題的過(guò)程變成了代碼算數(shù)學(xué)題的邏輯，當(dāng)然大一大二兩年也是沒(méi)怎么學(xué)編程，導(dǎo)致基礎(chǔ)賊爛😭
從大三開(kāi)始進(jìn)實(shí)驗(yàn)室慢慢補(bǔ)基礎(chǔ)，學(xué)東西才意識(shí)到編程這玩意只看書(shū)，應(yīng)付考試拿分沒(méi)意義，還得是多敲鍵盤(pán)。
第一次在這寫(xiě)文章，是大三進(jìn)實(shí)驗(yàn)室的時(shí)候，網(wǎng)上看到Vscode的界面比VS好看多了，就跟著搭環(huán)境，這不會(huì)那不會(huì)，當(dāng)時(shí)折騰了一天，想著那么難搞就記錄下來(lái)，生怕之后換電腦了又不會(huì)整了。也是這一次開(kāi)始接觸Markdown語(yǔ)言😁，確實(shí)好用
恰好，偷懶多天后又練習(xí)了一哈哈代碼，記錄一哈😍
| 斐波那契數(shù)列題目
寫(xiě)一個(gè)函數(shù)，輸入 n，求斐波那契（Fibonacci）數(shù)列的第 n 項(xiàng)（即
F
(
N
)
F(N)
F(N) ）。斐波那契數(shù)列的定義如下：
F
0
=
0
,
F
1
=
1
F_0 = 0, F_1 = 1
F0?=0,F1?=1
F
N
=
F
N
?
1
+
F
N
?
2
,
N
>
1
F_N = F_{N - 1} + F_{N - 2}, N >1
FN?=FN?1?+FN?2?,N>1
斐波那契數(shù)列由 0 和 1 開(kāi)始，之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出。
答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008，請(qǐng)返回 1。
示例 1：
示例 2：
思路
遞歸法
很常見(jiàn)的遞歸解題法，因?yàn)閺牡谌?xiàng)開(kāi)始，每一項(xiàng)都是前兩項(xiàng)的和，所以可以將問(wèn)題分解成每個(gè)項(xiàng)的求值再相加，也就得到了遞歸的總思想，下面按照遞歸三部曲確定算法流程
確定遞歸函數(shù)的參數(shù)列表：
每一次遞歸要計(jì)算的每一項(xiàng)的數(shù)值，所以參數(shù)列表應(yīng)該代表著當(dāng)前求值項(xiàng)，那么參數(shù)就是下標(biāo)Nint Fibonacci1(int N)
確定遞歸函數(shù)的終止條件：
遞歸也是一個(gè)遍歷的過(guò)程，而遍歷肯定有邊界，對(duì)于本題來(lái)說(shuō)，邊界就是[0, n]，那么終止條件就是下標(biāo)N達(dá)到邊界時(shí)即停止
重慶分公司
重慶分公司
if (0 == N)
{return 0;
}
if (1 == N)
{return 1;
}確定遞歸函數(shù)的單層遞歸邏輯
單層邏輯要求的是項(xiàng)值，而每一項(xiàng)又等于前兩項(xiàng)的和，這就是本題中的單層遞歸邏輯
return Fibonacci1(N - 1) + Fibonacci1(N - 2);以求
f
5
f_5
f5?為例子，框圖如下
圖中可以看出，綠色節(jié)點(diǎn)代表著首次計(jì)算，藍(lán)色節(jié)點(diǎn)代表著已知節(jié)點(diǎn)，粉色節(jié)點(diǎn)代表著重復(fù)計(jì)算，每個(gè)節(jié)點(diǎn)的時(shí)間消耗為
O
(
1
)
O(1)
O(1)，而二叉樹(shù)的節(jié)點(diǎn)數(shù)為
O
(
2
n
)
O(2^n)
O(2n)，所以時(shí)間復(fù)雜度為
O
(
2
n
)
O(2^n)
O(2n)
遞歸進(jìn)階法
上面提到了常規(guī)的遞歸法會(huì)導(dǎo)致多余的資源浪費(fèi)，當(dāng)N足夠大的時(shí)候，計(jì)算的時(shí)間和資源開(kāi)銷(xiāo)會(huì)很大，如果把這些重復(fù)計(jì)算的資源省略掉，就可以進(jìn)一步減少算法的時(shí)間開(kāi)銷(xiāo)，因?yàn)橹貜?fù)計(jì)算的項(xiàng)的值都是一樣的，那么只要判斷當(dāng)前項(xiàng)是否已經(jīng)計(jì)算過(guò)，如果計(jì)算過(guò)了則直接從之前的結(jié)果中取出即可，這樣就可以節(jié)省重復(fù)項(xiàng)的計(jì)算時(shí)間
同理下面按照遞歸三部曲確定算法流程
確定遞歸函數(shù)的參數(shù)列表
與常規(guī)遞歸法不同的是，進(jìn)階法需要保存之前計(jì)算過(guò)的項(xiàng)值，所以需要增加一個(gè)數(shù)組用來(lái)保存這些值int Fibonacci2(int N, vector
確定遞歸函數(shù)的終止條件：
這一塊跟常規(guī)遞歸法沒(méi)有什么差異，保持一致
確定遞歸函數(shù)的單層遞歸邏輯
與常規(guī)遞歸法相比，增加了重復(fù)項(xiàng)的對(duì)比流程
if (0 != Arr[N])
{return Arr[N];
}
return Fibonacci2(N - 1, Arr) + Fibonacci2(N - 2, Arr);以求
f
5
f_5
f5?為例子，框圖如下
與常規(guī)遞歸法對(duì)比，灰色節(jié)點(diǎn)代表已經(jīng)計(jì)算過(guò)的值，不需要進(jìn)行計(jì)算，那么實(shí)際的調(diào)用次數(shù)就只剩下左邊綠色節(jié)點(diǎn)和藍(lán)色節(jié)點(diǎn)，這樣時(shí)間復(fù)雜度就從
O
(
2
n
)
O(2^n)
O(2n) 降到
O
(
n
)
O(n)
O(n)，但是因?yàn)槭褂昧祟~外的數(shù)組進(jìn)行保存值，所以空間復(fù)雜度由原來(lái)的
O
(
1
)
O(1)
O(1) 升到
O
(
n
)
O(n)
O(n)，這就是算法中常見(jiàn)的空間換時(shí)間策略
動(dòng)態(tài)規(guī)劃
既然有遞歸，那么迭代法也跑不掉。
從第二項(xiàng)開(kāi)始，每一項(xiàng)都等于前兩項(xiàng)和，那么可以迭代的把遍歷過(guò)的所有項(xiàng)進(jìn)行計(jì)算，就可以得到最后一項(xiàng)的值了
f
2
=
f
0
+
f
1
f_2 = f_0 + f_1
f2?=f0?+f1?
f
3
=
f
1
+
f
2
=
f
1
+
(
f
0
+
f
1
)
f_3 = f_1 + f_2 = f_1 + (f_0 + f_1)
f3?=f1?+f2?=f1?+(f0?+f1?)
f
4
=
f
2
+
f
3
=
(
f
0
+
f
1
)
+
(
f
1
+
(
f
0
+
f
1
)
)
f_4 = f_2 + f_3 = (f_0 + f_1) + (f_1 + (f_0 + f_1))
f4?=f2?+f3?=(f0?+f1?)+(f1?+(f0?+f1?))
.
.
.
.
.
.
......
......
那么只需要保存記錄好遍歷到的每一項(xiàng)的前兩項(xiàng)值，并做結(jié)果累加就能模擬出上面式子的過(guò)程，具體算法流程如下
1. 先記錄保存首項(xiàng)和次項(xiàng)值
f
0
,
f
1
f_0, f_1
f0?,f1?
2. 從第二項(xiàng)開(kāi)始遍歷，遍歷到的項(xiàng)值等于其前兩項(xiàng)的和
3. 遍歷到最后一項(xiàng)，結(jié)束遍歷返回結(jié)果值
以上算法唯一需要思考的是第二步，要怎么計(jì)算當(dāng)前遍歷項(xiàng)的值？
可以申請(qǐng)一個(gè)長(zhǎng)度為N的數(shù)組，保存之前的每一項(xiàng)值，那么該算法的空間復(fù)雜度就跟N有關(guān)，為
O
(
n
)
O(n)
O(n)，仔細(xì)思考其實(shí)要保存的只是當(dāng)前遍歷項(xiàng)的前兩項(xiàng)，而已經(jīng)遍歷后的項(xiàng)的前兩項(xiàng)值其實(shí)并不關(guān)心，所以只需要申請(qǐng)兩個(gè)變量保存當(dāng)前遍歷項(xiàng)的前兩項(xiàng)值即可，空間復(fù)雜度也降為
O
(
n
)
O(n)
O(n)
代碼
int Fibonacci1(int i_uNum)
{if (0 >i_uNum)
{return -1;
}
else if (0 == i_uNum)
{return 0;
}
else if (1 == i_uNum)
{return 1;
}
return Fibonacci1(i_uNum - 1) + Fibonacci1(i_uNum - 2);
}
int Fibonacci2(int i_uNum, vector& i_uArr)
{if (0 >i_uNum)
{return -1;
}
else if (0 == i_uNum)
{return 0;
}
else if (1 == i_uNum)
{return 1;
}
if (0 != i_uArr[i_uNum])
{return i_uArr[i_uNum];
}
return Fibonacci2(i_uNum - 1, i_uArr) + Fibonacci2(i_uNum - 2, i_uArr);
}
int Fibonacci3(int i_uNum)
{if (0 >i_uNum)
{return -1;
}
else if (0 == i_uNum)
{return 0;
}
else if (1 == i_uNum)
{return 1;
}
int Fir = 0, Sec = 1;
for (int i = 2; i<= i_uNum; i++)
{int tmp = Fir;
Fir = Sec;
Sec = tmp + Sec;
}
return b;
}
小結(jié)
進(jìn)階遞歸和動(dòng)態(tài)規(guī)劃的本質(zhì)思想是一致的，區(qū)別在于：
希望以后能好好學(xué)習(xí)，接觸更多的新東西，賺大錢(qián)😶
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
