HDOJ.1342 Lotto （DFS）

2019-11-14 13:02:09

字體：大中小

供稿：網(wǎng)友

Lotto [從零開始DFS(0)]

點(diǎn)我挑戰(zhàn)題目

從零開始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)] —小結(jié)：做DFS題目的關(guān)注點(diǎn) HDOJ(HDU).1035 Robot Motion [從零開始DFS(4)]—DFS題目練習(xí) HDOJ(HDU).1241 Oil Deposits(DFS) [從零開始DFS(5)] —DFS八向搜索/雙重for循環(huán)遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開始DFS(７)]—DFS練習(xí)/check函數(shù)的思想

題意分析

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

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

Tip:數(shù)字為訪問順序，紅色代表前進(jìn)的過程，藍(lán)色代表返回的過程。這里可以看到，是永遠(yuǎn)先訪問上邊的節(jié)點(diǎn)，其次是下面的節(jié)點(diǎn)。

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

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

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

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

Tiip:由此可見，當(dāng)數(shù)據(jù)規(guī)模非常大的時候，剪枝可以顯著提高程序運(yùn)行的效率。有時候沒剪枝T了，剪枝就AC了。

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

代碼總覽

/* 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函數(shù)開始：

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

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

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

下面關(guān)鍵來了：

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

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

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