★☆   输入文件：dfs3.in   输出文件：dfs3.out   简单对比

时间限制：1 s   内存限制：128 MB

问题描述

试编程将 1 至 N （ N ≤ 15 ）的自然数序列 1 ， 2 ， … ， N 重新排列，使任意相邻两数之和为素数。例如 N=3 时有两种排列方案 123 、 321 满足要求。

【输入格式】

输入文件：dfs3.in

第一行：一个整数n(1<=n<=15)

【输出格式】

输出文件：dfs3.out

输出若干行，每行为一种排列方案（排列方案按字典序排列， 相邻数字之间用空格分隔） ），最后一行输出排列方案总数。

【输入样例】

输入文件名：dfs3.in

3

输出文件名：dfs3.out

1 2 3

3 2 1

2

 

1 #include 
     
       2 #include 
      
        3   4 using namespace std; 5   6 int n,ans,a[55]; 7 int prim[55],use[55]; 8 void Prim() 9 {10     for(int i=1;i<=(n<<1);i++)11     {12         prim[i]=1;13         for(int j=2;j*j<=i;j++)14             if(i%j==0)15             {16                 prim[i]=0;17                 break;18             }19     }20 }21 22 void DFS(int cnt)23 {24     if(cnt==n+1)25     {26         ans++;27         for(int i=1;i<=n;i++)28             printf("%d ",a[i]);29         printf("\n");30         return ;31     }32     for(int i=1;i<=n;i++)33     {34         if(use[i]) continue;35         if(!prim[a[cnt-1]+i]&&cnt>1) continue;36         use[i]=1; a[cnt]=i;37         DFS(cnt+1);38         use[i]=0;39     }40 }41 42 int main()43 {44     freopen("dfs3.in","r",stdin);45     freopen("dfs3.out","w",stdout);46     scanf("%d",&n);47     Prim();  DFS(1);48     printf("%d",ans);49     return 0;50 }