素数环（深搜）

亦凉 2022-09-28 13:01 125阅读 0赞

描述

有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。

为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。

![20120315192417_81102.gif][]

输入

有多组测试数据，每组输入一个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

思路：

输入0退出，1和非偶数的可以构成素数环，看评论区出题人说1也可以构成，头和尾都是1之和为2

代码：

#include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    int a[45]={0},b[21]={0},v[21]={0},n;
    void init()//筛选出素数 
    {
    	int i,j;
    	for(i=2; i<45; i++)
    		a[i] = i;  
    	for (i=2; i*i<45; i++)
    	{
    		if (a[i] != 0)
    		for (j=i*2; j<45; j+=i)
    		{
    			a[j] = 0;
    		}
    	}
    }
    void dfs(int x)
    {
    	int i,j;
    	if (x > 0 && b[0]!=1)  //必须1开头 
    	{
    		return ;
    	}
    	for (j=2; j<=x; j++)
    	{
    		if (!a[b[j-2]+b[j-1]]) //两素数之和不是素数之间返回 
    		{
    			return ;
    		}
    	}
    	if (x == n)//刚好n个数 ,是一种解 
    	{
    		if (a[b[0] + b[x-1]]) //头和尾也必须是素数 
    		{
    			for (j=0; j<n; j++)
    			{
    				cout<<b[j]<<" "; 
    			}
    			cout<<endl;
    			return ;	
    		}
    	}
    	for (i=1; i<=n; i++)
    	{
    		if (!v[i])
    		{
    			b[x] = i;
    			v[i] = 1;
    			dfs(x+1); //列举第二个数 
    			v[i] = 0;
    		}
    	}
    } 
    int main()
    {
    	init();
    	int i,j,ca=1,T=0;
    	while (cin>>n)
    	{
    		if (n==0)
    			break;
    		T++;
    		cout<<"Case "<<T<<":"<<endl;
    		memset(v,0,sizeof(v));
    		if (n==1)
    		{
    			cout<<1<<endl;
    		}
    		else if (n%2==0)
    		{
    			dfs(0);
    		}
    		else
    		{
    			cout<<"No Answer"<<endl;
    		}
    	}
    	return 0;
     }

[20120315192417_81102.gif]: http://acm.nyist.net/JudgeOnline/admin/kind/attached/20120315192417_81102.gif