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.创建数组a[21]用来存放当前素数环,a[0]存放1
2.循环变量i从2开始搜索,if (isprime(a[cur]+i)  )  a[cur+1] = i ;并标记i被访问, 然后搜索第 cur+1 个素数,如果搜索第cur+1个素数不成功,再次把i标记为1
3.如果 cur(当前素数个数)== n-1 ,判断最后一个元素和 1 是否相加为素数,是则输出数组 a

 
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int a[21]={1};
bool visit[21];
int n;

bool isprime(int x)
{
	int i;
	for(i=2;i*i<=x;i++)
	{
		if(x%i==0)return false;
	}
	return true;
}
void DFS(int x)
{
	int i;
	if(x==n-1) 
	{
		if(isprime(a[x]+1))
		{
			printf("1");
			for(i=1;i<n;i++)
				printf(" %d",a[i]);
				puts(""); 
			return;
		}
	}
	
	for(i=2;i<=n;i++)
	{
		
		if(!visit[i] && isprime(a[x]+i))
		{
			visit[i]=1;
			a[x+1]=i;
			DFS(x+1);
			visit[i]=0;
		}		
	}
}
int main()
{	
	int i;
	int Case=1;
	while(scanf("%d",&n),n)
	{
		memset(visit,0,sizeof(visit));
		
		printf("Case %d:\n",Case++);
		if(n%2==0 || n==1 )
			DFS(0);			
		else printf("No Answer\n");		
	}
	return 0;
}        


 

别人的改进代码,时间0

素数较少,打表给出,减少判断时间

 
# include <iostream>
# include <algorithm>
using namespace std;
bool sushu[]={0,
0,1,1,0,1,0,1,0,
0,0,1,0,1,0,0,0,
1,0,1,0,0,0,1,0,
0,0,0,0,1,0,1,0,
0,0,0,0,1,0,1,0
};
int a[21], res[21], n, flag;
void dfs(int now)
{
	int i;
	if (now==n&&sushu[a[n-1]+a[n]])
	{
		flag = 0;
		for (i = 0; i<n; i++)
			cout<<a[i]<<" ";
		cout<<endl;
	}
	else
	{
		for (i = 2; i<=n; i++)
			if (!res[i]&&sushu[i+a[now-1]])
			{
				res[i] = 1;
				a[now] = i;
				dfs(now+1);
				res[i] = 0;
			}
	}
}
int main()
{
	int N;
	N=1;
	while (cin>>n&&n)
	{
		flag = 1;
		a[0]=a[n]=1;
		cout<<"Case "<<N++<<":"<<endl;
		if ((n-1)&1||n==1)
			dfs(1);
		if (flag)
			cout<<"No Answer\n";
	}
	return 0;
}