首页 > 学院 > 开发设计 > 正文

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

2019-11-14 08:55:45
字体:
来源:转载
供稿:网友

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(7)]—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活学活用才是王道啊!!


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表