首页 > 代码库 > UVa524 Prime Ring Problem (回溯法)
UVa524 Prime Ring Problem (回溯法)
链接：http://acm.hust.edu.cn/vjudge/problem/19667
分析：先打个素数表，题目要求从1开始打印，直接把1固定到A[0]位置，打印的时候就可以直接从A[0]开始打印了，然后枚举2~n，vis判断之前是否用过，和是否为素数，都满足则继续递归枚举，然后回溯将vis还原。
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 int n, isp[35], A[20], vis[20]; 6 7 int is_prime(int x) { 8 for (int i = 2; i < x; i++) 9 if (!(x % i)) return 0;10 return 1;11 }12 13 void dfs(int cur) {14 if (cur == n)15 if (isp[A[0] + A[n - 1]]) {16 for (int i = 0; i < n; i++) {17 if (i != 0) cout << " ";18 cout << A[i];19 }20 cout << endl;21 } else return;22 else for (int i = 2; i <= n; i++)23 if (!vis[i] && isp[i + A[cur - 1]]) {24 A[cur] = i;25 vis[i] = 1;26 dfs(cur + 1);27 vis[i] = 0;28 }29 }30 31 int main() {32 int kase = 0;33 A[0] = 1;34 for (int i = 2; i < 32; i++) isp[i] = is_prime(i);35 while (cin >> n && n) {36 memset(vis, 0, sizeof(vis));37 if (kase++) cout << endl;38 cout << "Case " << kase << ":" << endl;39 dfs(1);40 }41 return 0;42 }
UVa524 Prime Ring Problem (回溯法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。