HDU 1016 Prime Ring Problem（深搜+回溯+剪枝+Eratosthenes素数筛）

Prime Ring Problem

A ring is compose of n circles as shown in diagram. Put natural number 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 < 20).

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. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

Sample Input

6 8

Sample Output

Case 1: 1 4 3 2 5 6 1 6 5 2 3 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-n连成一个环，使得相邻的两个数和为素数，并且从1开始逆时针围成的环，输出可行的方案，并按字典序输出。0<n<20。每个样例与下一个样例间隔一个空行。 题目有点小坑，它没有说只能数字之间有空格，害我提交的时候PE了 废话不多说，现在来讲思路，首先要用到Eratosthenes素数筛，求出2-40内的素数，因为20+20=40，两数之和最大也不会超过40。然后就开始深搜dfs，剪枝，回溯，详细参见代码。

#include <iostream> #include <cstring> using namespace std; int prime[40] = {0}, vis[40] = {0}, pre[25], cnt = 0, n;//pre数组存储素数环，vis数组表示访问过的元素，prime数组为0表示素数 void init() { for(int i = 2; i <= 7; i++) { if(!prime[i]) for(int j = i * i; j < 40; j += i) prime[j] = 1; } } void dfs(int cur) { if(cur == n) { if(!prime[pre[n - 1] + pre[0]]) { for(int i = 0; i < n - 1; i++) printf("%d ", pre[i]); printf("%d\n", pre[n - 1]); } } for(int i = 2; i <= n; i++) { if(!vis[i] && !prime[pre[cur - 1] + i]) //如果没有访问过的数字并且与前一个数字相加为素数，则继续搜下一个，并且将这个数字标记为已访问 { vis[i] = 1; pre[cur] = i; dfs(cur + 1); vis[i] = 0; //完成本次搜索后取消标记，以免下次搜索时没有访问被误判为访问过的数字 } } } int main() { init(); int cnt = 0; while(scanf("%d", &n) != EOF){ printf("Case %d:\n", ++cnt); memset(vis, 0, sizeof(vis)); pre[0] = 1; dfs(1); printf("\n"); } return 0; }

End