题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1016
题意很简单，就是输入一个n，把1～n的数填入n个圆圈里，但是要满足相邻两个数的和是素数，输出的时候要按符合条件的序号按递增的形式输出，每个实例之间要有空行。
这是一道dfs的经典题目，其中还要结合素数的打表思想。一开始觉得给出的n<20，那么相邻两数之和最大也就37（18+19），40以内的素数可以很简单地存入prime数组中：2、3、5、7、11、13、17、19、23、29、31、37（对应的数组下标是0～11）。然后在dfs中，判断相邻两数之和是否是素数，直接从prime数组里查找即可。但是发现这样查找非常繁琐，最坏的情况（虽然这是不可能的）每个和都要查找11次。如果是19个数（n最大为19），就要查19×11次了。看了别人打表的思想后，才发现，这样可以节省很多时间。注意，prime的数组下标代表1～n的数，存储的数指示了该数是否是素数（0：不是素数 1：是素数）
至于dfs里面，有一个要注意的地方是，素数环里首尾元素之和的判断很容易忘记，而这个判断好之后，也就代表整个序列是符合条件的，可以输出。具体代码如下：
1 #include <iostream> 2 using namespace std; 3 4 int visit[40], prime[40], cur[40]; 5 int n; 6 7 int is_prime(int x) 8 { 9 int i; 10 if (x == 2) 11 return 1; 12 else if (x % 2 == 0 || x == 1) 13 return 0; 14 for (i = 3; i * i <= x; i += 2) 15 { 16 if (x % i == 0) 17 return 0; 18 } 19 return 1; 20 } 21 22 void dfs(int p) 23 { 24 int i; 25 if (p == n && prime[cur[n] + 1]) //素数环里首尾元素之和的判断 26 { 27 printf("1"); 28 for (i = 2; i <= n; i++) 29 { 30 printf(" %d", cur[i]); 31 } 32 printf("\n"); 33 } 34 for (i = 2; i <= n; i++) 35 { 36 if (prime[cur[p]+i] && !visit[i]) //未访问过的数i与它的前一个数（cur[p]）之和是素数
37 { 38 cur[p+1] = i; //cur指示下一个位置p+1，新的cur作为下一个未访问过的数的前一个数 39 visit[i] = 1; //该数已被访问 40 dfs(p+1); //搜索下一个未访问过的数 41 visit[i] = 0; //恢复递归前的未访问状态 42 } 43 } 44 } 45 46 int main() 47 { 48 int i, cas = 0; 49 for (i = 1; i <= 40; i++) 50 prime[i] = is_prime(i); //打表，0代表不是素数，1代表是素数，为dfs的查表作预处理 51 while (cin >> n) 52 { 53 memset(visit, 0, sizeof(visit)); 54 memset(cur, 0, sizeof(cur)); 55 printf("Case %d:\n", ++cas); 56 cur[1] = 1; //从1开始，代表位置1 57 visit[1] = 1; //由于要从1开始打印，可以转换为visit[1]已经被访问 58 dfs(1); //从1开始搜索 59 printf("\n"); 60 } 61 return 0; 62 }
2014.7.23
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 40; 8 int prime[maxn], vis[maxn], s[maxn], n; 9 10 bool is_prime(int n) 11 { 12 if (n == 2) 13 return true; 14 for (int i = 2; i*i <= n; i++) 15 { 16 if (n % i == 0) 17 return false; 18 } 19 return true; 20 } 21 22 void dfs(int p) 23 { 24 if (p-1 == n) // 开始写成p == n，找了差不多两日， = = 25 { 26 if (prime[s[p-1]+1]) 27 { 28 for (int i = 1; i <= n-1; i++) 29 printf("%d ", s[i]); 30 printf("%d\n", s[n]); 31 return; 32 } 33 } 34 for (int i = 2; i <= n; i++) 35 { 36 if (prime[s[p-1]+i] && !vis[i]) 37 { 38 vis[i] = 1; 39 s[p] = i; 40 dfs(p+1); 41 vis[i] = 0; 42 } 43 } 44 } 45 46 int main() 47 { 48 int cas = 0; 49 memset(prime, 0, sizeof(prime)); 50 for (int i = 2; i <= maxn-3; i++) 51 { 52 if (is_prime(i)) 53 prime[i] = 1; 54 } 55 while (scanf("%d", &n) != EOF) 56 { 57 printf("Case %d:\n", ++cas); 58 vis[1] = 1; 59 s[1] = 1; 60 dfs(2); 61 printf("\n"); 62 } 63 return 0; 64 } 65