生活随笔
收集整理的这篇文章主要介绍了
HDOJ1016 素数环（DFS）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题目：
1 /*
2 素数环（顺时针逆时针）---dfs
3 使用栈
4 1-n（n最大是20，相邻最大和39，素数范围2-39之间）
5 2-39间的素数：
6 2，3，5，7，11，13，17，19，23，29，31，37
7 从1开始，逐个尝试，如果是素数，入栈，否则尝试下一个，直到全部尝试完；
8 如果n个数全部入栈了，输出一组解（n最大为20，输出栈可以使用递归），
9 第一个数始终是1，第二个数需要尝试n+1的时候，就表示结束了（next = -1）。
10 */
11 #include <cstdio>
12 #include <iostream>
13 #include <stack>
14 using namespace std;
15
16 #define N 22
17 //全局变量
18 int prime[
40];
19 int arr[N];
20 stack<
int>
s;
21
22 //函数
23 void InitPrime();
24 void InitArr(
int n);
25 void dfs(
int n);
26 int GetNext(
int b,
int n);
27 void Output(
int n);
28 //main
29 void main()
30 {
31 int n;
32 InitPrime();
33 while (scanf(
"%d",&n)!=
EOF)
34 {
35 InitArr(n);
36 dfs(n);
37 }
38 }
39
40 void InitPrime()
41 {
42 for (
int i=
0;i<
40;i++
)
43 {
44 switch(i)
//本题数量不多，就直接这样写啦，如果数量多可以用【筛选法】或者【试除法】
45 {
46 case 2:
case 3:
case 5:
47 case 7:
case 11:
case 13:
48 case 17:
case 19:
case 23:
49 case 29:
case 31:
case 37:
50 prime[i] =
1;
51 break;
52 default:
53 prime[i] =
0;
54 }
55 }
56 }
57
58 void InitArr(
int n)
59 {
60 for (
int i=
1; i<=n ; i++
)
61 {
62 arr[i] =
0;
63 }
64 }
65 void dfs(
int n)
66 {
67 int flag,next,b,idx;
68 s.push(
1);
69 arr[
1] =
1;
70 flag =
1;
71 idx =
1;
//从idx开始寻找匹配数字
72 while (flag)
73 {
74 b =
s.top();
75 next =
GetNext(idx,n);
76 if (next == -
1)
//尝试结束，回溯
77 {
78 if (b ==
1 && next == -
1)
//over
79 {
80 flag =
0;
81 }
82 idx =
s.top();
83 s.pop();
84 arr[idx] =
0;
85 continue;
86 }
87 if (prime[next+b] ==
1)
//匹配成功，next入栈，idx化为2
88 {
89 arr[next] =
1;
90 s.push(next);
91 idx =
1;
92 //全部入栈则输出
93 if (s.size() == n && prime[
1+s.top()] ==
1)
//既要顺时针为素数环又要逆时针为素数环
94 {
95 Output(n);
96 cout<<
endl;
97 idx =
s.top();
98 s.pop();
99 arr[idx] =
0;
100 }
101 continue;
102 }
103 //匹配失败，idx化为next
104 idx =
next;
105 }
106
107 }
108 int GetNext(
int b,
int n)
109 {
110 for (
int i=b+
1;i<=n;i++
)
111 {
112 if (arr[i]!=
1)
113 return i;
114 }
115 return -
1;
//全部尝试完返回-1
116 }
117 void Output(
int n)
118 {
119 int cur;
120 if (n!=
0)
121 {
122 cur =
s.top();
123 s.pop();
124 Output(n-
1);
125 cout<<cur<<
' ';
126 s.push(cur);
//还要加回去
127 }
128 }
总结
以上是生活随笔为你收集整理的HDOJ1016 素数环（DFS）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
