個(gè)人主頁(yè)：??在肯德基吃麻辣燙
我的gitee：C++倉(cāng)庫(kù)
個(gè)人專(zhuān)欄：C++專(zhuān)欄

前言

從本文開(kāi)始進(jìn)入遞歸，搜索與回溯算法專(zhuān)題講解。

一、名詞解釋

1、什么是遞歸？

遞歸就是函數(shù)自己調(diào)用自己。

2、為什么會(huì)用到遞歸？

遞歸的本質(zhì)是：

主問(wèn)題：—>相同的子問(wèn)題
子問(wèn)題：—>相同的子問(wèn)題

3、如何理解遞歸？

通過(guò)：

• 1）通過(guò)遞歸的細(xì)節(jié)展開(kāi)圖（前期可以，過(guò)了前期一定不能再用了）
• 2）通過(guò)二叉樹(shù)中的題目
• 3）宏觀(guān)看待遞歸問(wèn)題（重要）

越往后學(xué)越發(fā)現(xiàn)，如果只抓住遞歸的細(xì)節(jié)展開(kāi)圖，你會(huì)發(fā)現(xiàn)你根本就學(xué)不好遞歸這個(gè)東西，遞歸的細(xì)節(jié)展開(kāi)圖只是為了輔助你讀過(guò)新手期，如果你后面還在用它，那么你往往是學(xué)不好遞歸的。

那么：如何理解宏觀(guān)看待遞歸問(wèn)題這個(gè)點(diǎn)呢？

可以分為幾個(gè)部分：

• • 1）不要再在意遞歸的細(xì)節(jié)展開(kāi)圖
• • 2）把遞歸的函數(shù)當(dāng)成一個(gè)黑盒子
• • 3）相信這個(gè)黑盒子一定能完成這個(gè)任務(wù)

4、如何寫(xiě)好遞歸？

寫(xiě)好一個(gè)遞歸也分為三點(diǎn)：

• 1）先找到相同的子問(wèn)題（函數(shù)頭的設(shè)計(jì)）
• 2）只關(guān)心某一個(gè)子問(wèn)題是如何解決的（函數(shù)體的書(shū)寫(xiě)）
• 3）遞歸出口

二、搜索vs深度優(yōu)先遍歷vs深度優(yōu)先搜索vs寬度優(yōu)先遍歷vs寬度優(yōu)先搜索vs暴搜

1、深度優(yōu)先遍歷vs深度優(yōu)先搜索

其實(shí)，一句話(huà)就能概括下來(lái)：
遍歷是形式，搜索是目的。

所以，我們平時(shí)說(shuō)的深度優(yōu)先遍歷和深度優(yōu)先搜索，其實(shí)他們倆是一樣的。
都可以叫做dfs。

2、寬度優(yōu)先遍歷vs寬度優(yōu)先搜索

其實(shí)，一句話(huà)就能概括下來(lái)：
遍歷是形式，搜索是目的。

所以，我們平時(shí)說(shuō)的寬度優(yōu)先遍歷和寬度優(yōu)先搜索，其實(shí)他們倆是一樣的。
都可以叫做bfs。

3、關(guān)系圖

我們所說(shuō)的搜索，其實(shí)就是暴搜。

4. 搜索問(wèn)題的拓展

我們剛開(kāi)始學(xué)習(xí)搜索時(shí)，總以為dfs和bfs這兩個(gè)搜索都只與二叉樹(shù)有關(guān)。其實(shí)不然。
從下面的例題開(kāi)始你會(huì)發(fā)現(xiàn)，很多東西都能使用dfs進(jìn)行求解。

三、回溯與剪枝

這兩個(gè)名詞聽(tīng)起來(lái)貌似很高大上，其實(shí)用一個(gè)例子就能解釋清楚了。

下面來(lái)看一個(gè)迷宮問(wèn)題：

入口和出口如上：我們從入口出發(fā)，往右邊走遇到墻壁之后，往下走。走到藍(lán)色標(biāo)記，也就是拐角點(diǎn)的地方后，這就是一個(gè)岔路口，此時(shí)我們有兩種選擇：

• 1）往左邊走
• 2）往右邊走

當(dāng)我們選擇往左邊走時(shí)，如下圖：

會(huì)遇到墻壁，此時(shí)我們就需要原路返回。

這個(gè)從某一位置出發(fā)，一條道走到黑，再沿著原路返回的過(guò)程，就叫做回溯。

回溯的這條路徑，我們用綠色來(lái)標(biāo)記。

此時(shí)又走到了藍(lán)色拐點(diǎn)，在這個(gè)岔路口我們有三種選擇：
1）往上走
2）往左走
3）往右走

可是，我們最初是從上面下來(lái)的，然后沿著左邊走，走不通之后再返回來(lái)的。
所以，我們只有一個(gè)選擇：往右走。

而這個(gè)判斷的過(guò)程，也就是選擇路徑的過(guò)程，就叫做剪枝。

將往上走的路徑剪掉，將往左走的路徑剪掉，就是剪枝。

四、專(zhuān)題一

1. 漢諾塔問(wèn)題

點(diǎn)我直達(dá)

算法分析

1.找到相同的子問(wèn)題：

當(dāng)n = 1時(shí)：

直接將盤(pán)子從A柱子挪到C柱子即可。

當(dāng)n = 2 時(shí)

分為三步走：

1）我們需要將盤(pán)子a上面的盤(pán)子借助C柱子移動(dòng)到B柱子。

2）將a盤(pán)子移動(dòng)到C柱子上

3）將B柱子上的所有盤(pán)子借助A盤(pán)子移動(dòng)到C柱子上。

當(dāng)n = 3 時(shí)

與第二步相同：
分為三步走
1）將a盤(pán)子上面的所有盤(pán)子借助C柱子移動(dòng)到B柱子上。

2）將a盤(pán)子移動(dòng)到C柱子上。

3）將B柱子上面的所有盤(pán)子借助A柱子移動(dòng)到C柱子上。

2.只關(guān)心某一個(gè)子問(wèn)題如何解決。

所以我們會(huì)發(fā)現(xiàn)，當(dāng)n >= 2時(shí)，都會(huì)執(zhí)行相同的子問(wèn)題的操作。操作如下：

• 1）將a盤(pán)子上面的所有盤(pán)子通過(guò)C柱子挪到B柱子上。
• 2）將a盤(pán)子挪到C盤(pán)子上。
• 3）將B柱子上面的所有盤(pán)子挪到C柱子上。

在這整個(gè)過(guò)程中，你要相信一件事情：
你交給dfs這個(gè)函數(shù)的任務(wù)是：

我要把所有盤(pán)子全部借助一個(gè)柱子挪到另一個(gè)柱子上。

并且要相信dfs這個(gè)函數(shù)一定能完成這個(gè)任務(wù)。

這就是宏觀(guān)看待問(wèn)題的思路。

3.遞歸出口
遞歸出口就是當(dāng)n = 1時(shí)，你會(huì)發(fā)現(xiàn)跟當(dāng)n = 其他數(shù)的操作步驟是不一樣的。
當(dāng)n = 1時(shí)，直接將a盤(pán)子移動(dòng)到C柱子即可。

代碼編寫(xiě)

class Solution {
public:
//1.重復(fù)的子問(wèn)題（函數(shù)頭）
//要將A柱子上面的所有盤(pán)子借助B柱子全部轉(zhuǎn)移到C柱子上面

//2.只關(guān)心某一個(gè)子問(wèn)題在做什么（函數(shù)體）

//3.遞歸出口

    void dfs(vector<int>& A, vector<int>& B, vector<int>& C,int n) 
    {
        if(n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }

        dfs(A,C,B,n-1);
        C.push_back(A.back());
        A.pop_back();
        dfs(B,A,C,n-1);
    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        int n = A.size();
        dfs(A,B,C,n);
    }
};

總結(jié)

提示：這里對(duì)文章進(jìn)行總結(jié)：

本文章詳細(xì)講解了遞歸，搜索與回溯算法的入門(mén)理解級(jí)操作，以及通過(guò)一道例題感受一下dfs這種算法的強(qiáng)大之處，關(guān)鍵在于dfs寫(xiě)起來(lái)特別簡(jiǎn)單。

學(xué)好dfs，是進(jìn)入大廠(chǎng)的必備技能。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-705211.html

到了這里，關(guān)于【C++】遞歸，搜索與回溯算法入門(mén)介紹和專(zhuān)題一講解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！