1016素数环的搜索

本文主要是介绍1016素数环的搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*1-n的自然数组成一个环，使得每相邻的两个数的和是素数。

方法：回溯法。

1是初始，寻找1后面的数字，2-n的每个数都代表搜索的方向。*/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int mark[20];
int cc[20];
bool prime(double x)
{//判断 和 是否为素数int i=2;for(;i<=sqrt(x);i++){if((int)x%i==0)return false;}return true;
}
void dfs(int x)
{//寻找x后面的元素if(x==n&&prime(1.0+cc[x])){//结束条件，不是说x=n了，而是说x是第n位数了。x是个位置坐标。for(int i=1;i<=n;i++){//输出if(i==1) cout<<cc[i];else cout<<" "<<cc[i];}cout<<endl;}else{for(int i=2;i<=n;i++){//2-n的方向，方向指1后面可以是2-n的任意一个。

            if(!mark[i]&&prime(cc[x]+(double)i)){//cc[x]是当前的，i是判断是否要加的，这个i是n的元素之一
                cc[x+1]=i;//从1开始使用下标，寻找的是x后面的位置的元素，即x+1位置上的元素
                mark[i]=1;//标记该元素已经被使用了dfs(x+1);//下一步搜索mark[i]=0;//回溯}}}
}
int main()
{int t=1;while(cin>>n){memset(mark,0,sizeof(mark));cc[1]=mark[1]=1;//从1开始方便保存cout<<"Case "<<t<<":"<<endl;t++;if(n==1)cout<<n<<endl<<endl;else{dfs(1);}cout<<endl;}return 0;
}

这篇关于1016素数环的搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---