Prime Ring Problem(dfs水)

showproblem.php?pid=1016

Prime Ring Problem

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

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:
4 3 2 5 6
6 5 2 3 4

Case 2:
2 3 8 5 6 7 4
2 5 8 3 4 7 6
4 7 6 5 8 3 2
6 7 4 3 8 5 2

Source

Asia 1996, Shanghai (Mainland China)

简单的dfs

直接上代码:

这里介绍一个报错:Floating point exception (core dumped) linux下报这个一般就是出现了除0或者模0操作....写代码要仔细呀

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 #define N 50
 5 int a[N];
 6 bool vis[N];
 7 bool is_prime[N];
 8 void init()
 9 {
10     for(int i =0 ;i < N ;i++) is_prime[i] = 1;
11     for(int i =2  ;i < N ;i++)
12     {
13         for(int j = 2 ; j <= i/2 ;j++)
14         {
15             if(i%j==0) {is_prime[i] = 0 ; continue;}
16         }
17     }
18 }
19 void dfs(int n, int cnt)
20 {
21     if(cnt == n&&is_prime[a[0]+a[n-1]]) 
22     {
23         for(int i =0 ; i < n-1 ;i++)
24         {
25             printf("%d ",a[i]);
26         }
27         printf("%d
",a[n-1]);
28     }
29 
30     for(int i = 1 ;i <= n ;i++)
31     {
32         if(!vis[i]&&is_prime[a[cnt-1]+i])
33         {
34             a[cnt] = i;
35             vis[i] = 1;
36             dfs(n,cnt+1);
37             vis[i] = 0;
38         }
39     }
40 }
41 
42 int main()
43 {
44     int n;
45     int c = 0;
46     init();
47     while(~scanf("%d",&n))
48     {
49         printf("Case %d:
",++c);
50         a[0] = 1;
51         memset(vis,0,sizeof(vis));
52         vis[1] = 1;
53         dfs(n,1);
54         puts("");
55     }
56     return 0;
57 }