NYOJ 488 素數環(DFS)

素數環

時間限制： 1000 ms  |  記憶體限制： 65535 KB 難度： 2

描述

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

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

輸入

有多組測試資料，每組輸入一個n(0<n<20)，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      

思路：

1.n為1時應輸出1。

2.n為奇數時直接結束(因為當n為奇數時，必定存在奇數+奇數那麼就不可能組成素數)，否則會逾時(背景應該沒有較大的偶數n，不知道還能怎麼優化QWQ)

3.n為偶數好像都有答案，不清楚原因。ORZ

代碼：

#include<stdio.h>
int n,book[25],ans[25]={1},j,flag,pri[45];
//數組book标記數字是否被使用
//數組ans表示目前狀态存放數字元素
//數組pri标記素數
//flag标記是否存在答案
void prime_number(){                    //标記素數元素為0
    int i;
    pri[0]=1;                           //判斷素數1 2應該是無所謂，反正加不到
    pri[1]=1;
    for(i=2;i<8;i++)
        if(!pri[i])
            for(j=i+i;j<41;j+=i)
                pri[j]=1;
}

void dfs(int last,int cnt){             //last表示上個數字，cnt表示ans種有多少數字
    if(cnt==n){
        if(pri[last+1]==0){
            for(j=0;j<n-1;j++)
                printf("%d ",ans[j]);
            printf("%d\n",ans[j]);
            flag=0;
        }
        return;
    }
    for(int i=2;i<=n;i++){
        if(book[i]==0&&pri[last+i]==0){
            book[i]=1;                  //标記過i
            ans[cnt]=i;
            dfs(i,cnt+1);
            book[i]=0;                  //清除标記i
        }
    }
}
int main(){
    int time=0;
    prime_number();
    while(scanf("%d",&n),n){
        printf("Case %d:\n",++time);
        flag=1;
        if(n==1){
            printf("1\n");
            continue;
        }
        if(n%2!=1)dfs(1,1);
        if(flag)printf("No Answer\n");
    }
    return 0;
}