Problem Description
A ring is composeof n circles as shown in diagram. Put natural number 1, 2, ..., n into eachcircle separately, and the sum of numbers in two adjacent circles should be aprime. Note: the number of first circle should always be 1.
环是组合成n个圆圈所示的图。把自然数1，2，...，n为进分别各圈，和数字中的两个相邻圈之和应该是一个素数。
注意：第一圈的数量始终应为1。
Input
n (0 < n <20).
Output
The output formatis shown as sample below. Each row represents a series of circle numbers in thering beginning from 1 clockwisely and anticlockwisely. The order of numbersmust 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.
输出格式如下图所示的样品。每一行代表一个系列的圆形数字的环从1开始顺时针和按逆时针方向。号的顺序，必须满足上述要求。在字典顺序打印解决方案。
请你写一个程序，完成上述过程。
打印每个案例后，一个空行。
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，依次判断即可，难在于递归执行过程，建议单步调试观察其运行过程，建议例子为：4
#include<stdio.h> #include<string.h> #include<stdlib.h> int ans[20]; bool hash[20]; int n; int prinme[]={2,3,5,7,11,13,17,19,23,29,31}; bool judge(int x)//判断一个数是否为素数，这个不难理解 { int i; for(i=0;i<11;i++) { if(x==prinme[i]) return true; } return false; } void check() //因为前n个数已经被检查，这里只需要坚持n和1是否 //符合条件，如果符合则输出 { if(judge(ans[n]+ans[1])==false) return ; for(int i=1;ans[i]!=0;i++){ if(i!=1) printf(" "); printf("%d",ans[i]); } printf("\n"); } void DFS(int num) { int i; if(num>1) //每次想加一都递归调用判断，如果不符合则return DFS，重新for，再递归判断 if(judge(ans[num]+ans[num-1])==false) return ; if(num==n){ check(); //进行判断输出 return ; //会return到DFS，继续进行。 } for(i=2;i<=n;i++){ //难点是区分，这是哪一次i，单步调试吧 if(hash[i]==false){ hash[i]=true; ans[num+1]=i; DFS(num+1); hash[i]=false; } } } int main() { int cas=0; while(scanf("%d",&n)!=EOF){ cas++; for(int i=0;i<20;i++) hash[i]=false; ans[1]=1; printf("Case %d:\n",cas); hash[1]=true; DFS(1); //printf("\n"); } system("pause"); return 0; }
