小学四年级也能看懂的DFS第二课数字探险队——这次我们有两条路可以选本课目标学会让电脑尝试不同的选择初步理解 DFS 的探索过程上一课我们认识了小勇士。他从第 1 级台阶开始一直走到第 4 级。我们学会了用dfs(x 1)让他继续向前走。但是上一课有一个小问题小勇士每次只能往前走 1 步。如果前面还有其他选择电脑又该怎么办呢今天我们就来解决这个问题一、数字王国发布了新任务数字王国里有一条神奇的道路。小勇士从数字 1 出发目标是到达数字 4。这次魔法规则发生了变化每次可以前进 1 步。也可以前进 2 步。例如现在站在数字 1。先问孩子们如果你是小勇士你会选择哪一条路答案是两条路都可以尝试我们不急着判断哪条路更好而是让电脑把不同的可能性都探索一遍。这就是今天的核心想法。二、先不写代码我们自己玩一次我们规定从数字 1 出发。每次可以加 1也可以加 2。到达数字 4就算完成任务。超过数字 4就说明走过头了。我们来看看有哪些走法。我们发现一共有 3 种走法。但是电脑怎么知道要尝试哪条路呢难道我们要把每条路线都手动写出来吗当然不用今天我们就要让电脑自己尝试。三、给电脑一个新本领两种选择都试试上一课我们学过dfs(x 1);意思是从数字x继续走到下一个数字。今天我们多给电脑一个选择dfs(x 1); dfs(x 2);第一句尝试走 1 步。第二句尝试走 2 步。注意这两句不是让小勇士同时走两条路而是让电脑先探索一种走法再回来探索另一种走法。我们先看一段完整的程序。第一版把所有走到的数字都输出#include iostream using namespace std; void dfs(int x) { if (x 4) return; cout x endl; dfs(x 1); dfs(x 2); } int main() { dfs(1); return 0; }这段程序里最重要的变化只有一处以前只有一个dfs(x 1)现在多了一个dfs(x 2)。我们先别着急运行。猜一猜电脑会输出哪些数字四、让电脑带我们探险我们一起追踪电脑的行动。首先执行dfs(1);小勇士站在数字 1。按照程序电脑先执行第一条路dfs(x 1);也就是前往数字 2。到达数字 2 后电脑仍然按照相同规则办事先走 1 步再走 2 步。当电脑走到数字 4 时它还会尝试dfs(5)和dfs(6)。这两次调用都会因为x 4而停止。之后电脑才会回到之前还没尝试的另一条路。这里有一个非常重要的发现电脑不是只走一条路。它会先把眼前的一条路探索下去再回来尝试其他选择。这就是深度优先搜索名字里“深度”的直观含义。五、勇士的岔路口——先走左边再回来走右边1、故事开始森林里的两个岔路口小勇士进入了一片神奇森林。森林里有很多岔路口每个岔路口都有两条路左边的路。右边的路。勇士决定遵守一条规则每次遇到岔路口先走左边。左边走完了再回来走右边。比如勇士来到第一个岔路口。勇士先走左边。如果左边还有岔路口就继续按照同样的规则探索。一直走到没有路可走的地方勇士才会回来继续探索之前没走过的路。这就是 DFS 最重要的想法。2、先不写代码我们用手指走一遍假设勇士要连续经过两个岔路口每次都可以选择左边或者右边。第一个岔路口有两种选择左边记作L。右边记作R。如果第一个岔路口选了左边还要面对第二个岔路口。第二个岔路口也有两种选择L或R。所以勇士可能走出四种路线孩子可以伸出两根手指分别代表两个岔路口。每根手指都能选择L或R。一共就是 2 * 2 4 种走法。但这里有一个重要问题勇士为什么会按照LL → LR → RL → RR的顺序探索而不是乱走呢因为我们给勇士规定了明确的规则先左后右而且要把一条路探索完才轮到下一条。接下来让 C 帮我们完成这件事。3、让 C 也学会走岔路先认识今天的主角void dfs(int x)我们可以把dfs(x)想象成勇士来到了第x个岔路口准备继续探险。当勇士来到第 1 个岔路口就调用dfs(1)。当他来到第 2 个岔路口就调用dfs(2)。为了方便孩子理解我们暂时规定一共只有两个岔路口。当x 3时说明两个岔路口都已经做出选择路线完成了。下面是完整程序。#include iostream using namespace std; void dfs(int x) { if (x 3) { cout 找到一种走法 endl; return; } cout 第 x 个岔路口先走左边 endl; dfs(x 1); cout 第 x 个岔路口再走右边 endl; dfs(x 1); } int main() { dfs(1); return 0; }先别急着背代码。我们重点看下面这几行cout 先走左边 endl; dfs(x 1); cout 再走右边 endl; dfs(x 1);它们就像勇士收到的探险指令先宣布走左边。进入下一层岔路口把那里的事情做完。回到这里。再宣布走右边。再进入下一层岔路口把那里的事情做完。注意第二个dfs(x 1)不会和第一个同时执行。第一个调用里面的事情全部完成后程序才会执行第二个调用。这正是孩子需要理解的关键。4、我们陪着程序一步一步走第一步勇士从第 1 个岔路口出发程序执行dfs(1)。勇士来到第 1 个岔路口先选择左边。执行第一个调用dfs(1 1)也就是dfs(2)。勇士来到了第 2 个岔路口。第二步第 2 个岔路口也先走左边勇士在第 2 个岔路口先走左边。于是程序调用dfs(3)。发现x 3说明两个岔路口的选择已经完成。程序输出“找到一种走法”然后执行return结束这一次调用。第三步回到第 2 个岔路口左边的探索已经结束了勇士回到第 2 个岔路口终于可以走之前还没探索的右边了。程序继续执行第二个dfs(3)。又找到一种走法然后结束这次调用。第四步回到第 1 个岔路口第 2 个岔路口的左右两边都探索完了。所以勇士回到第 1 个岔路口开始探索第 1 个岔路口的右边。这个过程反复进行直到每一条路线都探索完。你会发现程序虽然只有几行但它一直在做同一件事先探索左边回来再探索右边。5、让孩子看见完整的探索顺序下面这棵树就是刚才程序的探险路线。特别提醒孩子们每个叶子节点代表一种完整的走法。为什么是先LL再LR因为勇士先进入第一个岔路口的左边然后把里面的左右两种走法全部探索完才会回到第一个岔路口开始探索右边。这就是“走到底再回来”的含义。六、课堂小练习如果有三个岔路口呢现在把森林变大一点勇士需要连续做出三个选择每个岔路口仍然只有左、右两条路。你觉得一共会有多少种不同走法请选择你的答案4 种 6 种8 种回答正确每个岔路口有 2 种选择连续 3 次选择一共是 2 * 2 * 2 8 种。七、这节课需要记住三句话遇到岔路口就有不同的选择。先走左边把左边探索完再回来走右边。dfs(x 1)执行完了程序才会接着执行下面的dfs(x 1)。这一课最重要的目标是让孩子真正理解程序可以像探险的勇士一样先沿着一条路不断向前走完后再回到之前的岔路口继续探索另一条路。当孩子们能够画出LL → LR → RL → RR的探索顺序再学习迷宫、排列组合和回溯就会容易很多。八、课后小任务去数字王国继续探险请孩子们自己完成下面两个任务。任务一三个岔路口从路口 1 出发每次可以向左 或 向右一共要经过三个岔路口一共有多少种走法。任务二交换探索顺序按照下面两句的顺序交换再观察输出顺序有何变化。dfs(x 2); dfs(x 1);下一课我们就真正走进迷宫小勇士要判断上下左右绕过墙壁寻找出口。我们可以把今天学到的“尝试不同选择”变成一个真正能够解决问题的 C 程序。