【原创】
有这样一个有趣的问题，输入n，然后取1<x<n中的数，围成一个环，使得相邻的两个数和为素数，并且第一个数一定是1，输出所有的可能序列，比如说输入n=6，那么得到的序列是1 4 3 2 5 6、1 6 5 2 3 4这样两个序列，不难验证，这个环就满足条件，那么利用我们的代码来实现
利用递归回溯的方法，即试探性的往下走，若走到一个地方发现不满足条件，则返回上一个状态从新选择，结合这一主要思想，有如下代码，其中仍然接受多组输入数据，即可以多次输入n，
代码：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 //递归回溯法 5 int ans[22];// 保存环中每一个被放入的数 6 bool hash[22];//标记之前已经被放入的数 7 int n;//全局的n，表示输入的数字，题目要求1<n<17,即最大为16 8 int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41};//由于n最大为16，因而其最大和素数在这里面 9 bool judge(int x){ 10 //判断x是否为素数 11 for (int i = 0; i<13; i++) { 12 if (prime[i]==x) { 13 return true;//是 14 } 15 } 16 return false;//不是 17 } 18 //检查解 19 void check(){ 20 if(judge(ans[n]+ans[1])==false)return;//这里只用检查最后一个数字和第一个数字和是否为素数了 21 for(int i = 1;i<=n;i++){ 22 if (i!=1) { 23 printf(" ");//最后一个无空格 24 } 25 printf("%d",ans[i]); 26 } 27 printf(" "); 28 } 29 //递归枚举 30 void DFS(int num){//num为当前已经放入环中的数字量 31 if(num>1) 32 if (judge(ans[num]+ans[num-1])==false) return;//表示相邻的这两个数和不为素数 33 if(num==n){//当放入个数已经达到n，检查了，这就是为什么check函数中只用判断最后一次放入是否有效，其实，这里完全不用check，直接在这里判断judge(ans[n]+ans[1])==true?.然后输出，但是为了方便分离，所以单独写了一个函数 34 check(); 35 return; 36 } 37 for(int i = 2;i<=n;i++){//放入一个数，这就是递归的魅力，要脑袋里结合一组数据来查看这里的执行 38 if(hash[i]==false){//i是待放入环中的数字， 39 hash[i]=true; 40 ans[num+1] = i;//一定是num+1哦， 41 DFS(num+1); 42 hash[i] = false;//当在上一层中return回来之后，这里一定要将hash[i]重新设置为false哦；方便后继的使用， 43 } 44 45 } 46 } 47 int main() { 48 int Case = 0; 49 while (scanf("%d",&n)!=EOF) { 50 Case++; 51 for (int i = 0; i<22; i++) { 52 hash[i] = false; 53 } 54 ans[1] = 1;//第一个横为1，上面已经做了标记处理，所以这里不再需要考虑ans数组中残留的上一组数据 55 printf("Case %d: ",Case); 56 hash[1] = true; 57 DFS(1);//一开始都是从放入环1开始 58 printf(" "); 59 } 60 return 0; 61 } 62 63 /************************************************************** 64 Problem: 1459 65 User: Numen_fan 66 Language: C++ 67 Result: Accepted 68 Time:600 ms 69 Memory:1020 kb 70 ****************************************************************/
注：这份代码注释蛮详细的，建议结合一组输入，跟随着代码进行简单的调试，在草稿纸上进行手工理解，才能彻底理解；