DFS搜索题素数环

素数环：

输入整数1,2,3,4,5，···，n组成一个环，使得相邻两个整数之和均为素数。

输出时从整数1开始逆时针排列。同一个环应恰好输出一次。n<=16.

Sample:

input:

output:

1 4 3 2 5 6

1 6 5 2 3 4

使用DFS搜索解释：素数环的第一个数为1，则选定第一个数为1，然后向下遍历所有数据，能够和前面一个数据组合相加成为素数的数就被数组记录下来。

知道判断到最后一个数字，然后检查它和第一个数相加是否为素数，若是就输出数组中记录的答案，不是就从头开始。

代码如下：

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int N=;

 int vis[N],ans[N];

 int n;

 bool flag;

 bool is_prime(int x)//判断两个数据相加是否为素数

 {

     for(int i=;i*i<=x;i++)

     if(x%i==)return false;

     return true;

 }

 void dfs(int cur)

 {

     if(cur==n+)

     {

         if(is_prime(ans[n]+ans[]))

         {

             for(int i=;i<=n;i++)

             {

                 if(i>)cout<<" ";

                 cout<<ans[i];

             }

                 cout<<endl;

         }

         return;

     }

     for(int i=;i<=n;i++)

     {

         if(!vis[i]&&is_prime(ans[cur-]+i))

         {

             vis[i]=;

             ans[cur]=i;

             dfs(cur+);

             vis[i]=;

         }

     }

     return;

 }

 int main()

 {

     while(cin>>n)

     {

         flag=false;

         memset(vis,,sizeof(vis));

         ans[]=;

         dfs();//第一个数已经固定为1，就从2开始搜索

     }

     return ;

 }

巴特西

DFS搜索题素数环

最新文章

热门文章