首页 > 代码库 > codevs1031 质数环
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[100],j[100],ans[100],vis = 0,n;vector<int> a[100];void judge_prime(){ bool judge; for(int i = 1;i <= 40;i++){ isprime[i] = 1; for(int j = 2;j <= i / 2;j++){ if(i % j == 0){ isprime[i] = 0; break; } } }}void judge_add(){ for(int i = 1;i <= n;i++){ for(int j = i+1;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+1]) return; for(int i = 1;i <= n;i++) cout<<ans[i]<<" "; cout<<endl; return; } for(int i = 0;i < a[last].size();i++){ if(i >= a[last].size()) break; k = a[last][i]; if(!j[k]){ ans[deep+1] = k; j[k] = 1; dfs(deep+1,k); j[k] = 0; } }}int main(){ judge_prime(); cin>>n; judge_add(); ans[1] = 1; j[1] = 1; dfs(1,1); return 0;}
codevs1031 质数环
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。