Prime Ring Problem
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 23218 Accepted Submission(s): 10355Problem DescriptionA 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.Inputn (0 < n < 20).OutputThe 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 Input6 8Sample OutputCase 1:1 4 3 2 5 61 6 5 2 3 4Case 2:1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 2
这一题的意思是输入一个数n，然后让你用1~n的数围成一个圈，但是每相邻的两个数的和必须为素数。
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 #define MAX 22 5 int a[MAX]; //标记数组 6 int b[MAX]; 7 int n; 8 bool prime(double n) 9 { 10 int i, m; 11 m = (int)sqrt(n); 12 for (i=2; i<=m; i++) 13 if ((int)n%i == 0) 14 return false; 15 return true; 16 } 17 void dfs(int i) 18 { 19 int j; 20 if (i>=n) 21 { 22 if (prime(double(b[n-1]+1))) //判断最后一个和第一个数的和是不是素数 23 { 24 cout<<b[0]; 25 for (j=1; j<n; j++) 26 cout<<" "<<b[j]; 27 cout<<endl; 28 } 29 } 30 else 31 { 32 for (j=2; j<=n; j++) 33 { 34 if (a[j] || !prime(double(b[i-1]+j))) //a[j]已经被加入到圈中或者相邻两个数和不是素数，则continue 35 continue; 36 a[j] = 1; //如果j已经加入圈中,则标记为1 37 b[i] = j; 38 dfs(i+1); 39 a[j] = 0; 40 } 41 } 42 } 43 int main() 44 { 45 int i=1, j; 46 while (cin>>n) 47 { 48 memset(a,0,sizeof(a)); //全置为0 49 cout<<"Case "<<i++<<":"<<endl; 50 b[0] = 1; 51 dfs(1); 52 cout<<endl; 53 } 54 return 0; 55 }
原文：http://www.cnblogs.com/yazhou/p/3611032.html
