搜素与回溯 素数环:

素数环:

从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。

书上算法分析：

【算法分析】

非常明显，这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。

【算法流程】

1、数据初始化；   2、递归填数：判断第i个数填入是否合法；

A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；

B、如果不合法：选择下一种可能；

代码实现：（自己手打一遍，加上自己的理解）

#include<bits/stdc++.h>
using namespace std;
bool b[21]={0};
int total=0,a[21]={0};
int print();             //输出答案
bool pd(int x,int y);    //判断素数
int search(int x);       //回溯方案
int main()
{

   search(1);
   cout<<total<<endl;    //这是总方案数
   return 0;
}
int search(int x)
{
    int i;
    for(i=1;i<=20;i++)
        if(pd(a[x-1],i)&&!b[i])//和是否为素数  该数是否可用
    {
        a[x]=i;          
        b[i]=1;
        if(x==20)
        {
            pd(a[20],a[1]);
            print();
        }
        else search(x+1);
        b[i]=0;              //可以选择不用这个数，保证每种方案
    }
}
bool pd(int x,int y)
{
    int i=x+y,j=2;
    while(j<=sqrt(i)&&i%j!=0)
        j++;
        if(j>sqrt(i))  return 1;
        else       return 0;
}
int print()
{
   total++;
   cout<<"<"<<total<<">";    //第几种方案
   for(int j=1;j<=20;j++)    //素数圈
     cout<<a[j]<<" ";
   cout<<endl;
}