题目：
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
解题思路：这是一个深搜问题，找出满足条件的所有情况，定义一个数组，然后起始坐标为1，之后从后面2、3、4、5、6之前任意搭配，当然走过之后的点要标记，相邻两个元素的和为素数，也要考虑第一个与最后一个数也要满足条件。。注意：每一个输出样例之后都要有一个换行。
程序代码：
#include<stdio.h> #include<math.h> #include<string.h> int n,l=1; int a[500],book[500]; int fn(int m); void dfs(int step) { int k; if(step>n&&fn(1+a[step-1])==1) { printf("%d",a[1]); for(int i=2;i<=n;i++) printf(" %d",a[i]); printf("\n"); return; } for(k=2;k<=n;k++) { a[step]=k; if(fn(a[step]+a[step-1])==1&&book[k]==0) { book[k]=1; dfs(step+1); book[k]=0; } } return; } int main() { int i,j,k=1; while(scanf("%d",&n)!=EOF) { memset(book,0,sizeof(book)); for(i=1;i<=n;i++) a[i]=i; printf("Case %d:\n",k); book[1]=1; a[1]=1; dfs(2); printf("\n"); k++; } return 0; } int fn(int m) { int k,i,a; if(m==1) return 0; k=(int)sqrt(m); for(i=2;i<=k;i++) { if(m%i==0) return 0; } return 1; }
