首页 > 代码库 > UVa 524 Prime Ring Problem(回溯法)
UVa 524 Prime Ring Problem(回溯法)
传送门
Description
A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 1, 2, . . . , n into each circle separately, and the sum of numbers in two adjacent circles should be a prime. Note: the number of first circle should always be 1.
Input
n (0 < n ≤ 16)
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. You are to write a program that completes above process.
Sample Input
6 8
Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
思路
题意:
输入正整数n,把整数1,2,3,……,n组成一个环,使得相邻两个整数之和均为素数。输出时序列头为1开始的序列,同一个环应恰好输出一次
题解:
#include<bits/stdc++.h>using namespace std;const int maxn = 40;bool is_prime[maxn],vis[maxn];int n,a[maxn];void dfs(int cur){ if (cur == n && is_prime[a[0] + a[n-1]]) //递归边界,因为是环,所以还要测试第一个和最后一个 { printf("%d",a[0]); for (int i = 1;i < n;i++) printf(" %d",a[i]); printf("\n"); } else { for (int i = 2;i <= n;i++) //尝试放置每个数i { if (!vis[i] && is_prime[i + a[cur-1]]) //如果i没有用过,并且与前一个数之和为素数 { a[cur] = i; vis[i] = true; //设置使用标志 dfs(cur+1); vis[i] = false; //清楚标志 } } }}int main(){ //提前预处理素数表 memset(is_prime,true,sizeof(is_prime)); is_prime[0] = is_prime[1] = false; for (int i = 2;i < maxn;i++) { if (is_prime[i]) { for (int j = 2 * i;j < maxn;j += i) { is_prime[j] = false; } } } int tcase = 0; while (~scanf("%d",&n)) { memset(vis,false,sizeof(vis)); memset(a,0,sizeof(a)); if (tcase) printf("\n"); printf("Case %d:\n",++tcase); a[0] = 1; dfs(1); } return 0;}
UVa 524 Prime Ring Problem(回溯法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。