题目描述：

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.

输入：

n (1 < n < 17).

输出：

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.

样例输入：

68

样例输出：

Case 1:1 4 3 2 5 61 6 5 2 3 4Case 2:1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 2

Code:

#include <cstdio> using namespace std; const int arrSize=22;int ans[arrSize];     //保存环中每一个被放入的数bool hash[arrSize];   //标记之前已经被放入环中的数int n;int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41};  //在给定范围内的素数集合 bool isPrime(int x){    for(int cnt=0;cnt<13;++cnt){        if(x==prime[cnt])            return true;    }    return false;} void check(){                             //检查输出由回溯法枚举得到的解    if(isPrime(ans[n]+ans[1])==false)     //判断最后一个数与第一个数的和是否为素数，若不是则直接返回        return;    for(int cnt=1;cnt<=n;++cnt){        if(cnt!=1)            printf(" ");        printf("%d",ans[cnt]);    }    printf("\n");} void DFS(int num){     //递归枚举,num为ans数组中已经放入数字的个数    if(num>1){         //当放入数字的个数大于1时        if(isPrime(ans[num]+ans[num-1])==false)            return;    }    if(num==n){        //当放入的数字的个数等于n时        check();        return;    }    for(int cnt=2;cnt<=n;++cnt){        if(hash[cnt]==false){            hash[cnt]=true;            ans[num+1]=cnt;            DFS(num+1);            hash[cnt]=false;   //能执行到这儿就说明当前num+1个数确定为ans[1]到ans[num+1]时,        }                      //所有情况都已经处理过，所以要把hash[i]重新标记为未使用过。    }} int main(){    int cas=0;    while(scanf("%d",&n)!=EOF){        ++cas;        for(int cnt=0;cnt<arrSize;++cnt){            hash[cnt]=false;        }        ans[1]=1;        printf("Case %d:\n",cas);        hash[1]=true;        DFS(1);        printf("\n");    }    return 0;} /**************************************************************    Problem: 1459    User: lcyvino    Language: C++    Result: Accepted    Time:590 ms    Memory:1020 kb****************************************************************/

 

题目1459：Prime ring problem