学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1016

1-n的正整数，每个元素构成一个环，要求前后相邻的元素之和为素数，且第一个元素始终为1，如果有多个满足的情况，按照字典序输出每组序列。

思路：深度优先搜索，边搜索边判断，当深度为n时，输出暂存数组里面的元素，即为符合的答案，从2到n开始遍历，能满足字典序从小到大。

AC代码：

#include <iostream>
using namespace std;
int n,casenum=1;
bool flag[50];    //素数标记表 
int prime[50];   //没用 
int num[20];    //暂存每个元素的数组 
bool visit[20];  //标记每个元素的状态 
void primemake(){
	memset(flag,0,sizeof(flag));
	int t=0;
	for(int i=2;i<=50;i++)
	{
		if(!flag[i]){
			prime[t++]=i;
			for(int j=2;i*j<=50;j++)
				flag[i*j]=1;
		}
	}
}                 //筛选法构造素数表 
void dfs(int s);
int main()
{
	
	while(cin>>n)
	{
		if(n<=0||n>=20)break;
		cout<<"Case "<<casenum<<":"<<endl;
		primemake();
		memset(visit,0,sizeof(visit));
	    num[0]=1;       //题目要求开始元素始终为1  
		dfs(1);
		cout<<endl;
		casenum++;
	}
	return 0;
}
void dfs(int s) //s为搜索的深度 
{
	if(s==n)
	{
		if(!flag[num[s-1]+num[0]]){
			for(int i=0;i<n-1;i++)
				cout<<num[i]<<" ";
			cout<<num[n-1]<<endl;	
		}
		return ;
	}

	for(int i=2;i<=n;i++)
	{
		
		if(visit[i] || flag[num[s-1]+i])continue ;//边搜索边判断条件 
		num[s]=i;
		visit[i]=1;       //状态标记 
		dfs(s+1);
		visit[i]=0;      //取消状态标记 
	}
}