HDU 1016 Prime Ring Problem
程序员文章站
2022-07-10 09:18:44
...
原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1016
Prime Ring Problem
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 25493 Accepted Submission(s): 11369
Problem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.
Note: the number of first circle should always be 1.
Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.
You are to write a program that completes above process.
Print a blank line after each case.
Sample Input
6 8
Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
Source
Recommend
JGShining
分析:这道题目就是用深度优先遍历的方式来解决的。首先构造素数表,这个我就不多解释了,网上代码和解释多的是。由于环的开始点被定死的,都是1,1先入栈,标记为访问过的数字,用for循环遍历给定范围内的所有数字,遇到与1相加是素数的,停止,就将它放入栈中,标记为访问过的数字,进入DFS函数操作,DFS函数也就是一个迭代过程,用for 循环遍历所有未访问过的 数字,如果与栈顶元素相加为素数,则停止,放入栈中,标记为访问过的数字,一直迭代下去,一直到没有可以用的数字为止(PS:没有可以用的数字就是 情况1:所有数字都被访问过,也就是全部入栈 ;情况2:不是所有数字都被访问过,但是剩下的数字中没有能够和栈顶元素相加和为素数的了)如果此时栈内元素==n,那么说明当前序列符合题目要求,则从栈底到栈顶依次输出所有元素。如果此时栈内元素!=n,说明当前序列不可能是符合题意的子序列,因此必须回溯!!!
回溯是在DFS()后,回溯必须注意要把visit[]中相应的元素还原为未访问(比如说你从1 2 3 4 5 中5不合题意,回溯那么5必须标记为未访问,因为你要得到的序列是 1 2 3 4),并且弹出栈顶元素。
源代码:
//深度优先搜索(DFS) #include <stdio.h> #include <string.h> #include <stack> using namespace std; const int MAXN = 50; const int MAXNA = 21; bool isPrime[MAXN]; bool isVis[MAXNA]; int arstack[MAXNA]; int total,n; stack<int> ans; stack<int> temp; //初始素数表 void initPrime(){ memset(isPrime,1,sizeof(isPrime)); isPrime[0] = false; isPrime[1] = false; for(int i=2;i<MAXN;i++){ if(isPrime[i]){ for(int j = 2;j*i<=MAXN;j++) isPrime[j*i] = false; } } } void DFS(int x,int count){ if(count == n && isPrime[x+1]){ int i=0; temp = ans; while(!temp.empty()){ arstack[i++]= temp.top(); temp.pop(); } for(int j=i-1;j>0;j--){ printf("%d ",arstack[j]); } printf("%d\n",arstack[0]); return; } else{ for(int d=1;d<=n;d++){ if(!isVis[d] && isPrime[d+x]){ isVis[d]=1; ans.push(d); DFS(d,count+1); ans.pop(); isVis[d]=0; } } } } main(){ initPrime(); int k=1; while(scanf("%d",&n)!=EOF){ while(!ans.empty())ans.pop(); memset(isVis,0,sizeof(isVis)); printf("Case %d:\n",k++); isVis[1] = 1; ans.push(1); for(int i=2;i<=n;i++){ total = 1; if(!isVis[i]&&isPrime[1+i]){ isVis[i] = 1; ans.push(i); DFS(i,total+1); ans.pop(); isVis[i] = 0; } } printf("\n"); } }
上一篇: 【FastDFS专题】fastdfs使用实战(安装篇)
下一篇: nyoj306 dfs+二分搜索