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
题目大意：
给出一个数n,将从1到n的数全排列，将相邻两个数互为素数且第一个数为1，第一个数与最后一个数也互为素数的排列进行输出
#include <stdio.h>
#include <string.h>
int n;
int vis[], a[];//数组vis记录改点是否被访问过，数组a记录符合条件的数
int judge(int s)//判断s是否是素数
{
int flag = ;
for(int i = ; i <= s/; i++)
{
if(s%i == )
{
flag = ;
break;
}
}
return flag;
}
void dfs(int s, int cnt)//利用深搜来解决该问题，cnt是将要往数组中放入第几个数，s是放入数组中的末端的数
{
int i, j;
if(cnt == n+ && judge(a[]+a[n]))//当放入数组中的数（cnt-1)等于n时，且数组第一个数与最后一个数也互为素数时，进行输出
{
for(j = ; j < n+; j++)
{
if(j != )
printf(" ");
printf("%d", a[j]);
}
printf("\n");
return ;
}
for(i = ; i <= n; i++)
{
if(judge(i + s) && !vis[i])//如果i与s互为素数并且i没有被访问过时，访问i,将i放入数组中
{
a[cnt] = i;
vis[i] = ;
dfs(i, cnt + );//i进行与它上一个数相同的操作，将要往数组中放入第cnt+1个数
vis[i] = ;//返回后，要将i标记为未访问 }
}
return ;
}
int main()
{
int num = ;
while(~scanf("%d", &n))
{
printf("Case %d:\n", num++);
memset(vis, , sizeof(vis));
vis[] = ;//将1标记为已访问
a[] = ;//将1放入数组中
dfs(, );
printf("\n");
}
return ;
}