2110【例5.1】素数环时间限制: 1000 ms 内存限制: 65536 KB提交数:19024 通过数: 7285【题目描述】输入正整数nn把整数11,22,…,nn 组成一个环使得相邻两个整数之和均为素数。【输入】输入正整数nn。【输出】输出任意一个满足条件的环。【输入样例】6【输出样例】4 3 2 5 6 1【提示】数据满足4≤n≤3讲解及代码这题我们用深搜#includebits/stdc.h using namespace std; bool vis[50]; int path[50]; int n; bool check(int x){//判断是否是素数 if(x 2) return false;//素数必须大于2 int t sqrt(x); for(int i 2; i t;i) if(x % i 0) return false; return true; } bool dfs(int x){ if(x n){ if(check(path[1] path[n])1) {//头尾不能是一样的素数 for(int i 1;i n;i) cout path[i] ; return true; }else return false; } for(int i 1;i n;i){ if(vis[i]) continue; if(check(ipath[x-1])1) {//判断跟上一个数是不是一样的质数 path[x] i; vis[i] true;//用过了 if(dfs(x1)1) return true;//递推下去 vis[i] false; } } return false; } int main(){ cinn; path[1] 1; vis[1] true; dfs(2);//第1层一定不重复 return 0; }递推过程第一层i上一个数不重复进入下一层重复继续循环第2层i上一个数不重复进入下一层重复继续循环第3层i上一个数不重复进入下一层重复继续循环第4层i上一个数不重复进入下一层重复继续循环最后一层i上一个数不重复判断头尾是否重复重复继续循环