1031 質數環（深搜練習）

1031 質數環（深搜練習）

 
題目描述 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

題解：暴力搜索
代碼代碼詳解：

#include
#include
using namespace std;
int a[18],n,b[18];//a用來存放可選數據，b用來存放已放數據
int F(int n)//測試是否為素數，1為不是，0為是素數
{
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)return 0;
    }
    return 1;
}
void dfs(int x)//搜索
{
    if(x==n){
        if(F(b[x-1]+1)){//查看最後一個與第一個是否可以相加為素數
            for(int i=0;i