一、题目
https://www.luogu.org/problemnew/show/UVA524
二、分析
例1:以n = 4为例。n = 4的排列有
1,2,3,4 相邻两个数相加都是素数,符合题意
1,3,2,4 2和4相加不是素数,不符合题意
1,3,4,2 4和2相加不是素数,不符合题意
1,4,2,3 4和2相加不是素数,不符合题意
1,4,3,2 相邻两个数相加都是素数,符合题意。
所以正确的答案为
1,2,3,4
1,4,3,2
例2:以n = 5为例。n = 5的排列有
1,2,3,4,5 4和5相加不是素数,不符合题意
1,2,3,5,? 3和5相加不是素数,不符合题意
1,2,4,? 2和4相加不是素数,不符合题意
1,2,5,3,? 5和3相加不是素数,不符合题意
1,2,5,4,? 5和4相加不是素数,不符合题意
1,3,? 1和3相加不是素数,不符合题意
1,4,2,? 4和2相加不是素数,不符合题意
1,5,? 1和5相加不是素数,不符合题意
所以n=5时,没有答案。
三、代码
#include<bits/stdc++.h>
using namespace std;
int n,i,cnt,a[100];
int prime[100];
bool visited[100]; //标记visited[i]是否被用过
void dfs(int pos)
{
for(int i=2; i<=n; i++)
{
if(!visited[i] && prime[a[pos-1] + i]) //i没有用过,且与上一个数的和为素数
{
visited[i] = true; // 标记
a[pos]=i; // 存储
if(pos == n) // 放完了n个数
{
if(prime[a[pos] + 1]) //这是一个环,所以最后一个数和第一个数1相邻
{
for(int j=1;j<n;j++)
{
printf("%d ",a[j]);
}
printf("%d",a[n]); //这里很恶心,行末不能有空格
printf("\n");
}
}
else
{
dfs(pos+1);
}
visited[i] = false; //回溯
}
}
}
int main()
{
// 素数打表
prime[2]=prime[3]=prime[5]=prime[7]=prime[11]=prime[13]=prime[17]=prime[19]=prime[23]=prime[29]=prime[31]=1; //先处理一下素数
while(scanf("%d",&n) == 1)
{
cnt++;
printf("Case %d:\n",cnt);
a[1]=1; //第一个数是1
dfs(2); //从第二个数开始搜
cout << endl;
}
return 0;
}
少儿编程、信息学竞赛咨询请加微信307591841或QQ群581357582
信息学竞赛公众号.jpg
网友评论