猫史档案馆

//1.1素数环

#include<bits/stdc++.h>

using namespace std;

int a[100]={0};

bool b[100]={0},n;

int sum=0;

bool f(int a,int b){

       int x=a+b;

       int i;

    if(c==2)return 1;

       for(i=2;i*i<=c;i++){

              if(c%i==0)return 0;

       }

       return 1;

}

int search(int k){

       int i;

       for(i=2;i<=n;i++){

              if(f(a[k-1],i)&&(!b[i])){

                     a[k]=i;b[i]=1;

                     if(k==n){

                            if(f(a[n],a[1])) sum++;

                     }

                     else{

                         search(k+1); 

                     }

                     b[i]=0;

              }

       }

}

int main(){

    int i;

    cin>>n;

    a[1]=1;

       search(2);

       cout<<sum<<endl;

       return 0;

}

以上是一个搜索经典案例：素数环。

深度优先搜索是比较重要的一种算法。

1.1素数环:从1到n(1<=n<=12）这n个数摆成一个环，要求相邻的两个数的和是一个素数。请输出方案总数。如果无解，输出"no solution!"（引号不输出)

那么我们这题呢是一个最基本的搜索，可以说是很简单的了。首先这个一定要完全理解，并且应完整的自己写出来（完全不借助任何提醒）。

好，那么我们再来回过头来分析一下这道题。比如n=6。我们写一个环：

在1号放一个1。2号可以放2~6，放了2后，3号位置其中3和5满足条件。

先试探3。3号放了3以后，4好位置可以放4，但放了4之后，均不可行。故而3号放3不可行。

接下来试探3号位置放5……

如此往复循环，直至所有可能性全部搜索完成。

所以，搜索基本框架可以表示为：

int search(int k)

{

       for(i=1;i<=可能的位置;i++)

       if(满足条件)

       {

              保存结果

              if(到达目的)相应的操作

              else search(k+1);

              回溯

       }

}

现在我们在来解析一下刚刚的代码：

b数组表示数字i有没有被用过。

a[i]表示放在环中的数字。

f函数的含义是判断素数。

Search中的k表示当前搜索的数。

整个函数解释如下：

int search(int k){

       int i;

       for(i=2;i<=n;i++){

              if(f(a[k-1],i)&&(!b[i])){

                     a[k]=i;b[i]=1;//记录状态

                     if(k==n){//到达目的

                            if(f(a[n],a[1])) sum++;//如果成功，sum加一

                     }

                     else{

                         search(k+1);  //搜索下一个数

                     }

                     b[i]=0;回溯

              }

       }

}

这样一轮解释下来，对这个解法就有了一定的理解。

爵士OIer

//1.1素数环

#include<bits/stdc++.h>

using namespace std;

int a[100]={0};

bool b[100]={0},n;

int sum=0;

bool f(int a,int b){

       int x=a+b;

       int i;

    if(c==2)return 1;

       for(i=2;i*i<=c;i++){

              if(c%i==0)return 0;

       }

       return 1;

}

int search(int k){

       int i;

       for(i=2;i<=n;i++){

              if(f(a[k-1],i)&&(!b[i])){

                     a[k]=i;b[i]=1;

                     if(k==n){

                            if(f(a[n],a[1])) sum++;

                     }

                     else{

                         search(k+1); 

                     }

                     b[i]=0;

              }

       }

}

int main(){

    int i;

    cin>>n;

    a[1]=1;

       search(2);

       cout<<sum<<endl;

       return 0;

}