< Return to Video

峡谷 | 像程序员一样思考 第六集

  • 0:09 - 0:11
    [ 像程序员一样思考 ]
  • 0:13 - 0:18
    [ 地点:198 森林 ]
  • 0:18 - 0:20
    [ 第六集 峡谷 ]
  • 0:22 - 0:27
    艾斯克、海吉和奥克塔维亚
    站在无底峡谷的边缘。
  • 0:27 - 0:29
    峡谷是他们与塔之间的唯一阻碍,
  • 0:29 - 0:33
    塔里藏有三个强大神器中的第二个。
  • 0:33 - 0:35
    他们在警卫回来前
  • 0:35 - 0:38
    只有一小段时间可以跨越这个峡谷。
  • 0:38 - 0:43
    海吉的燃料箱空了,
    无法带艾斯克飞越过去,
  • 0:43 - 0:46
    所以,唯一选择是建一座桥。
  • 0:46 - 0:51
    幸运的是,附近漂浮的石头堆
    可以用来搭一座桥,
  • 0:51 - 0:53
    石头堆是奥克塔维亚
    自己发明的——
  • 0:53 - 0:55
    叫作“飘浮块”。
  • 0:55 - 0:57
    他们可以用一股能量
    激活一堆飘浮块,
  • 0:57 - 1:02
    这样在这些飘浮块自动组装时,
    艾斯克就能跨越峡谷。
  • 1:02 - 1:06
    但现在存在一个问题。
  • 1:06 - 1:10
    这些飘浮块只有在组合成
    完美的回文结构时才能保持稳定。
  • 1:10 - 1:13
    也就是说,它们得被组合成
  • 1:13 - 1:17
    正序看和倒序看都一致的结构才行。
  • 1:17 - 1:19
    飘浮块最初是随机排列的,
  • 1:19 - 1:21
    但如果可行,
  • 1:21 - 1:24
    它们随后会自动拼装成回文结构。
  • 1:24 - 1:27
    但如果它们无法被拼成回文结构,
  • 1:27 - 1:28
    桥就会坍塌掉,
  • 1:28 - 1:32
    走在上面的人就会坠入深谷。
  • 1:32 - 1:33
    让我们来看一个例子。
  • 1:33 - 1:36
    这堆飘浮块能被组成稳定的结构。
  • 1:36 - 1:39
    首先,A 型方块
    能被排列在左右两侧。
  • 1:39 - 1:40
    接着是 B 型方块。
  • 1:40 - 1:44
    最后,C 型方块正好
    能被放在两块 B 之间。
  • 1:44 - 1:47
    但假设多一块 A 型方块的话。
  • 1:47 - 1:50
    首先两块 A 排列好,
    然后两块 B 也排列好,
  • 1:50 - 1:54
    但剩下的 A 块
    和 C 块就没地方放了,
  • 1:54 - 1:56
    因此整座桥都会塌掉。
  • 1:56 - 2:01
    力量节点晶石只够海吉
    激活一堆飘浮块,
  • 2:01 - 2:04
    艾斯克要给海吉什么指令,
  • 2:04 - 2:08
    才能让它有效地找到并激活
    一堆稳固且为回文结构的飘浮块呢?
  • 2:08 - 2:18
    [ 可暂停播放自行解题 ]
  • 2:18 - 2:24
    回文排列的例子如:ANNA、RACECAR、
    以及 MADAM IM ADAM。
  • 2:24 - 2:27
    通过数一个字母
    在回文中出现的次数,
  • 2:27 - 2:30
    你会发现一个有用的模式。
  • 2:30 - 2:35
    [ 可暂停播放自行解题 ]
  • 2:35 - 2:38
    我们先来看一个简单的方案。
  • 2:38 - 2:40
    简易方案是一种
  • 2:40 - 2:43
    简单的、未被优化的粗暴方法,
  • 2:43 - 2:45
    但是它可以达成目标。
  • 2:45 - 2:48
    简单方案是分析问题的有用方法,
  • 2:48 - 2:52
    是更优方案的铺路石。
  • 2:52 - 2:54
    在这种情况下,一个简单方案是:
  • 2:54 - 2:57
    尝试这堆飘浮块的所有可能组合,
  • 2:57 - 3:02
    并通过正向,反向阅读
    来确定其是否为回文结构。
  • 3:02 - 3:03
    但这种方法有个缺陷,
  • 3:03 - 3:06
    它需要大量的时间。
  • 3:06 - 3:09
    如果海吉每秒
    能判断一种组合可不可行,
  • 3:09 - 3:14
    那么只有 10 块的飘浮块堆,
    需要 42 天才能算完。
  • 3:14 - 3:17
    这是因为总时间
  • 3:17 - 3:20
    是总块数的阶乘。
  • 3:20 - 3:23
    10 个飘浮块就有
    超过 300 万种组合方式。
  • 3:23 - 3:28
    这个简单的解决方案表明,
    我们需要一种更快的方法
  • 3:28 - 3:31
    来判断一堆飘浮块
    是否可以形成回文。
  • 3:31 - 3:36
    首先,很明显的是,
    一堆各不相同的飘浮块
  • 3:36 - 3:37
    永远不可能形成回文结构。
  • 3:37 - 3:38
    为什么?
  • 3:38 - 3:40
    因为如果没有重复,
  • 3:40 - 3:43
    第一块和最后一块就不可能相同。
  • 3:43 - 3:48
    那么什么时候一个给定的
    序列可以形成回文呢?
  • 3:48 - 3:53
    一种方法是分析
    一些现有的回文。
  • 3:53 - 3:56
    ANNA 有两个 A 和两个 N,
  • 3:56 - 4:01
    RACECAR 有两个 R、
    两个 A、两个 C 和一个 E,
  • 4:01 - 4:08
    MADAM IM ADAM 中,
    有四个 M、四个 A、两个 D 和 一个 I。
  • 4:08 - 4:11
    模式是,大多数字母
  • 4:11 - 4:13
    会出现偶数次,
  • 4:13 - 4:16
    最多只有一个字母
    可以只出现一次。
  • 4:16 - 4:17
    这就完了吗?
  • 4:17 - 4:20
    如果 RACECAR
    有3个 E 而不是1个呢?
  • 4:20 - 4:24
    我们可以把新的两个 E 钉在两端,
    仍能得到一个回文,
  • 4:24 - 4:26
    所以字母出现 3 次是可以的。
  • 4:26 - 4:32
    但如果有 3 个 E 和 3 个 C ,
    最后一个 C 就没有地方放了。
  • 4:32 - 4:35
    让我们来概括一下思路,
  • 4:35 - 4:39
    最多只有一个字母能出现奇数次,
  • 4:39 - 4:42
    但其他字母必须出现偶数次。
  • 4:42 - 4:44
    海吉可以数每个字母
    在飘浮堆中出现的次数,
  • 4:44 - 4:46
    把这些信息存放到
    字典这种数据结构中,
  • 4:46 - 4:49
    这是一种储存信息的简洁方式。
  • 4:49 - 4:53
    可以通过一个循环遍历这个字典,
    数有几个字母出现了奇数次。
  • 4:53 - 4:56
    如果有少于两个字母出现了奇数次,
  • 4:56 - 4:59
    那么这堆飘浮块
    就能被组成回文结构。
  • 4:59 - 5:03
    这种方法比之前的
    那个简单解决方案要快得多。
  • 5:03 - 5:06
    它只需线性时间,
    而不是阶乘时间。
  • 5:06 - 5:08
    线性时间指的是
  • 5:08 - 5:10
    程序运行时间与方块数量成正比。
  • 5:10 - 5:14
    现在,请你为海吉编写一个循环,
    来分别处理这些飘浮块堆,
  • 5:14 - 5:19
    当它找到可行的方案时,
    暂停程序,这样就成功了。
  • 5:19 - 5:20
    接下来会发生的是:
  • 5:20 - 5:22
    虽然海吉的速度很快,
  • 5:22 - 5:24
    但有很多的飘浮块堆,
    要花很长的时间,
  • 5:24 - 5:25
    很长很长的时间。
  • 6:18 - 6:20
    艾斯克和海吉现在安全了,
  • 6:20 - 6:22
    但奥克塔维亚就没那么幸运了。
Title:
峡谷 | 像程序员一样思考 第六集
Speaker:
亚历克斯 · 罗森塔尔
Description:

查看完整课程:https://ed.ted.com/lessons/the-chasm-think-like-a-coder-ep-6

这是我们的动画系列《像一个程序员一样思考》的第六集。这部十集的动画系列讲述的是一个名叫艾斯克的女孩和她的机器人伙伴海吉试图拯救世界的故事。两人开始了收集三大神器的任务,在路上他们必须解决一系列编程难题。

课程讲解:亚历克斯 · 罗森塔尔(Alex Rosenthal),动画执导:Kozmonot 动画工作室。

more » « less
Video Language:
English
Team:
closed TED
Project:
TED-Ed
Duration:
06:24

Chinese, Simplified subtitles

Revisions