模拟-树的思维

点击打开在线编译器,边学边练

1. 模拟法简介

        在前面的文章已经提到过模拟这个思维,模拟的思维无处不在,就树形的DFS算法而言,我们更多的情况并非建立一棵树,这对我们书写和易用性而言太差了,我们通常会适用多个数组进行模拟,树也是可以利用数组进行模拟的。

        如下图:

11.png

        上面一排表示数组下标,下面一排表示数据,其实通过这样的简单方式,也能够设计出一个模拟的二叉树,其具体的表示为:

12.png

        仔细对比以下数据,可以发现数组中的数据存储的就是与之相联系的数组下标,通过这样的方式可以方便的建立一颗简单的模拟法的树,同时再创建一个数组用来存储具体的值,两个数组保持一一对应的关系就可以简单完成,这就是通过模拟算法来模拟树结构的核心思路,这个思路进行扩展其实会发现与建立树,甚至是后文才会学的图并没有什么核心的区别。

2. 例题——全排列

        从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

        对于常规的思路而言,我们需要对0~9一共十个数字进行全排列,就需要列出10层for循环,每一层分别表示不同的数字,同时还需要利用if语句进行判重,因此写出来的代码就显得非常的累赘,其格式大致如下:

for()
    for()
        for()
            …………    省略N层for循环
                for()
                      if()

        不要小看这样的代码,对于一个新手而言,能够有这样大胆的思维,其实是很难得的,不过就后面而言,这样的思维显得莫过于臃肿了,而且极其不相似一种成熟的代码,实际上,利用DFS算法,我们将10个数通过数组进行拆分,需要多少就调用多少,同时再建立一个判断的数组,这样也不需要我们写出累赘的if语句了,利用函数的递归实现多层的for功能。

        本例题的代码为:

#include<iostream>
#include<cmath>
using namespace std;
 
int p[10]= {0};
bool vis[10]= {0};
int n;
void dfs(int x) {
    if (x==n+1) {
        for(int i=1; i<=n; i++)
            cout<<p[i]<<" ";
        cout<<endl;
        return ;
    }
 
    for (int i=1; i<=n; i++) {
        if (vis[i]==false  ) {
            p[x] = i;
            vis[i] = true;
            dfs(x+1);
            vis[i] = false;
        }
    }
}
 
int main() {
    while (cin>>n) {
        dfs(1);
    }
    return 0;
}

PS:这样的全排列C++的STL库已经封装好了,称之为next_permuitation(n,n+a);

3. 例题——程序员爬楼梯

爬楼梯问题

        爬楼梯的问题更像我们常规的算法问题,以是否能够走到第4格楼梯为例,我们初始的状态是走0个楼梯,建立二叉树,根结点设置为0,随后对于0这个状态而言,有两种形态,走一步和走三步,这分别对应二叉树的左孩子和右孩子,在走完之后,我们成功的引出了两种状态,共走1步和共走3步 ,我们再分别在这个基础上重新建立左孩子和右孩子引出两个状态,便可以逐渐构建出这颗二叉树,最终,通过数最终的状态我们可以知道一共有3个答案满足条件。

13.png

套用DFS的模板可以轻易求解,本例题代码为:

#include<iostream>
 
using namespace std;
 
typedef long long ll;
ll ans,n;
 
void dfs(ll k) {
    if(k==n) {
        ans++;
        return;
    } else if(k>n) {
        return;
    }
    dfs(k+1);
    dfs(k+3);
}
 
int main() {
    while(cin>>n) {
        ans=0;
        dfs(0);
        cout<<ans<<endl;
    }
    return 0;
}


上一课:DFS(深度优先搜索) 下一课:树与森林
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记