《艰难历程 | 像程序员一样思考》 第八集

观看完整课程：https://ed.ted.com/lessons/the-gauntlet-think-like-a-coder-ep-8

这是我们的动画系列 《像程序员一样思考》的第八集。该故事共十集，讲述了女孩Ethic 和她的机器人伙伴 Hedge 努力拯救世界的故事。 两人从收集三件神器开始，必须通过解决一系列编程谜题来完成这一使命。

课程讲解：艾历克斯·罗森塔尔（Alex Rosenthal）
动画制作：Kozmonot 动画工作室

Ethic 和 Hedge 从高塔坠落，

翻滚着掉进了纯能量激流中，

这条来自 Bradbarrier 的激流
通向 Huxenborg。

那里整个城市的工厂
都在制造机器人，

也是记忆节点的存放地点。

三件强力神器中，记忆节点
是 Ethic 需要收集的最后一件。

度过了漫长的一天
和更漫长的夜晚后，

他们发现自己正身处
由砖块和钢铁构成的峡谷中。

正当他们快到达激流的尽头时，

一条绳索套住了他们，

他们的救世主 Lemma 已等候多时。

当 Ethic 从森林高塔取得创造节点后，

陆地上所有的无线装置
都恢复了正常运作。

反抗军领袖 Adila
立即开始联系盟友，

首推在 Huxenborg 工作的
杰出科学家 Lemma，

由她从内部协助打败机器人。

不料，无线电波也惊动了守卫。

守卫因此采取了防御措施，

来保护位于城市中心
关键区域的最后神器。

要到达那里，只有一种办法：
战胜分叉路径的严酷挑战。

这是一系列致命的发光传送带，
在 Huxenborg 地下蜿蜒而行。

从当前位置开始，

每条路延伸一段后就分为两条；

每个分支不断重复此过程，

从而产生了成千上万的分支。

通往神器的路只有一条；
其他的路径只会通向毁灭。

幸运的是，创造节点
赋予了 Hedge 一种神秘力量：

能生成比自身略小的两个复制体。

每个复制体只能做两件事：

通过无线电向父级传回信息，
并复制两个更小的自己 ... ...

这些复制体与其子级复制体
也会做同样的这两件事，

不断复制直至满足数量。

一支巡逻队正在接近他们，
Ethic 的时间很有限。

为了找到安全路径，
她该给 Hedge 下达什么指令？

[ 可暂停视频，自行解题 ]

[ 答案揭晓：3 ]

[ 答案揭晓：2 ]

[ 答案揭晓：1 ]

程序员的装备库中
有一件强大的工具叫递归，

它是一组不断进行自引用的指令，

就像用一个词本身来定义这个词，

除了让人觉得怪异之外，
这种方式本身非常有效。

递归涉及重复，但与循环不同。

循环在执行一次操作后，
会重复执行这个过程，

而递归在开始执行一次操作后 ，
会在完成之前再次执行操作，

完成前再次执行同样动作，
以此类推下去 ... ...

一直重复此操作，
直到满足某种条件，

然后将信息一层层传递回去，

直到传回起点，最后结束循环。

递归非常适合解决
涉及自相似性的问题，

其中每个部分都与整体高度相似。

例如，一个致命的防御系统，

设计用来终结任何大胆的闯入者。

[ 可暂停视频，自行解题 ]

[ 答案揭晓：3 ]

[ 答案揭晓：2 ]

[ 答案揭晓：1 ]

Ethic 的难题表面看起来很难，

但使用递归就特别简单了。

为了找到这个方法，
先来看看谜题的最简版本：

如果整个迷宫只有两条路呢？

如果 Hedge 复制两个自己，
走入错路的复制体将被毁灭。

另一个复制体会抵达神器，

并用无线电发回其路径信息，
不需要考虑其他路径，

那就是 Hedge 接收到的答案。

这就是 “递归的基本情况”。

现在，假设迷宫由起点分为两支，

在每个分支的节点
Hedge 进行自我复制 ——

我们称为 分支 1 和 分支 2——

它们继续进行复制，
得到 叶片 1 至叶片 4，

三条分支会被摧毁。

到达神器的那条路径
将传回正确答案，

但只回传给父级。

如果分支 1 或 2 在节点等待

并从无线电收到回传信息，

即从其所在位置
通往神器的正确道路。

要从分支的角度
告诉 Hedge 正确答案，

分支会报告自己走过的路径，

以及刚从无线电收到的路径信息。

不管迷宫分支多少次，
同样的过程都会奏效，

复制体在无线电上接收到的答案

必然是从它的位置到控制室的路径，

然后，如果加上它走的分支，

也就能告诉父级
如何从它的位置到控制室。

在这次名为“探路者”的行动中，

我们总结出 Hedge 的每个复制体
需要遵循的指令如下：

1. 如果到达神器地点，

通过无线电告知父级
选左边或右边的路径。

2. 到达节点后，离开传送带，

并向左右两条路发送复制体。

让它们各自运行“探路者”，

这就是递归的过程，

在最终指令触发前，这个过程
可能会发生很多次。最终指令是：

3. 如果无线接收到任何信息，
都应当传递回父级——

不管你走左边还是右边的路
到达你所在位置，

然后重复刚接收到的一切信息。

”探路者“是程序员调用函数、

子程序或过程的一个例子。

不管用什么术语来形容，
其本质都是一样的——

这只是一组带有标签的指令，
可以方便地重复使用——

甚至可以被其自身调用。

在我们的案例中，
这一方法将非常有效——

仅仅使用三条指令
就能映射出整个路径网络。

这就是接下来所发生的事情：

在巡逻队正要经过拐角时，
Ethic 和 Lemma 及时伪装了自己。

她们试图迷惑机器人，
以便为 Hedge 争取时间，

终于，Hedge 的无线电响起，
收到了正确路径信息。

他们三个跳上了传送带，

逃离了紧追不舍的一队机械守卫。