Prime Ring Problem

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

题意描述：

输出1到n的自然数可以组成一个以1开头，顺时针或逆时针相邻两个和都为素数的环的情况。

解题思路：

a[]数组为盒子，盒子里放入数，book[]记录数字是否已被使用，a[1]赋值为1，book[1]=1数字1已被使用；当查找到第n+1个盒子时，说明前n个盒子已查找完，若a[1]+a[n]也为素数即符合情况输出。未查找到n+1时，从数字二开始判断，若数字还未被使用且与前一个盒子中的数的和为素数，既符合，将数字放入盒子，记录数字已被使用，查找下一个盒子；查找结束要取消这个点的标记。

错误分析：

之前先想到的是啊哈算法上的对数的全排列，可是如果先对数进行全排列的话会数据特别多，不利于查找。

#include<Stdio.h>
#include<string.h>
#include<math.h>
int a[25],book[25],n;

int prime(int x)
{
	int j,k;
	if(x==1)
		return 0;
	k=(int)sqrt(x);
	for(j=2;j<=k;j++)
		if(x%j==0)
			return 0;
	return 1;
}

void dfs(int num)
{
	int i;//i不能定义为全局变量 
	if(num==n+1&&prime(a[1]+a[n])==1)//当查找到n+1个盒子时，说明前n个盒子已查找完，若符合，输出 
	{
	
			for(i=1;i<n;i++)
				printf("%d ",a[i]);
			printf("%d\n",a[n]);
	
		
	}
	else
		for(i=2;i<=n;i++)//利用循环查看第num个盒子可以放2-n中的哪个数 
			if(book[i]==0&&prime(i+a[num-1])==1)//判断这个数是否被使用过，是否符合条件 
			{
				book[i]=1;
				a[num]=i;
				
				dfs(num+1);
				book[i]=0;
			}
}

int main()
{
	int t=0;
	while(scanf("%d",&n)!=EOF)
	{
		memset(book,0,sizeof(book));
		memset(a,0,sizeof(a));
		t++;
		printf("Case %d:\n",t);
		a[1]=1;
		book[1]=1;
		dfs(2);
		printf("\n");
	}
	return 0;
}