1. 模拟法简介文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
在前面的文章已经提到过模拟这个思维，模拟的思维无处不在，就树形的DFS算法而言，我们更多的情况并非建立一棵树，这对我们书写和易用性而言太差了，我们通常会适用多个数组进行模拟，树也是可以利用数组进行模拟的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
如下图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
上面一排表示数组下标，下面一排表示数据，其实通过这样的简单方式，也能够设计出一个模拟的二叉树，其具体的表示为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
仔细对比以下数据，可以发现数组中的数据存储的就是与之相联系的数组下标，通过这样的方式可以方便的建立一颗简单的模拟法的树，同时再创建一个数组用来存储具体的值，两个数组保持一一对应的关系就可以简单完成，这就是通过模拟算法来模拟树结构的核心思路，这个思路进行扩展其实会发现与建立树，甚至是后文才会学的图并没有什么核心的区别。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
2. 例题——全排列文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
对于常规的思路而言，我们需要对0~9一共十个数字进行全排列，就需要列出10层for循环，每一层分别表示不同的数字，同时还需要利用if语句进行判重，因此写出来的代码就显得非常的累赘，其格式大致如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
for() for() for() ………… 省略N层for循环 for() if() |
不要小看这样的代码，对于一个新手而言，能够有这样大胆的思维，其实是很难得的，不过就后面而言，这样的思维显得莫过于臃肿了，而且极其不相似一种成熟的代码，实际上，利用DFS算法，我们将10个数通过数组进行拆分，需要多少就调用多少，同时再建立一个判断的数组，这样也不需要我们写出累赘的if语句了，利用函数的递归实现多层的for功能。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
本例题的代码为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
#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);文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
3. 例题——程序员爬楼梯文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
爬楼梯的问题更像我们常规的算法问题，以是否能够走到第4格楼梯为例，我们初始的状态是走0个楼梯，建立二叉树，根结点设置为0，随后对于0这个状态而言，有两种形态，走一步和走三步，这分别对应二叉树的左孩子和右孩子，在走完之后，我们成功的引出了两种状态，共走1步和共走3步 ，我们再分别在这个基础上重新建立左孩子和右孩子引出两个状态，便可以逐渐构建出这颗二叉树，最终，通过数最终的状态我们可以知道一共有3个答案满足条件。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
套用DFS的模板可以轻易求解，本例题代码为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25180.html
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #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;} |