首页 > 代码库 > DFS搜索题素数环

DFS搜索题素数环

2024-07-16 11:08:26   214人阅读

素数环：

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

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

Sample:

input:

6

output:

1 4 3 2 5 6 

1 6 5 2 3 4

 

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

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

代码如下：

 1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 const int N=100; 5 int vis[N],ans[N]; 6 int n; 7 bool flag; 8 bool is_prime(int x)//判断两个数据相加是否为素数 9 {10     for(int i=2;i*i<=x;i++)11     if(x%i==0)return false;12     return true;13 }14 void dfs(int cur)15 {16     if(cur==n+1)17     {18         if(is_prime(ans[n]+ans[1]))19         {20             for(int i=1;i<=n;i++)21             {22                 if(i>1)cout<<" ";23                 cout<<ans[i];24             }25                 cout<<endl;26         }27         return;28     }29     for(int i=2;i<=n;i++)30     {31         if(!vis[i]&&is_prime(ans[cur-1]+i))32         {33             vis[i]=1;34             ans[cur]=i;35             dfs(cur+1);36             vis[i]=0;37         }38     }39     return;40 }41 int main()42 {43     while(cin>>n)44     {45         flag=false;46         memset(vis,0,sizeof(vis));47         ans[1]=1;48         dfs(2);//第一个数已经固定为1，就从2开始搜索49     }50     return 0;51 }

 


联系
我们