题目描述： Description
A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 1,2,3，…，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
解题思路： 这是一道回溯法的模板题。如果纯暴力的话，你会发现是很大的结果。而你预先处理下素数，再dfs进行回溯，就可以很快的找到答案。
AC代码：
#include<cstring> #include<iostream> #include<cstdio> #include<cmath> #define MAXN 30 using namespace std; int n , A[80],isp[80],vis[80]; int is_p(int x) { for(int i = 2 ; i*i<=x ; i++) { if(x%i==0) return 0; } return 1; } void dfs(int cur) { if(cur == n && isp[A[0]+A[n-1]]) { for(int i = 0 ; i < n ; i++) { if(i!=0) cout << " "; cout << A[i]; } cout << endl; } else for(int i = 2 ; i <= n ; i++) { if(!vis[i]&&isp[i+A[cur-1]]) { A[cur] = i; vis[i] = 1; dfs(cur+1); vis[i] = 0; } } } int main() { int kase = 0; while(scanf("%d",&n)==1&&n>0) { if(kase > 0) cout << endl; printf("Case %d:\n",++kase); for(int i = 2 ; i <= n*2 ; i++) { isp[i] = is_p(i); } // for(int i = 0 ; i < n ; i++) // { // cout << A[i] << ' '; // } // cout << endl; memset(vis,0,sizeof(vis)); A[0] = 1; dfs(1); } return 0; }