DFS搜索题素数环

时间:2023-03-08 22:05:06

素数环:

输入整数1,2,3,4,5,···,n组成一个环,使得相邻两个整数之和均为素数。

输出时从整数1开始逆时针排列。同一个环应恰好输出一次。n<=16.

Sample:

input:

6

output:

1 4 3 2 5 6

1 6 5 2 3 4

使用DFS搜索解释:素数环的第一个数为1,则选定第一个数为1,然后向下遍历所有数据,能够和前面一个数据组合相加成为素数的数就被数组记录下来。

知道判断到最后一个数字,然后检查它和第一个数相加是否为素数,若是就输出数组中记录的答案,不是就从头开始。

代码如下:

 #include<iostream>
#include<cstring>
using namespace std;
const int N=;
int vis[N],ans[N];
int n;
bool flag;
bool is_prime(int x)//判断两个数据相加是否为素数
{
for(int i=;i*i<=x;i++)
if(x%i==)return false;
return true;
}
void dfs(int cur)
{
if(cur==n+)
{
if(is_prime(ans[n]+ans[]))
{
for(int i=;i<=n;i++)
{
if(i>)cout<<" ";
cout<<ans[i];
}
cout<<endl;
}
return;
}
for(int i=;i<=n;i++)
{
if(!vis[i]&&is_prime(ans[cur-]+i))
{
vis[i]=;
ans[cur]=i;
dfs(cur+);
vis[i]=;
}
}
return;
}
int main()
{
while(cin>>n)
{
flag=false;
memset(vis,,sizeof(vis));
ans[]=;
dfs();//第一个数已经固定为1,就从2开始搜索
}
return ;
}