素数环
时间限制：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;
}