搜索分析（DFS、BFS、递归、记忆化搜索）

1、线性查找

在数组a[]={0,1,2,3,4,5,6,7,8,9,10}中查找1这个元素。

（1）普通搜索方法，一个循环从0到10搜索，这里略。

（2）递归（从中间向两边）

1 //递归一定要写成记忆化递归  2 #include 
      
        3 using namespace std; 4 bool vis[11]; 5 int count1=0; 6  7 void search(int n){ 8     count1++; 9     if(n>10||n<0||vis[n]){10         //cout<<"back"<

递归(从中间到两边)

这种方法一定要加标记数组，不然会出现死循环。

其中一个死循环：

search(9)->search(8)->search(9)

而这样的死循环太多了。

其实分析的时候直接把递归的树形图画出来就好了，直观而且方便。

这样带有标记数组的递归，本质上就是记忆化递归。

所以这种环形的递归都可以写成记忆化递归。

（3）递归（从后面向前面）

1 #include 
      
        2 using namespace std; 3  4 int count1=0; 5  6 void search(int n){ 7     count1++; 8     if(n>10||n<0){ 9     }10     else if(n==1){11         cout<<"find"<

递归(从后面向前面)

这种方法是不需要标记数组的，因为递归是线性的，而不是环形的，递归之间没有交叉，不会造成重复访问。

这种和求阶乘的是一样的。

（4）BFS（从中间向两边）

1 #include 
      
        2 using namespace std; 3 bool vis[11]; 4 int count1=0; 5 queue
       
         que; 6  7 void searchBFS(int n){ 8     que.push(n); 9     while(!que.empty()){10         count1++;11         cout<<"count1:"<
        
         <
         
          =0&&!vis[tmp-1]) que.push(tmp-1);23             if(tmp+1<=10&&!vis[tmp+1]) que.push(tmp+1); 24         }25     }26 }27 28 int main(){29     int a[]={
    0,1,2,3,4,5,6,7,8,9,10};30     searchBFS(9);31     cout<
          
           <

BFS（从中间向两边）

这种BFS也是一定要带标记数组的，所以也可以写成记忆化。

这种BFS如果不带标记数组的话，也是可以得到正确答案的，不过会重复算很多算过的东西。

例如：9 8 10 7 9 9 6 8 8 10 8 10 .........

比如说上面的9就访问了很多次，而由于队列FIFO的特性，所以虽然重复算很多次，还是会得到正确答案。

因为7、6那一支会逐渐到1的。

当然，BFS也可以直接写成线性的，这样也是不需要标记数组的。

其实还是那样，把情况的树形图画出来就很舒服了，直观方便。

二、阶乘

（1）普通求阶乘方法：略。

（2）阶乘的递归实现DFS

阶乘的递归实现

1 #include 
      
        2 using namespace std; 3 int jiechen(int n){ 4     if(n==1) return 1; 5     else{ 6         return n*jiechen(n-1); 7     } 8 } 9 int main(){10     cout<
       
        <

DFS

从尾直接算到头，不需要标记数组

（2）阶乘的栈实现

1 /* 2 伪码： 3 我们求f(n)，f(n)入栈 4 在栈不空的情况下(下面循环) 5 出栈  6 f(n)=f(n-1)*n 7 如果f(n-1)没有被求出来，直接入栈  8 */ 9 10 //对数组而言，我们操作的肯定是下标，而一定不是数组元素的值 11 #include 
      
       12 using namespace std;13 stack
       
         sta; 14 int a[15];15 16 int jiechen(int n){17     a[1]=1;18     sta.push(n);19     while(!sta.empty()){20         int tmp=sta.top();21         sta.pop();22         //如果a[tmp-1]被计算了 23         if(a[tmp-1]!=0){24             a[tmp]=a[tmp-1]*tmp;25             cout<
        
         <<" "<
         
          <