輸入正整數n，把整數1，2，3，···n組成一個環，使得相鄰兩個整數之和均為素數。輸出時從整數1開始逆時針排列。同一個環應恰好輸出一次。n16。

回溯法

#include<iostream> #include <string> #include <string.h> #include<math.h>using namespace std; int vis[16+5]; int n; int tot = 0; int c[16+5]; int isp[40]; void dfs(int cur) {if (cur == n && isp[c[0] + c[n - 1]]) {for (int i = 0; i < n-1; i++)cout << c[i] << " ";cout << c[n - 1];cout << endl;}elsefor (int i = 2; i <= n; i++) {if (!vis[i] && isp[c[cur-1] + i]) {//頭節點是確定的vis[i] = 1;c[cur] = i;dfs(cur + 1);vis[i] = 0; //循環遍歷每一種情況}} } int main() { #ifdef LOCALfreopen("data.in", "r", stdin);//scanffreopen("data.out", "w", stdout);//printf #endifint kase = 0;for (int i = 1; i <= 2 * 16; i++) {bool isok = true;for (int j = 2; j <= sqrt(i); j++) {if (i%j == 0)isok = false;}if (isok)isp[i] = 1;}while (scanf("%d", &n)==1&&n) {if(kase)cout<<endl;kase++;cout << "Case " << kase << ":"<<endl;memset(vis, 0, sizeof(vis));memset(c, 0, sizeof(c));c[0] = 1;dfs(1);//cout << endl;}//system("pause");return 0; }

?

總結

以上是生活随笔為你收集整理的UVA524 PrimeRingProblem素数环的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。