2110【例5.1】素數(shù)環(huán)時間限制: 1000 ms 內(nèi)存限制: 65536 KB提交數(shù):19024 通過數(shù): 7285【題目描述】輸入正整數(shù)nn把整數(shù)11,22,…,nn 組成一個環(huán)使得相鄰兩個整數(shù)之和均為素數(shù)。【輸入】輸入正整數(shù)nn?！据敵觥枯敵鋈我庖粋€滿足條件的環(huán)?！据斎霕永?【輸出樣例】4 3 2 5 6 1【提示】數(shù)據(jù)滿足4≤n≤3講解及代碼這題我們用深搜#includebits/stdc.h using namespace std; bool vis[50]; int path[50]; int n; bool check(int x){//判斷是否是素數(shù) if(x 2) return false;//素數(shù)必須大于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) {//頭尾不能是一樣的素數(shù) 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) {//判斷跟上一個數(shù)是不是一樣的質數(shù) 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上一個數(shù)不重復進入下一層重復繼續(xù)循環(huán)第2層i上一個數(shù)不重復進入下一層重復繼續(xù)循環(huán)第3層i上一個數(shù)不重復進入下一層重復繼續(xù)循環(huán)第4層i上一個數(shù)不重復進入下一層重復繼續(xù)循環(huán)最后一層i上一個數(shù)不重復判斷頭尾是否重復重復繼續(xù)循環(huán)