2110【例5.1】素?cái)?shù)環(huán)時(shí)間限制: 1000 ms 內(nèi)存限制: 65536 KB提交數(shù):19024 通過數(shù): 7285【題目描述】輸入正整數(shù)nn把整數(shù)11,22,…,nn 組成一個(gè)環(huán)使得相鄰兩個(gè)整數(shù)之和均為素?cái)?shù)?！据斎搿枯斎胝麛?shù)nn。【輸出】輸出任意一個(gè)滿足條件的環(huán)。【輸入樣例】6【輸出樣例】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){//判斷是否是素?cái)?shù) if(x 2) return false;//素?cái)?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) {//頭尾不能是一樣的素?cái)?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) {//判斷跟上一個(gè)數(shù)是不是一樣的質(zhì)數(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層一定不重復(fù) return 0; }遞推過程第一層i上一個(gè)數(shù)不重復(fù)進(jìn)入下一層重復(fù)繼續(xù)循環(huán)第2層i上一個(gè)數(shù)不重復(fù)進(jìn)入下一層重復(fù)繼續(xù)循環(huán)第3層i上一個(gè)數(shù)不重復(fù)進(jìn)入下一層重復(fù)繼續(xù)循環(huán)第4層i上一個(gè)數(shù)不重復(fù)進(jìn)入下一層重復(fù)繼續(xù)循環(huán)最后一層i上一個(gè)數(shù)不重復(fù)判斷頭尾是否重復(fù)重復(fù)繼續(xù)循環(huán)