题目描述
如图所示为一个由n个圆圈构成的圆环。将自然数1，2，...，n放入圆圈内，并且要求任意两个相邻的圆圈内的数字之和为素数。请问给你圆圈数，你能给出放置自然数的所有正确方案吗？
注意：圆圈中的数字一定是从1开始的，并且连续不重复。
输入
一行，为整数n（1<n<20），表示圆圈数。
输出
输出所有正确的方案，按字典序从小到大排序。每组输出后输出一个换行。具体输出格式见输出样例。
注意：只能按照顺时针方向放置数字。如果无解，输出-1
样例输入
6
样例输出
1 4 3 2 5 6 1 6 5 2 3 4
Code:
#include<bits/stdc++.h>
using namespace std;
int n,tot,ans[21];
bool vis[21];
bool G[21][21];
bool isprime(int n){
if(n==1){
return false;
}else if(n==2){
return false;
}
for(int i=2;i<n;i++){
if(n%i==0)
return false;
}
return true;
}
void print(){
tot++;
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
void dfs(int st){
if(st==n+1){
if(G[ans[n]][1]){
print();
}
return;
}
for(int i=2;i<=n;i++){
if(vis[i]==0&&G[ans[st-1]][i]){
ans[st]=i;
vis[i]=true;
dfs(st+1);
vis[i]=false;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
G[i][j]=G[j][i]=isprime(i+j);
}
}
ans[1]=1;
vis[1]=true;
dfs(2);
if(tot==0){
cout<<-1<<endl;
}
return 0;
}
/**************************************************************
Problem: 2841
User: yangrenrui
Language: C++
Result: 正确
Time:18 ms
Memory:2212 kb
****************************************************************/
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/99345.html