真题（来自一本通）

2110：【例5.1】素数环

时间限制: 1000 ms 内存限制: 65536 KB
提交数:19024 通过数: 7285

【题目描述】

【输入】

【输出】

【输入样例】

6

【输出样例】

4 3 2 5 6 1

【提示】

这题我们用深搜

#include<bits/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(i+path[x-1])==1) {//判断跟上一个数是不是一样的质数 path[x] = i; vis[i] = true;//用过了 if(dfs(x+1)==1) return true;//递推下去 vis[i] = false; } } return false; } int main(){ cin>>n; path[1] = 1; vis[1] = true; dfs(2);//第1层一定不重复 return 0; }

递推过程：