Prime RingProblem素环问题
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
代码如下：
#include <stdio.h>
#include <stdlib.h>int num[21],mark[21],n;
int prime_num[12] = {2,3,5,7,11,13,17,19,23,29,31,37};//判断是否是质数，是返回1，不是返回0
int is_prime(int a)
{int i;for(i = 0; i < 12;i++)if(a==prime_num[i])return 1;return 0;
}
void print_num()
{int i;for(i = 1; i < n;i++)printf("%d ",num[i]);printf("%d",num[n]);
}int dfs(int pre,int post,int flag)
{//如果不符合，直接返回int i;if(!is_prime(pre+post))//前+后若不是素数，则返回 0 return 0;num[flag] = post;if(flag==n&&is_prime(post+1)){print_num();printf("\n");return 1;}//使用过了这个数字就标记为0mark[post] = 0;for( i = 2;i<=n;i++)if(mark[i]!=0 && dfs(post,i,flag+1))break;//标记位恢复原状mark[post] = 1;return 0;
}int main()
{int count,i;count = 1;while(scanf("%d",&n)!=EOF){for(i = 1; i <= n; i++)mark[i] = i;num[1] = 1;printf("Case %d:\n",count++);if(n==1)printf("1\n");for(i = 2;i<=n;i++)dfs(1,i,2);printf("\n");}return 0;
}