Chinese, Simplified subtitles

← 主显节塔 | 像程序员一样思考 - 第 7 集

观看完整课程: https://ed.ted.com/lessons/the-tower-of-epiphany-think-like-a-coder-ep-7

本视频是《像程序员一样思考》系列动画的第 7 集。全部 10 集都跟随女孩 Ethic 和她的机器人伙伴 Hedge 的脚步,记录着他们尝试拯救世界的行为。他们需要收集三样物品,同时必须面对一系列的编程谜题。

授课:Alex Rosenthal;导演:Kozmonot Animation Studio。

Get Embed Code
21 Languages

Showing Revision 20 created 05/11/2020 by Yolanda Zhang.

  1. Ethic 和 Hedge 站在巨大塔楼的底层。
  2. 能量屏障把他们与第二个目标隔开了:
  3. 创造之结。
  4. 为了拿到它,
    Ethic 要用三束能量流爬上塔楼。
  5. 一旦她开始前进,
    计时器就会启动 60 秒倒计时。
  6. 在房间后部,
    有个由隐形柱子组成的容器,
  7. 可以储存能量。
  8. 一分钟后,能量会从上方倾泻而下,
  9. 一次填满一个单位,
  10. 力场确保它不会向前或向后流动。
  11. 在 60 秒的冷却时间里,
  12. Ethic 和 Hedge 必须确定
    有多少能量会流下来。
  13. 对于这三个挑战,
  14. 他们必须使能量正好填满底座。
  15. 如果他们做对了,
    能量会助他们更进一步。
  16. 但如果他们弄错了,
    能量就会泄漏出来,
  17. 落向他们。
  18. 墙上的图是一个例子。
  19. 这个结构能容纳 2 个单位的能量。
  20. 这个可以容纳 4 个单位——
    左边 3 个,右边 1 个。
  21. 这个结构也可以容纳
    4 个单位的能量,
  22. 因为如果右边有能量 ,就会泄漏。
  23. 能量落下的方法
  24. 让它只会在空间容纳量不够时泄漏。
  25. Hedge 每次能让一个能量柱现形
    并数出它的高度,
  26. 但他不能一次看全整个结构。
  27. Ethic 要怎样让 Hedge 计算出
  28. 这个容器可以容纳多少能量呢?
  29. 现在暂停来自己试试。
  30. 有一种方法来思考这个问题:
  31. 对于一个空的单元格,
    当且仅当它左边有墙,
  32. 右边也有墙时,
  33. 才可以容纳能量。
  34. 但 Hedge 一个个检查
    这些单元格会耗费很多时间。
  35. 如果他一次考虑一整个纵列呢?
  36. 比如这个结构可以容纳多少能量?
  37. 暂停来自己试试。
  38. 我们可以通过这个例子
    来分析一下问题。
  39. 这里有 5 纵列单元格。
  40. 最左边的不能容纳任何能量,
    因为没有比它更高的了。
  41. 第二列能容纳3个单元格的能量,
  42. 这两个四格高的纵列
    可以把能量夹在中间。
  43. 我们得出 3 格的结论,因为能量
    最终会等于最高纵列——4,
  44. 再减去这列的高度 ——
    就是 4 减 1。
  45. 第三列同理——左边 4 格,
    右边 4 格,这列高 3 格,
  46. 所以 4 减 3 等于 1 个单位。
  47. 第四、第五列右边没有更高的,
  48. 所以它们无法容纳任何能量。
  49. 我们可以把这个方法
    转变成一种算法。
  50. 每次选择一个纵列作为参考点,
  51. Hedge 由此向左一点点检查,
    找到最高的纵列,
  52. 再检查右边并找出最高的纵列,
  53. 两个高度中较小的
    就是最终能量可以填满的高度。
  54. 如果这个结果高过某列原高度,
  55. 那么减去这列的原有高度,
  56. 就能得出这个纵列的容纳量。
  57. 如果低于某列的原有高度,
  58. 能量就会泄漏。
  59. Hedge 可以对整个底座
    依次这样操作,
  60. 从左到右,一次一列。
  61. 对于每一纵列都重复同样的操作——
    向左找到最高的,
  62. 右边也是,
    取两个高度中较小的一个,
  63. 减去原纵列原有的高度,
  64. 如果得到正数就算进总容量里。
  65. 这一流程的运行次数和纵列数相等。
  66. 这样的确可行,但如果底座很大,
    这样做会耗费很多时间。
  67. 每一步,Hedge 都要反复地左看右看。
  68. 如果有 N 个纵列,
    他就需要把每个纵列都看 N 遍。
  69. 有没有更快的方法呢?
  70. 有个节省时间的方法:
  71. 首先,Hedge 从左边开始,
  72. 并连续记录最高纵列的高度。
  73. 这样就是 2,然后还是 2,
    因为第一个更高,
  74. 然后是 4,4,4。
  75. 然后他可以找到最高纵列的右端,
  76. 只要同样从右到左再做一遍:
    1,3,4,4,4。
  77. 最终,他会记下这样一个表格。
  78. 现在 Hedge 可以再扫描一次,
  79. 按照之前的等式计算每个纵列
    可以容纳多少能量:
  80. 在存储的左右最高值中选较小的,
  81. 再减去当前纵列的高度。
  82. 与把 N 个纵列每个看 N 遍相比,
    他只需把每个纵列看三遍——
  83. 这就是我们所说的线性时间。
  84. 还有很多更优解决方法,
  85. 但这个已经够好了。
  86. Ethic 和 Hedge 配合默契。
  87. 他们轻而易举地通过了
    第一个瀑布,塔楼地板上升了。
  88. 第二个难一些。
  89. 第三个容器非常大,
    每列有数十个单元格。
  90. 计时器显示出 0,
    但 Ethic 的动作很快。
  91. 她在最后时刻找到了正确位置,
  92. 能量让他们上升至创造之结。
  93. 和第一次一样,它显现出了幻象:
    多年前的记忆。
  94. 世界机器改变了一切,
  95. Ethic 作为首席机器人工程师,
  96. 对她目击到的现象感到不安。
  97. 当 Brad 障碍升起并围住人群时,
  98. 她知道大事不妙了。
  99. 于是她造出了三个物品,
  100. 它们拥有修复人们的力量、
    创造力以及记忆的能力,
  101. 并把它们偷运到了三个社区里。
  102. 在她告诉人们如何使用之前,
  103. 政府发现了她的成果,
    并派出机器人
  104. 抓捕她以及其他程序员。
  105. Ethic 用世界机器创造的
    最后一件物品是个机器人,
  106. 它可以把古老的装置
  107. 围在大型迷宫中,
    使它远离愚昧的力量。
  108. 她给这个物品起名叫 Hedge。
  109. 在没有任何警告的情况下,
    能量电梯开始闪烁,然后消散了。