题目：
| 1016 | Prime Ring Problem |
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 }
