HDOJ(HDU).1016 Prime Ring Problem (DFS)

2019-11-11 07:25:02

字體：大中小

來源：轉載

供稿：網友

HDOJ(HDU).1016 PRime Ring Problem (DFS) [從零開始DFS(3)]

從零開始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函數的思想

題意分析

給出數字n，要求將1-n的數字填成素數環，即相鄰2個數字的和為素數，按字典序依次輸出所有可能的組合。并且題目說過所有的組合開頭均為1。

哎呀這題太熟悉了，又是填數字的題目，似曾相識的感覺。討論過的填數字的題目，傳送門：

HDOJ(HDU).1342 Lotto [從零開始DFS(0)] HDOJ(HDU).1015 Safecracker [從零開始DFS(2)]

如果獨立完成了幾道dfs的題目，就會發現：其實dfs只是工具，真正考察思維的，是什么時候進行dfs，怎樣進行dfs

1.什么時候進行dfs：即遞歸邊界。滿足何種情況就不進行搜索了，或者何種情況進行一個輸出，亦或是利用條件判斷去掉重復的情況。 2.怎樣進行dfs：是二重搜索（HDOJ.1342),還是四向搜索（HDOJ.1010),還是在數組中找遍所有的元素（HDOJ.1015）。也許以后還有八向搜索，全部搜索等等方式。

不難發現本題要求的是，兩個相鄰的數字和為素數，那么也就是在每次搜索的時候，都判斷一下前2個數字的和是否為素數，若是的話繼續進行搜索，否則終止。

需要注意的是，最后還需要判斷一下，最后一個數字和第一個數字的和是否為素數，因為題目的要求是素數環嘛。否則會出現多解。

為了方便判斷素數，最好在初始化的時候進行素數篩。規模在50即可（n上限是19，最大就是19+18=37）。

上代碼。

代碼總覽

/* HDOJ.1016 Author:pengwill Date:2017-2-5*/#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;bool visit[21],prime[51];int b[21],n;void init(){ // prime 0 & not prime 1 for(int i = 2; i<=sqrt(50) ;++ i) if(prime[i] == 0){ for(int j = 2;i*j<=50;++j) prime[i*j] = 1; } prime[1] = 0; visit[1] = true;b[1] = 1;}bool check(int depth){ if(depth == n+1)//對于最后要判斷首位數字的和是否為素數 if(prime[b[1]+b[depth-1]] == 0 && prime[b[depth-2]+b[depth-1]] == 0) return true; else return false; else if(prime[b[depth-2]+b[depth-1]] == 0) return true;//若不是最后就直接判斷前2個即可 else return false;}void print(){ for(int i = 1;i<=n; ++i) if(i == 1) printf("%d",b[i]); else printf(" %d",b[i]); printf("/n");}void dfs(int depth){ if(false == check(depth)) return; if(depth == n+1){ //輸出 print(); return; } for(int i = 2; i<=n ;++i){ if(!visit[i]){ visit[i] = 1; b[depth] = i; dfs(depth+1); visit[i] = 0; } }}int main(){ int t = 1; init(); while(scanf("%d",&n) != EOF){ printf("Case %d:/n",t++); if(1==n) printf("1/n"); else dfs(2);//第一位是1，故從深度為2開始dfs printf("/n"); } return 0;}

對n為1的時候進行特判。 init函數打50規模的素數表，然后把1置為訪問過。若n不為1，對深度為2進行dfs。每次在遞歸調用dfs之前，首先檢查一下前邊2個數的和（depth-1和depth-2）是否為素數。（因為b[0]為0，當depth為2的時候也可以直接調用check函數，不用特判）。需要注意的是，當depth為n+1的時候，check需要檢查兩項內容：一是剛才說的前兩個數的和是否為素數，二是最后一個數和第一個數的和是否為素數。這樣就能保證是素數環了。

本題還有一個坑點，就是輸出格式。輸出可能組合的時候注意是每個數字之間有一個空格，也就是在行末尾只有一個換行符。題目還說了在每種case之后輸出個空行，也就是說不是每組數據之間（原文表述是 Print a blank line after each case. 是after，不是between）。所以最后還是有一個空行的。

此題不難，dfs活學活用才是王道啊！！

上一篇：1.2.1學習VB可以做什么？

下一篇：約瑟夫環問題(Josephus)　—— 循環單鏈表