0基礎演算法基礎學演算法 第八彈 遞歸進階，dfs第一講

  • 2020 年 8 月 22 日
  • 筆記

　　最近很有一段時間沒有更新了，主要是因為我要去參加一個重要的考試—-小升初！作為一個武漢的兢兢業業的小學生當然要去試一試我們那裡最好的幾個學校的考試了，總之因為很多的原因放了好久的鴿子，不過從今天開始我要回歸正軌了，以後基本上都是每周更一篇（註：不是每周一篇0基礎演算法系列，可能是學習筆記），因為馬上我也要去報道了！

———–正文分割線————

　　·之前我早就在第六彈就講述過關於遞歸的內容（//www.cnblogs.com/qj-Network-Box/p/12729230.html）今天我們要講的dfs便是遞歸的一種拓展應用，dfs中文全名叫做深度優先搜索，至於什麼是深度優先搜索其實也不好解釋，所以我們可以在例題中弄明白，dfs的原理就是利用遞歸的特性，函數套函數，層層遞進，越搜越深，這也是它名字的來歷，現在我們可以開始我們的第一個示例

一，有1 2 3三個數字卡片放進a b c三個盒子里，有哪些排列組合方法

　　這道題有好幾種做法，比較常規的做法是枚舉各種情況，比較簡單易懂，循環就完了嘛，循環三次，枚舉三個數，每次都枚舉1-3的數字卡片，分別裝入a b c的盒子里，程式碼如下

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     int k=1;//第三個數 
 5     for(int i=1;i<=3;i++)
 6     for(int j=1;j<=3;j++)//篩前兩個數 
 7     {
 8         if(j!=i)
 9         {
10             while(k==i||k==j)//篩第三個數 
11             {
12                 k++;
13                 k=k%3+1;//免得k出現大於等於4的情況    
14             } 
15             cout<<i<<" "<<j<<" "<<k<<endl;//輸出 
16         }
17     }
18     return 0;
19 }

運行結果也很明了

可以看到最後一共六種結果，分別是123 132 213 231 312和321；

這樣做當然是可以輕易做出來，但要是不只是有三個球三個盒子呢，如果是100000個球，100000個盒子呢，那就得寫100000個循環了，同時if語句也是少不了的，這樣一寫得寫到猴年馬月啊，因此這肯定是不可能的，這時候就得請出搜索家族中的dfs，深度優先搜索了

一，dfs解「有1 2 3三個數字卡片放進a b c三個盒子里，有哪些排列組合方法」

　　寫搜索前非常重要的一個步驟是要提前理好思路，如果不太清楚如何整理思路，可以看看我的第一彈(//www.cnblogs.com/qj-Network-Box/p/12502643.html),按照我的習慣我一般會畫一個流程圖理清思路，如下圖

流程圖可以幫我們理好思路，接下來是我們的程式碼部分

#include <bits/stdc++.h>
using namespace std;
int a[3];
int b[3];//a是盒子，b是卡片,true表示在手上，false表示不再 
void dfs(int k)
{
    if(k==4)//如果他站在了「第四個」盒子前 
    {
        for(int i=1;i<=3;i++) cout<<a[i]<<" ";
        cout<<endl;
        return;//返回上一步 
    } 
    for(int i=1;i<=3;i++)
    {
        if(b[i]==0)
        {
            a[k]=i;//在a[k]的盒子中裝入撲克牌i 
            b[i]=1;//b[i]的卡片已經放在盒子里的 
            dfs(k+1);//遞歸繼續搜下一個盒子 
            b[i]=0;//卡片記得拿回來，搜索剩下的組合時還要用的 
        } 
    } 
 } 
int main(){
    dfs(1);//直接調用 
    return 0; 
}

運行結果完全正確

結果完全正確

看到這裡，很多人會感到很不解，明明套幾個循環就可以解決的東西，為什麼要這樣大費周章地整那麼麻煩的遞歸呢？這道題我們的目的並不是把他真的做出來，而是為了引入這樣的概念，況且就像我前面說的，這只是三個數三個盒子，如果是100000個數，100000個盒子呢？那樣就只能選擇使用dfs的方法了，接下來我再給大家看一道」簡單「的題（不太熟練者慎入，這個題大概還要等2-3彈後才會涉及的難度）

二，洛谷題單 八皇后

#include<bits/stdc++.h>
using namespace std;
int n, a[50], sum;
bool book[4][50];
void dfs(int i)
{
    int j;
    if(i>n)
    {
        sum++;
        if(sum>3) return ;
        for(int i=1;i<=n;i++)    cout<<a[i]<<" ";
        cout<<endl;
        return ;
    }

    for(j=1;j<=n;j++)
        if( !book[1][j] && (!book[2][i+j]) && (!book[3][i-j+n]) )
    {
        a[i] = j;
        book[1][j] = 1;
        book[2][i+j] = 1;
        book[3][i-j+n] = 1;
        dfs(i+1);
        book[1][j] = 0;
        book[2][i+j] = 0;
        book[3][i-j+n] = 0;
    }
}

int main()
{
    cin>>n;
    dfs(1);
    cout<<sum;
    return 0;
}

上面是一種解決方式的程式碼，用的就是dfs，但是裡面涉及了一些後兩彈會說的一些pmn的內容，到那時候我會以八皇后為例題講解，關注了我後敬請期待吧！

　　第八彈 dfs第一講算是結束了，以後還有第九彈 dfs2，第十彈 dfs3，如果覺得我講的還不錯，就麻煩您動動手指，點贊👍關注➕，如果您沒有cnblogs的帳號，也可以加入QQ群，群號1031457671，或者使用鏈接加入群聊 //jq.qq.com/?_wv=1027&k=poupnxU3，群里有豐富資源、電子書，同時也歡迎大家進群交流分享自己的電子書，歡迎各位進群！

 

　　

 

VirMach 便宜 VPS

QNews

QNews