问题描述
如图所示，环由n个圆组成。将自然数1,2，…，n分别放入每个圆中，并且两个相邻圆中的数字总和应为素数。
注意：第一个圆圈的数量应该始终为1
#include<iostream> #include<string.h> #include<stdlib.h> //与第一个全排列问题差不多，只是判断条件变多了 using namespace std; int book[25]; int result[25]; int n; int num; //判断是否为素数 int prime(int n) { if(n<=1)//小于1则直接返回 { return 0; } int i; for(i=2;i*i<=n;i++)//遍历每一个数，但是使用开方来限制循环次数 { if(n%i==0)//不是素数，直接终止循环 { break; } } if(i*i>n)//循环完了之后，应该满足该条件，则是素数 { return 1; } return 0; } //判断是否能将当前的数字放到当前的圈内 int check(int i,int step) { if((book[i]==0)&&prime(i+result[step-1])==1)//能够放进去的条件就是，当前位置为空，并且当前要放入的数字和前面一个数字的和是素数要同时满足 { if(step==n-1)//判断尾部和第一个数的和是否构成素数 { if(!prime(i+result[0]))//不是素数，就返回0 { return 0; } } return 1;//剩下的情况都是满足的，可以直接填入数字 } return 0; } // void dfs(int step) { if(step==n)//判断边界 { int a; cout<<result[0]<<" ";//满足条件之后，先输出第一个数 for(a=1;a<n;a++)//然后循环输出所有的结果，结果存储在result数组当中 { cout<<result[a]<<" "; } cout<<endl; return; } int i; for(i=2;i<=n;i++)//从2到n遍历每一种情况 { if(check(i,step))//检查是否满足条件 { book[i]=1;//满足就标记当前位置 result[step]=i;//记录当前的结果 dfs(step+1);//继续往下搜索 book[i]=0;//恢复初始状态 } } } int main() { memset(result, 0, sizeof(result));//这两句是初始化result结果数组和book标记数组 memset(book,0,sizeof(book)); result[0]=1;//第一项要保持1，直接赋值 dfs(1);//然后从1开始进行遍历 cout<<endl; } return 0; }