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

1、线性查找

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

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

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

 //递归一定要写成记忆化递归

 #include <bits/stdc++.h>

 using namespace std;

 bool vis[];

 int count1=;

 void search(int n){

     count1++;

     if(n>||n<||vis[n]){

         //cout<<"back"<<endl;

     }

     else if(n==){

         vis[n]=true;

         cout<<"find"<<endl;

     }

     else {

         vis[n]=true;

         search(n-);

         search(n+);

     }

 }

 int main(){

     int a[]={,,,,,,,,,,};

     search();

     cout<<count1<<endl;

     return ;

 }

递归(从中间到两边)

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

其中一个死循环：

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

而这样的死循环太多了。

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

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

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

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

 #include <bits/stdc++.h>

 using namespace std;

 int count1=;

 void search(int n){

     count1++;

     if(n>||n<){

     }

     else if(n==){

         cout<<"find"<<endl;

     }

     else {

         search(n-);

     }

 }

 int main(){

     int a[]={,,,,,,,,,,};

     search();

     cout<<count1<<endl;

     return ;

 }

递归(从后面向前面)

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

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

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

 #include <bits/stdc++.h>

 using namespace std;

 bool vis[];

 int count1=;

 queue<int> que;

 void searchBFS(int n){

     que.push(n);

     while(!que.empty()){

         count1++;

         cout<<"count1:"<<count1<<endl;

         int tmp=que.front();

         que.pop();

         vis[tmp]=true;

         cout<<"tmp:"<<tmp<<endl;

         if(tmp==) {

             cout<<"find"<<endl;

             return ;

         }

         else{

             if(tmp->=&&!vis[tmp-]) que.push(tmp-);

             if(tmp+<=&&!vis[tmp+]) que.push(tmp+);

         }

     }

 }

 int main(){

     int a[]={,,,,,,,,,,};

     searchBFS();

     cout<<count1<<endl;

     return ;

 }

BFS（从中间向两边）

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

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

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

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

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

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

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

二、阶乘

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

（2）阶乘的递归实现DFS

阶乘的递归实现

 #include <bits/stdc++.h>

 using namespace std;

 int jiechen(int n){

     if(n==) return ;

     else{

         return n*jiechen(n-);

     }

 }

 int main(){

     cout<<jiechen()<<endl;

     return ;

 }

DFS

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

（2）阶乘的栈实现

 /*

 伪码：

 我们求f(n)，f(n)入栈

 在栈不空的情况下(下面循环)

 出栈

 f(n)=f(n-1)*n

 如果f(n-1)没有被求出来，直接入栈

 */

 //对数组而言，我们操作的肯定是下标，而一定不是数组元素的值

 #include <bits/stdc++.h>

 using namespace std;

 stack<int> sta;

 int a[];

 int jiechen(int n){

     a[]=;

     sta.push(n);

     while(!sta.empty()){

         int tmp=sta.top();

         sta.pop();

         //如果a[tmp-1]被计算了

         if(a[tmp-]!=){

             a[tmp]=a[tmp-]*tmp;

             cout<<tmp<<" "<<a[tmp]<<endl;

         }

         else{

             sta.push(tmp);

             sta.push(tmp-);

         }

     }

     return a[];

 }

 int main(){

     cout<<jiechen()<<endl;

     return ;

 }

阶乘的栈实现

对数组而言，我们操作（存储进栈或者队列或者其它操作）的肯定是下标，而一定不是数组元素的值

其实栈实现和递归实现是一样的，因为递归在计算机内部就是用栈实现的。

巴特西

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

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

1、线性查找

二、阶乘

最新文章

热门文章