NYOJ 488-素数环【dfs】

古城微笑少年丶 2022-08-21 11:57 177阅读 0赞

## 素数环 ##

时间限制：1000 ms | 内存限制：65535 KB

难度：2

描述

有一个整数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

来源

[hdu改编][hdu]

上传者

[ACM\_丁国强][ACM]

#include<stdio.h>
    #include<string.h>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int ss[50];
    int ans[50];
    int vis[50];
    int nn;
    int jj(int x)
    {
    	for(int i=2;i<=sqrt(x);i++)
    	{
    		if(x%i==0)
    		{
    			return 0;
    		}
    	}
    	return 1;
    }
    bool cnm=0;
    void dfs(int x)
    {
    	if(x==nn+1&&ss[ans[1]+ans[nn]]==1)
    	{
    		cnm=1;
    		for(int i=1;i<=nn;i++)
    		{
    			if(i==1)
    			printf("%d",ans[i]);
    			else
    			printf(" %d",ans[i]);
    		}
    		printf("\n");
    		return ;
    	}
    	else
    	{
    		for(int i=2;i<=nn;i++)
    		{
    			if(vis[i]==0)
    			{
    				if(ss[ans[x-1]+i]==1)
    				{
    					ans[x]=i;
    					vis[i]=1;
    					dfs(x+1);
    					vis[i]=0;
    				}
    			}
    		}
    	}
    	return ;
    }
    int main()
    {
    	memset(ss,0,sizeof(ss));
    	ss[2]=1;
    	ss[3]=1;
    	for(int i=4;i<50;i++)
    	{
    		if(jj(i))
    		{
    			ss[i]=1;
    		}
    	}	
    	int av3344=0;
    	while(scanf("%d",&nn)!=EOF)
    	{
    		if(nn==0)
    		break;
    		printf("Case %d:\n",++av3344);
    		if(nn==1)
    		{
    			printf("1\n");
    		}
    		else if(nn%2==1)
    		{
    			printf("No Answer\n");
    		}	
    		else
    		{
    			memset(vis,0,sizeof(vis));
    			memset(ans,0,sizeof(ans));
    			ans[1]=1;
    			vis[1]=1;
    			dfs(2);
    			if(cnm==0)
    			{
    				printf("No Answer\n");
    			}
    		}
    	}
    	return 0;
    }

[20120315192417_81102.gif]: http://acm.nyist.net/JudgeOnline/admin/kind/attached/20120315192417_81102.gif
[hdu]: http://acm.nyist.net/JudgeOnline/search_result.php?source=hdu%E6%94%B9%E7%BC%96
[ACM]: http://acm.nyist.net/JudgeOnline/profile.php?userid=ACM_%E4%B8%81%E5%9B%BD%E5%BC%BA