杭电1016--Prime Ring Problem(Dfs)

Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 34108 Accepted Submission(s): 15098

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 | We have carefully selected several similar problems for you: 1010 1072 1175 1253 1181

RE:素数环，字典序输出；

 1 #include <cmath> 
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 int dis[30], vis[30], my[30];
 7 int n;
 8 int is_prime(int a)     //判断素数； 
 9 {
10 
11     if(a == 1 || a == 0)
12         return 0;
13     if(a == 2)
14         return 1;
15     else
16     {
17         for(int i=2; i <= sqrt(a); i++)         //不要忘记等号；
18         {
19             if(a % i == 0)
20                 return 0; 
21         }
22         return 1;
23     }
24 } 
25 void Dfs(int a)
26 {
27     int i;
28     if(a == n && is_prime(dis[n-1] + dis[0]))
29     {
30         for(i = 0; i < n; i++)
31         {
32             if(i > 0)
33                 printf(" ");
34             printf("%d", dis[i]);
35         }
36         printf("
");
37         return;               //子循环结束； 
38     }
39     for(i=2; i<=n; i++)
40     {
41         if(!vis[i] && is_prime(dis[a - 1] + i))
42         {
43             vis[i] = 1;
44             dis[a] = i;
45             Dfs(a  + 1);
46             vis[i] = 0;
47         }
48     }
49 }
50 int main()
51 {
52     int i, j = 1;
53     while(~scanf("%d", &n))
54     {
55         memset(vis, 0 , sizeof(vis));
56         printf("Case %d:
", j++);
57         vis[0] = 1;
58         dis[0] = 1;
59         Dfs(1);
60         printf("
");
61     }
62     return 0; 
63 }