1 // 2 // Created by Arc on 2020/5/1. 3 //劳动节快乐！ 4 5 /* 6 * 从一到二十个数摆成一个环，ｕ要求相邻两个数的和是素数（包括１和２０）,保证第一个数为一（要不每个还都要输出NUM遍） 7 * 输出所有环 8 */ 9 //多任务，挨个试，用回溯．．．回溯也是某种意义上的dfs吧 10
11 #include <bits/stdc++.h> 12 using namespace std; 13 bool b[100]={0};//判断下标为i的数有没有被用过 14 int a[100]={0};//判断每个数里面放的是什么 15 int total=0;//总个数 16 void print();//打印 17 bool pd(int ,int);//判断传入的两个数和是否为素数 18 int search(int);//回溯 19 int NUM; 20 21 int main(){ 22 a[1]=1;//确定第一个数为一，就不会出现重复环了，因为每个数只能出现一次 23 cin>>NUM; 24 search(2); 25 26 cout<<total<<endl; 27 return 0; 28 29 } 30 int search(int t){ 31 for(int i=２;i<=NUM;i++){ 32 /* 33 * 可以发现底下只有一个大的if 34 * 也就是说，如果满足条件，那就t+1继续执行 35 * 如果执行了发现后面走不动了，那就恢复为未使用状态，继续forｕ循环寻找 36 * 但是如果连条件都满足不了，直接会返回上层循环 37 * 回溯就是说，看看满不满足条件， 38 * 然后走下去 39 */ 40 if( pd(a[t-1],i)&&(!b[i])) {//判断相邻两个数之和是不是素数＆＆这个数是不是被用过 41 a[t] = i; 42 b[i] = 1; 43 44 if (t == NUM) {//递归边界 45 if (pd(a[1], a[NUM])) { 46 print(); 47 48 } 49 } 50 else 51 search(t+1); 52 b[i]=0; 53 54 55 56 } 57 58 } 59 return 0; 60 } 61 void print(){ 62 total++; 63 for (int i = 1; i <= NUM ; ++i) { 64 cout<<a[i]<<" "; 65 66 } 67 cout<<" "; 68 } 69 bool pd(int a,int b){ 70 int all=a+b; 71 int k=2; 72 while(k<=sqrt(all)&&(all%k)) 73 k++; 74 if(k>sqrt(all)) 75 return 1; 76 return 0; 77 }
有几个问题：
第一：有的版本说是不要把第一个数固定死，但是我觉得不这样的话，可能跑程序就像死循环．．
（根据xty dl的估计，正常的电脑，16大概需要20min,而20就需要8000min左右）
我一开始因为这个问题以为是死循环了．．．
第二个问题：
还是，在搞t,i回溯的时候千万别混了啊！有时候在i的for 里面出现的耸人听闻的j．．．．．