首页 > 代码库 > Prime Ring Problem

Prime Ring Problem

2024-07-05 23:24:12   230人阅读

Prime Ring Problem

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 27   Accepted Submission(s) : 10

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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)
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 int num[25];
 5 int depend(int num[],int sum)
 6 {
 7     int jj,sign;
 8     for(jj=2,sign=0;jj*jj<=sum;jj++)
 9         if(sum%jj==0)sign++;
10     return sign;
11 }
12 
13 int depend2(int num[],int N)
14 {
15     int jj=0,sum[25];
16     memset(sum,0,sizeof(sum));
17     for(jj=0;jj<N;jj++)
18     {
19         sum[num[jj]]+=1;
20             if(sum[num[jj]]>1)
21                 return 0;
22     }
23     return 1;
24 }
25 
26 void DFS(int num[],int i,int N)
27 {
28     int flat,sum,ii,j;
29     if(i==N-1)
30     {
31         sum=num[i]+num[i-1];
32         flat=depend(num,sum);
33         if(flat!=0)return 0;
34         sum=num[0]+num[N-1];
35         flat=depend(num,sum);
36         if(flat!=0)return 0;
37         for(ii=0;ii<N;ii++)
38         {
39             printf("%d",num[ii]);
40             if(ii!=N-1)
41                 putchar(‘ ‘);
42         }
43         putchar(‘\n‘);
44         return;
45     }
46     if(i>0&&i<N)
47     {
48         sum=num[i]+num[i-1];
49         flat=depend(num,sum);
50         if(flat!=0)return 0;
51     }
52     for(j=1,flat=1;j<=N;j++)
53     {
54         num[i+1]=j;
55         flat=depend2(num,i+2);
56             if(flat!=1)continue;
57         DFS(num,i+1,N);
58     }
59 }
60 
61 int main()
62 {
63     int N,times,i,j;
64     times=1;
65     while(scanf("%d",&N)!=EOF)
66     {
67         memset(num,0,sizeof(num));
68         printf("Case %d:\n",times++);
69         num[0]=1;
70         DFS(num,0,N);
71         putchar(‘\n‘);
72     }
73     return 0;
74 
75 }
View Code

 


联系
我们