文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
非常典型非常顺手的深度优先搜索(DFS)题，写起来非常痛快。
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.
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.
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
Slyar:大意是给出N，求所有由1-N组成的首位为1环形序列，要求相邻两数的和为素数。素数判断不说了，因为N小于20，所以可以预先将素数打表保存供后面查询。因为规定了首位为1，所以从1开始搜索所有的可能，用visit[]标记访问过的数字，每次搜到深度等于N的时候就可以打印结果path[]了。没有结果的也就空着输出就好了，格式方面注意每行结果的最后一个数字后面没有空格。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define MAX 51 int n; int path[MAX]; int visit[MAX]; int prime[MAX]; int isPrime(int x) { int i; for (i = 2; i <= sqrt(x*1.0); i++) { if (x % i == 0) return 0; } return 1; } void dfs(int x) { int i; if ((x == n) && prime[path[1] + path[n]]) { for (i = 1; i < n; i++) { printf("%d ", path[i]); } printf("%d\n", path[n]); return; } else { for (i = 2; i <= n; i++) { if (!visit[i] && prime[path[x] + i]) { path[x+1] = i; visit[i] = 1; dfs(x+1); visit[i] = 0; } } } } int main() { int i, t; // 打表 for (i = 1; i < MAX; i++) { if (isPrime(i)) prime[i] = 1; else prime[i] = 0; } // 输出 t = 0; while(scanf("%d", &n) != EOF) { printf("Case %d:\n", ++t); memset(visit, 0, sizeof(visit)); path[1] = 1; visit[1] = 1; dfs(1); printf("\n"); } //system("pause"); return 0; } |