[Wikioi 1031]質數環---HBNU的童鞋過來看看

題目描述 Description

一個大小為N(N<=17)的質數環是由1到N共N個自然數組成的一個數環，數環上每兩個相鄰的數字之和為質數。如下圖是一個大小為6的質數環。為了友善描述，規定數環上的第一個數字總是1。如下圖可用1 4 3 2 5 6來描述。若兩個質數環，數字排列順序相同則視為本質相同。現在要求你求出所有本質不同的數環。

輸入描述 Input Description

隻有一個數N，表示需求的質數環的大小。如：

輸出描述 Output Description

每一行描述一個數環，如果有多組解，按照字典序從小到大輸出。如：

樣例輸入 Sample Input

6

樣例輸出 Sample Output

1 4 3 2 5 6

1 6 5 2 3 4

資料範圍及提示 Data Size & Hint

n<=17

對代碼不做解釋，貌似标程就是我的代碼，普通的DFS就行，建議用數組儲存每個數是否是質數，這樣可以省去重複判斷質數的時間，而且使代碼更簡單

#include <stdio.h>
#define MAXN 1000
int prime[MAXN],sol[MAXN],used[MAXN],n;
//prime[i]=1表示i是質數,sol[i]=目前輸出方案中環上第i個數,used[i]=目前輸出方案中環上第i個數
int isprime(int in) //是質數傳回1，不是傳回0
{
	int i;
	for(i=2;i<in;i++)
		if(in%i==0)
			return 0;
	return 1;
}
void dfs(int m) //填寫環上第m個數
{
	int i,j;
	if(m>n) //最後一個數已經填寫完
	{
		for(j=1;j<=n;j++)
			printf("%d ",sol[j]);
		printf("\n");
		return;
	}
	for(i=2;i<=n;i++)
	{
		if(used[i]==0&&prime[sol[m-1]+i]) //數字i沒有用過且i與第m-1個數之和為質數
		{
			used[i]=1;
			sol[m]=i;
			if(m<n) dfs(m+1);
			else if(prime[sol[1]+i]) dfs(m+1);
			sol[m]=0;
			used[i]=0;
		}
	}
}
int main()
{
	int i;
	scanf("%d",&n);
	for(i=2;i<=2*n;i++)
		prime[i]=isprime(i);
	used[1]=1; //數字1被用過了
	sol[1]=1; //第一個數是數字1
	dfs(2);
	return 0;
}