033：Prime RingProblem素环问题

Messj

Problem Description

A ring is composeof n circles as shown in diagram. Put natural number 1, 2, ..., n into eachcircle separately, and the sum of numbers in two adjacent circles should be aprime.
Note: the number of first circle should always be 1.

环是组合成n个圆圈所示的图。把自然数1，2，...，n为进分别各圈，和数字中的两个相邻圈之和应该是一个素数。

注意：第一圈的数量始终应为1。

Input

n (0 < n <20).

Output

The output formatis shown as sample below. Each row represents a series of circle numbers in thering beginning from 1 clockwisely and anticlockwisely. The order of numbersmust 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.

输出格式如下图所示的样品。每一行代表一个系列的圆形数字的环从1开始顺时针和按逆时针方向。号的顺序，必须满足上述要求。在字典顺序打印解决方案。

请你写一个程序，完成上述过程。

打印每个案例后，一个空行。

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

Messj

计算规模并不庞大，使用dfs和递归最容易不过

1. #include<cstdio>
   
2. #include<cstring>
   
3. #define N 20
   
4. 
   
5. using namespace std;
   
6. int ans[N];
   
7. bool hash[N];
   
8. int n;
   
9. int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41};
   
10. bool judge(int x)
    
11. {
    
12.         for(int i=0;i<13;i++)
    
13.                 if(prime[i]==x)
    
14.                         return true;
    
15.         return false;
    
16. }
    
17. void check()
    
18. {
    
19.         if(judge(ans[n]+ans[1])==false)
    
20.                 return ;
    
21.         for(int i=1;i<=n;i++)
    
22.         {
    
23.                 if(i!=1)
    
24.                         printf(" ");
    
25.                 printf("%d",ans[i]);
    
26.         }       
    
27.         printf("\n");
    
28. }
    
29. void DFS(int num)
    
30. {
    
31.         if(num>1)
    
32.                 if(judge(ans[num]+ans[num-1])==false)
    
33.                         return ;
    
34.         if(num==n)
    
35.         {
    
36.                 check();
    
37.                 return ;
    
38.         }
    
39.         for(int i=2;i<=n;i++)
    
40.         {
    
41.                 if(hash[i]==false)
    
42.                 {
    
43.                         hash[i]=true;
    
44.                         ans[num+1]=i;
    
45.                         DFS(num+1);
    
46.                         hash[i]=false;     //关键！！！回溯！！！
    
47.                 }
    
48.         }
    
49.        
    
50. }
    
51. int main()
    
52. {
    
53.         int cas=0;
    
54.         while(scanf("%d",&n)!=EOF)
    
55.         {
    
56.                 cas++;
    
57.                 for(int i=0;i<N;i++)
    
58.                         hash[i]=false;
    
59.                 ans[1]=1;
    
60.                 printf("Case %d:\n",cas);
    
61.                 hash[1]=true;
    
62.                 DFS(1);
    
63.                 printf("\n");
    
64.         }
    
65.         return 0;
    
66. }

复制代码