首页 > 代码库 > Prime Ring Problem
Prime Ring Problem
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.
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.
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)View Code
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。