传送门= ̄ω ̄=

思路:写个 judge(n) 函数在√n 的复杂度内判断 n 是否为质数,然后写 dfs(n) 深度优先搜索函数,n 表示当前枚举到了环的第 n 位,这一位和上一位的和必须为质数,如果枚举到最后一位了并且最后一位加1为质数就输出方案。

代码:

#include <iostream>
using namespace std;
int n,ans[20];
bool book[20];
bool judge(int num)
{
    for(int i=2;i*i<=num;i++)if(num%i==0)return 0;
    return 1;
}
void dfs(int cnt)
{
    if(cnt>n){if(judge(ans[n]+1)){for(int i=1;i<=n;i++)cout<<ans[i]<<' ';cout<<endl;}return;}
    for(int i=1;i<=n;i++)if(!book[i]&&judge(ans[cnt-1]+i))book[i]=1,ans[cnt]=i,dfs(cnt+1),book[i]=0;
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n,ans[1]=1,book[1]=1,dfs(2);
    return 0;
}

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注