HDOJ.1342 Lotto （DFS）

2019-11-14 12:07:05

字體：大中小

來源：轉載

供稿：網友

Lotto [從零開始DFS(0)]

點我挑戰題目

從零開始DFS HDOJ.1342 Lotto [從零開始DFS(0)] — DFS思想與框架/雙重DFS HDOJ.1010 Tempter of the Bone [從零開始DFS(1)] —DFS四向搜索/奇偶剪枝 HDOJ(HDU).1015 Safecracker [從零開始DFS(2)] —DFS四向搜索變種 HDOJ(HDU).1016 PRime Ring Problem (DFS) [從零開始DFS(3)] —小結：做DFS題目的關注點 HDOJ(HDU).1035 Robot Motion [從零開始DFS(4)]—DFS題目練習 HDOJ(HDU).1241 Oil Deposits(DFS) [從零開始DFS(5)] —DFS八向搜索/雙重for循環遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開始DFS(７)]—DFS練習/check函數的思想

題意分析

給出k（6 < k < 13)個數字，要求從這k個數字中選出升序的6個數字，并且按照字典序輸出全部的可能，給出的k個數字已經按照升序排列好。乍一看以為是排列組合，怎么想也想不到是用dfs來解決。按照這個數字選或者不選的邏輯，以為是dp什么的。最后看了題解才知道用dfs的方法做，也算是長見識了。作為dfs的第一道題，好好寫，紀念一下。 dfs一般采用遞歸寫法，或許是相比于bfs更加好寫吧，所以能用dfs寫的都用dfs了。既然是深度優先，思路就是沿著一條路一直走，直到走到死胡同，原路返回，返回到有多條道路的地方換其他路走。直到這條支路全部都訪問過了，按照原路返回，回到起點，如果起點還有別的支路，那么繼續訪問，反之結束整個搜索過程。

這里寫圖片描述（圖1-1）

Tip:數字為訪問順序，紅色代表前進的過程，藍色代表返回的過程。這里可以看到，是永遠先訪問上邊的節點，其次是下面的節點。

Tiip:故意畫成樹的樣子，樹也是一張圖呀。

實際解題的時候不可能無所約束的搜索下去，原因之一是會超時(TLE),原因之二就是沒有那個必要。那么就需要減小搜索的規模，俗稱剪枝。個人的理解是，當搜索到某一步的時候，繼續搜索下去的解，明顯不滿足題目的要求時，終止這次搜索。

這里寫圖片描述（圖1-2）

Tip:如圖，綠色節點均為不滿足題意的解，那么當我搜索到綠色箭頭所指向的點的時候，就沒必要繼續往下搜索了，即后續的3、4、5、6、7、8步驟均為多余的。

Tiip:由此可見，當數據規模非常大的時候，剪枝可以顯著提高程序運行的效率。有時候沒剪枝T了，剪枝就AC了。

回到本題。對于給定數字，面臨的選擇就是選或者不選，是不是和上面的樹邏輯上很相似。先上代碼，揉碎了慢慢寫。。

代碼總覽

/* Title:HDOJ.1342 Author:pengwill Date:2017-2-3*/#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;int a[20],b[10],n;void dfs(int num, int pos){ if(num == 7){ for(int i =1 ;i<num; ++i){ if(i == 1) printf("%d",b[i]); else printf(" %d",b[i]); } printf("/n");return; } if(pos>n) return; b[num] = a[pos]; dfs(num+1,pos+1); dfs(num,pos+1);}int main(){ int t = 0; while(scanf("%d",&n) && n != 0){ if(t!=0) printf("/n"); for(int i = 1; i<=n; ++i) scanf("%d",&a[i]); dfs(1,1); t++; } return 0;}

從main函數開始：

while(scanf("%d",&n) && n != 0){ if(t!=0) printf("/n"); for(int i = 1; i<=n; ++i) scanf("%d",&a[i]); t++; }

這里是數據的讀入部分，題目要求每組數據中間要有空行，所以引入變量t。那么關鍵就在于dfs函數。

void dfs(int num, int pos){ if(num == 7){ for(int i =1 ;i<num; ++i){ if(i == 1) printf("%d",b[i]); else printf(" %d",b[i]); } printf("/n");return; } if(pos>n) return; b[num] = a[pos]; dfs(num+1,pos+1); dfs(num,pos+1);}

dfs函數有2個形參，num和pos，乍一看不知道他們的作用，先姑且放著。之后是對于num是否為7的一個判斷。如果為7的話，進行一個輸出，應該就是題目要求的輸出，數組b中保存著結果?？梢妌um應該是判斷是否構成了6位的排列，當num為7遞歸調用dfs時，用return語句終止這次搜索。原因很簡單，題目只需要我找6位排列數，干嘛找7位的。這樣的判斷，叫做遞歸邊界（如有錯誤請各位指正）。遞歸邊界可以是判斷是否找到了解，如果找到了一組可行的解，就不進行遞歸了。當然要具體問題具體分析。向下看，是對pos是否大于n的判斷，如果大于n也就終止搜索了。n表示的是每組數據數字的個數，根據這個也可以想到，應該是從n個數中選6個，如果現在的位置是n+1(數據中根本沒有這個數)，當然不符合題意，終止。接著是一個賦值語句，應該可以想到是選中a數組pos這個位置的數字，把它寫到b的num這個位置。

下面關鍵來了：

dfs(num+1,pos+1);dfs(num,pos+1);

現在已經選中了a數組pos位置的數字，如果選它的話，那么就看下一位置選誰（這個位置是相對于數組b而言的），如果不選這個數字，那么對于這一位置，我們看看a數組下一個數字選還是不選。

這里寫圖片描述（圖1-3）