题意：给定一个整数，求其满足起点为1的素数环，，并把所有的素数环输出来。
#include <iostream> #include<cstdio> using namespace std; int ans[22];//保存环中每一个被放入的数 bool hash1[22];//标记之前已经被放入环中的数 int n; int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41};//素数 bool judge(int x){//判断一个数是否是素数 for(int i=0;i<13;i++){ if(prime[i]==x) return true; } return false; } void check(){//检查输出由回溯法枚举得到的解 if(judge(ans[n]+ans[1])==false) return; for(int i=1;i<=n;i++){ if(i!=1) printf(" "); printf("%d",ans[i]); } printf(" "); } void DFS(int num){ if(num>1) if(judge(ans[num]+ans[num-1])==false)//最后两个数字和是否为素数 return; if(num==n){//若已经放入了n个数 check();//检查输出 return;//返回，继续枚举下一组解 } for(int i=2;i<=n;i++){//放入一个数 if(hash1[i]==false){//若i还没放入环中 hash1[i]=true;//标记为已经使用 ans[num+1]=i;//将这个数字放入ans数组中 DFS(num+1);//继续尝试放入下一个数 hash1[i]=false;//重新标记为未使用 } } } int main() { int cas=0; while(scanf("%d",&n)!=EOF){ cas++; for(int i=0;i<22;i++) hash1[i]=false;//初始化标记所有数字为未被使用 ans[1]=1;//第一个数恒定为1 printf("Case %d: ",cas); hash1[1]=true;//标记1为被使用 DFS(1);//继续尝试放入下一个数字 printf(" "); } return 0; }
尝试放入第num+1个数字时，我们依次尝试放入所有在之前位置上未被使用的数字，假设当前x未被使用，将x放入第num+1个位置，标记x为已用，此时环中前num+1个数字全部确认，依次保存在ans[1]到ans[num+1]中，再进行下一个位置的枚举，即递归调用DFS。
当调用返回时，意味着当前num+1个数字确定为ans[1]到ans[num+1]中的值时对应的所有可行的答案已经全部处理完毕，此时需要改变ans[num+1]的值，从而进行新答案的搜索。
所以，此时ans[num+1]的值将不再为已经被枚举过的x，而是一个相异于x，同时又未在之前被使用过的新数字。那么对后续数字而言，x是未被使用过的，是可以被放入后序任何一个位置的，所以重新标记x为未使用，供后续数位选择。