codevs1031 质数环

一个大小为N(N<=17)的质数环是由1到N共N个自然数组成的一个数环，数环上每两个相邻的数字之和为质数。如下图是一个大小为6的质数环。为了方便描述，规定数环上的第一个数字总是1。如下图可用1 4 3 2 5 6来描述。若两个质数环，数字排列顺序相同则视为本质相同。现在要求你求出所有本质不同的数环。

思路：

1、首先素数环，就一定要进行素数判定，考虑n<=17,可以直接暴力求出来,或者说直接可以开一个数组，把与i的和为素数的j从小到大记录下来

2、由于要输出字典序最小的方案，所以第一个一定是一，把一作为第一个数，进行深搜，用刚才预处理好的j从小到大都试一边，然后往下递归，知道找到解位置，找不到解就输出-1

代码：

#include<iostream>

#include<cmath>

#include<vector>

using namespace std;

int isprime[],j[],ans[],vis = ,n;

vector<int> a[];

void judge_prime(){

    bool judge;

    for(int i = ;i <= ;i++){

        isprime[i] = ;

        for(int j = ;j <= i / ;j++){

            if(i % j == ){

                isprime[i] = ;

                break;

            }

        }

    }

}

void judge_add(){

    for(int i = ;i <= n;i++){

        for(int j = i+;j <= n;j++){

            if(isprime[i+j]){

                a[i].push_back(j);

                a[j].push_back(i);

            }

        }

    }

}

void dfs(int deep,int last){

    int k;

    if(deep == n){

        if(!isprime[last+]) return;

        for(int i = ;i <= n;i++) cout<<ans[i]<<" ";

        cout<<endl;

        return;

    }

    for(int i = ;i < a[last].size();i++){

        if(i >= a[last].size()) break;

        k = a[last][i];

        if(!j[k]){

            ans[deep+] = k;

            j[k] = ;

            dfs(deep+,k);

            j[k] = ;

        }

    }

}

int main(){

    judge_prime();

    cin>>n;

    judge_add();

    ans[] = ;

    j[] = ;

    dfs(,);

    return ;

}

巴特西

codevs1031 质数环

最新文章

热门文章