nyoj 488 素數環（深搜）

nyoj 488 素數環（深搜）

素數環

描述

有一個整數n，把從1到n的數字無重復的排列成環，且使每相鄰兩個數（包括首尾）的和都為素數，稱為素數環。

為了簡便起見，我們規定每個素數環都從1開始。例如，下圖就是6的一個素數環。

輸入

有多組測試數據，每組輸入一個n(0 輸出

每組第一行輸出對應的Case序號，從1開始。
如果存在滿足題意敘述的素數環，從小到大輸出。
否則輸出No Answer。

樣例輸入

6
8
3
0

樣例輸出

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
Case 3:
No Answer

來源

hdu改編

上傳者

ACM_丁國強

考察的是深搜；

深搜模板：

//深搜模板：（自己總結的，有不對的地方，還請各位路過的大牛，不吝指教！） 
int n;//首先申請一個全局變量 
int visit[10010];//標記 元素 
int a[10010];//存放元素 
void dfs(int cur)
{
	//此處是遞歸跳出條件 
	if(cur==n)//此處的判斷條件看數組下標是否 是從1 開始的
	{
		if(   )//題目中限定的一定條件。
		{
			printf("  ");//輸出相應的要求解的值 
		}
	}
	for(i=2;i<=n;++i)
	{
		if(  )//又是與題中的限定條件有關，到那時多了一個判斷是否已經標記過
		{
			visit[i]=1;
			a[k]=i;//將此時境況下滿足條件的數據存入數組 
			dfs(k+1); //對後面的元素進行遞歸 
			visit[i]=0;//這兩步與輸出多組數據有關，遞歸跳出的時候，在多組跳出的時候
			           //為了後續滿足題意的數據的輸出，需要返回出師狀態 
		} 
	} 
} 

代碼如下：

#include
#include
int n;
int visit[110];
int ring[110]={1};
int prime(int x)//判斷是否是素數 
{
	for(int i=2;i*i<=x;++i)
	{
		if(x%i==0)
		return 0;
	}
	return 1;
}
void dfs(int k)//深搜 
{
	int i;
	if(k==n-1)//循環跳出的條件 
	{
		if(prime(1+ring[k]))//滿足和為素數 
		{
			printf("1");
			for(i=1;i