4.3.2 Prime Ring Problem

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.

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

Source

Asia 1996, Shanghai (Mainland China)

Recommend

JGShining

思路：dfs，我是预处理，将每一个数可以与之匹配的质数先找出来，再dfs

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 const int b[]={2,3,5,7,11,13,17,19,23,29,31,37};
 5 int a[22],x[22][10],c[22];
 6 int n,t;
 7 bool prime[40],f[40];
 8 
 9 bool judge(int k)
10 {
11     if (prime[k]) return true;
12     return false;
13 }
14 
15 void w(int k)
16 {
17     prime[k]=true;
18 }
19 
20 void dfs(int k)
21 {
22 int t;
23 if (n==k)
24 {
25 //    printf("a[k]:%d a[k-1]:%d k:%d\n",a[k],a[k-1],k);
26     if (judge(a[k-1]+1))
27     {
28         for (int i=0;i<n-1;i++)
29             printf("%d ",a[i]);
30         printf("%d\n",a[n-1]);
31     //    printf("\n");
32    }
33     return;
34 }
35 for (int i=0;i<c[a[k-1]];i++)
36 {
37     t=x[a[k-1]][i];
38     if (t>n) break;
39     if (not f[t])
40     {
41         f[t]=true;
42         a[k]=t;
43         dfs(k+1);
44        a[k]=0;
45         f[t]=false;
46     }
47 }
48 }
49 
50 void init()
51 {
52 memset(prime,false,sizeof(prime));
53 memset(c,false,sizeof(c));
54 for (int i=0;i<11;i++)
55     w(b[i]);
56 //for (int i=0;i<41;i++)
57 //    if (prime[i]) printf("%d \n",i);
58 
59 for (int i=0;i<20;i++)
60     for (int j=1;j<20;j++)
61         if (i!=j && judge(i+j))
62         {
63             x[i][c[i]]=j;
64             c[i]++;
65         }
66 int cnt=0;
67    while (scanf("%d",&n)!=EOF)
68     {
69         cnt++;
70         printf("Case %d:\n",cnt);
71         memset(f,false,sizeof(f));
72         f[1]=true;
73         a[0]=1;
74        dfs(1);
75         printf("\n");
76     }
77 }
78 
79 int main ()
80 {
81 init();
82 return 0;
83 }