Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 20363 Accepted Submission(s): 9115
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 <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <cstdlib> 6 #include <algorithm> 7 #include <vector> 8 #include <stack> 9 #include <queue> 10 #include <cassert> 11 #include <set> 12 #include <sstream> 13 #include <map> 14 using namespace std ; 15 #ifdef DeBUG 16 #define bug assert 17 #else 18 #define bug // 19 #endif 20 #define zero {0} 21 #define INF 2000000000 22 #define eps 1e-6 23 int cnt=1; 24 int a[30];//记录序列 25 int used[30];//记录i是否使用 26 int prime[]={ 27 0,1,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0, 28 1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0, 29 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0 30 }; 31 int n; 32 void print()//打印数组 33 { 34 for(int i=1;i<n;i++) 35 printf("%d ",a[i]); 36 printf("%d\n",a[n]); 37 } 38 void dfs(int depth) 39 { 40 if(depth==n+1) 41 { 42 if(prime[a[n]+1])//判断最后一个元素与第一个元素是否为素数 43 { 44 print(); 45 } 46 return; 47 } 48 else 49 { 50 for(int i=1;i<=n;i++) 51 { 52 if(!used[i]&&prime[a[depth-1]+i]) 53 { 54 a[depth]=i; 55 used[i]=true; 56 // print(); 57 dfs(depth+1); 58 used[i]=false; 59 a[depth]=0; 60 } 61 } 62 } 63 } 64 int main() 65 { 66 67 68 #ifdef DeBUGs 69 freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); 70 // freopen("C:\\Users\\Sky\\Desktop\\打表.txt","w",stdout);//PLEASE DELETE IT!!!!!!!!!!!!!!!!!!!!!!!! 71 #endif 72 while(scanf("%d",&n)+1) 73 { 74 memset(a,0,sizeof(a)); 75 memset(used,0,sizeof(used)); 76 printf("Case %d:\n",cnt++); 77 a[1]=1; 78 used[1]=1; 79 dfs(2); 80 printf("\n"); 81 } 82 return 0; 83 } View Code
转载于:https://www.cnblogs.com/Skyxj/p/3248600.html
