本文主要是介绍1358 - 素数环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
从 1 \sim n1∼n 这 nn 个数，摆成一个环，要求相邻的两个数的和是素数，按照由小到大请输出所有可能的摆放形式。
比如：n = 4n=4，输出形式如下；
1:1 2 3 4
2:1 4 3 2
3:2 1 4 3
4:2 3 4 1
5:3 2 1 4
6:3 4 1 2
7:4 1 2 3
8:4 3 2 1
total:8
比如：n = 6n=6，输出形式如下；
1:1 4 3 2 5 6
2:1 6 5 2 3 4
3:2 3 4 1 6 5
4:2 5 6 1 4 3
5:3 2 5 6 1 4
6:3 4 1 6 5 2
7:4 1 6 5 2 3
8:4 3 2 5 6 1
9:5 2 3 4 1 6
10:5 6 1 4 3 2
11:6 1 4 3 2 5
12:6 5 2 3 4 1
total:12
输入
一个整数 nn ；（2 \le n \le 102≤n≤10）
输出
前若干行，每行输出一个素数环的解，最后一行，输出解的总数。
样例
输入
4
输出
1:1 2 3 4
2:1 4 3 2
3:2 1 4 3
4:2 3 4 1
5:3 2 1 4
6:3 4 1 2
7:4 1 2 3
8:4 3 2 1
total:8
来源
回溯
#include<bits/stdc++.h>
using namespace std;
const int inf=11;
int n,use[inf],f=0;
bool vis[inf];
void print(){printf("%d:",++f);for(int i=1;i<=n;i++){printf("%d ",use[i]); }printf("\n");
}
bool prime(int n){if(n<=1){return false;}for(int i=2;i*i<=n;i++){if(n%i==0){return false;}}return true;
}
void dfs(int k){if(k==n){bool flag=false;for(int i=1;i<n;i++){if(!prime(use[i]+use[i+1])){flag=true;}}if(!flag&&prime(use[1]+use[n])){print();}}for(int i=1;i<=n;i++){if(!vis[i]){vis[i]=true;use[k+1]=i;dfs(k+1);vis[i]=false;}}
}
int main(){cin>>n;dfs(0);printf("total:%d",f);return 0;
}这篇关于1358 - 素数环的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
