搜索部分学习小结

搜索分为广度搜索与深度搜索，不同的题目有不同的解决方法，有的题目两种方法都适用，但是总有一种相对简单，有的时候我们对于使用的方法是可知的，有的时候却是未知的。
看了看例题但仍然不会做，最近事情也好多，好没有精力去投入，要加油啊！
下面是广搜与深搜的模板框架：
广度优先搜索：

While Not Queue.Empty ()
Begin
可加结束条件
Tmp = Queue.Top ()
从Tmp循环拓展下一个状态Next
If 状态Next合法 Then
Begin
生成新状态Next
Next.Step = Tmp.Step + 1 
Queue.Pushback (Next)
End
Queue.Pop ()
End

深度优先搜索：深搜分递归与非递归两种方法：
递归实现：

Function Dfs (Int Step, 当前状态)
Begin
可加结束条件
从当前状态循环拓展下一个状态Next
If 状态Next合法 Then
Dfs (Step + 1, Next ))
End

非递归实现：

While Not Stack.Empty ()
Begin
Tmp = Stack.top()
从Tmp拓展下一个未拓展的状态Next
If 没有未拓展状态(到达叶节点) Then
Stack.pop() 
Else If 状态Next合法 Then
Stack.push(Next)
End

下面写一个深搜递归的例题：
素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。
这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
bool b[21]={0};
int total=0,a[21]={0};
int search(int);                           //回溯过程
int print();                               //输出方案
bool pd(int,int);                          //判断素数
int main()
{
    search(1);
    cout<<total<<endl;                    //输出总方案数
}
int search(int t)
{
    int i;
    for (i=1;i<=20;i++)                     //有20个数可选
     if (pd(a[t-1],i)&&(!b[i]))         //判断与前一个数是否构成素数及该数是否可用
      {
         a[t]=i;
         b[i]=1;
         if (t==20) { if (pd(a[20],a[1])) print();}
             else search(t+1);
         b[i]=0;
      }
}
int print()
{
   total++;
   cout<<"<"<<total<<">";
   for (int j=1;j<=20;j++)
     cout<<a[j]<<" ";
   cout<<endl; 
  }
bool pd(int x,int y)
{
    int k=2,i=x+y;
    while (k<=sqrt(i)&&i%k!=0) k++;
    if (k>sqrt(i)) return 1;
       else return 0;
}

这道题目（大概以后的题目都是如此，search,printf等函数写到主函数之外，用于实现功能）
这样主函数的功能就很明确了，这有点像类的思想概念，所有功能尽量不使用主函数去调，而是从其他函数中去调用功能。我上次在弄ATM的时候记得就用的大模拟的思路，很多功能都弄到了主函数中（这样的代码就很不愿意让人看，思路虽然没问题，但是显得很乱，以后再做的时候会尽量用这种思路，把功能具体化，分到数据类与操作类中去。）

继续看例题，尽量试着再去做吧。