WEBVTT

00:00:01.250 --> 00:00:04.369
[TED-Ed 原創系列]

00:00:06.673 --> 00:00:09.569
《時代女神 x 程式邏輯革命》

00:00:13.339 --> 00:00:17.923
[地點：一九八樹林]

00:00:18.190 --> 00:00:19.921
[第七集：覺醒]

NOTE Paragraph

00:00:31.586 --> 00:00:34.423
踏進巨塔的底層

00:00:34.423 --> 00:00:38.752
彥霖和凌杰要先越過能量布陣

00:00:38.752 --> 00:00:43.945
才能觸及第二枚瑰寶：創造之泉

00:00:52.667 --> 00:00:57.409
彥霖要藉三道能量流登上塔頂

00:00:57.409 --> 00:01:03.359
足下一步，啟動計時器倒數 60 秒

NOTE Paragraph

00:01:07.359 --> 00:01:09.719
在房間的盡頭，有一個能量池

00:01:09.719 --> 00:01:11.839
一座座隱形能量塔一字排開

00:01:11.839 --> 00:01:14.665
中間的空格可以蓄積能量

00:01:14.665 --> 00:01:18.865
一分鐘後，能量會如急流般瀉下

00:01:18.865 --> 00:01:21.015
每次填滿一個空格

00:01:21.015 --> 00:01:25.355
力場則在前後防止流溢

NOTE Paragraph

00:01:25.355 --> 00:01:27.825
在風平浪靜的 60 秒間

00:01:27.825 --> 00:01:32.723
彥霖、凌杰要決定降下多少格能量

00:01:32.723 --> 00:01:35.757
在三關挑戰中，每關都要調好份量

00:01:35.757 --> 00:01:38.237
能量池滿而不溢才算圓滿

00:01:38.237 --> 00:01:41.938
能量階梯就會將他們推上下一關

00:01:41.938 --> 00:01:46.208
計較份量若有閃失，能量階梯便破解

00:01:46.208 --> 00:01:48.208
一腳踩空，就是無情的迫降

NOTE Paragraph

00:01:48.208 --> 00:01:51.348
牆上的示意圖，枚舉幾個例子

00:01:51.348 --> 00:01:55.618
這範例蓄積恰恰兩格能量

00:01:55.618 --> 00:01:58.176
範例二則蓄積四格：

00:01:58.176 --> 00:02:00.735
第二欄 3 格、第三欄 1 格

00:02:00.735 --> 00:02:03.275
範例三也是蓄積四格：

00:02:03.275 --> 00:02:06.688
左右兩側框不住，能量會外溢

00:02:06.688 --> 00:02:09.909
能量雨降下後會盡量往空子鑽進去

00:02:09.909 --> 00:02:13.538
當所有空格填滿才會滿溢

00:02:13.538 --> 00:02:18.865
凌杰可逐次顯現一座能量塔再數高度

00:02:18.865 --> 00:02:22.725
但不能一窺整個能量池的全豹

00:02:22.725 --> 00:02:25.530
彥霖要為凌杰設計一個怎樣的程式

00:02:25.530 --> 00:02:29.340
來找出能量池框得下多少格能量？

NOTE Paragraph

00:02:29.340 --> 00:02:33.805
若要自己動腦筋，就按一下暫停

NOTE Paragraph

00:02:38.695 --> 00:02:41.635
這道題可以這樣入手：

00:02:41.635 --> 00:02:44.550
但凡一個空格，要框得住能量

00:02:44.550 --> 00:02:48.790
最左邊，必須總得有一堵牆框住

00:02:48.790 --> 00:02:51.517
最右邊，也得有一堵牆框住

00:02:51.517 --> 00:02:56.322
但凌杰每一格都左顧右盼會很費時

00:02:56.322 --> 00:03:01.185
假如凌杰逐欄來看每一座能量塔呢

00:03:01.185 --> 00:03:05.025
比如說，這裡框得住多少格能量？

NOTE Paragraph

00:03:05.025 --> 00:03:10.389
[若要自己動腦筋，就按一下暫停]

NOTE Paragraph

00:03:10.389 --> 00:03:13.759
回來剛才的例子，去分析這道題

00:03:13.759 --> 00:03:15.914
能量格疊成塔，計有 5 欄

00:03:15.914 --> 00:03:20.484
最左一欄已到頂，框不下任何能量

00:03:20.484 --> 00:03:23.118
第二欄，上面可再加 3 格

00:03:23.118 --> 00:03:27.244
左右這兩座四格塔，能量框得住

00:03:27.244 --> 00:03:32.186
算法是將能量塔
最高平整的高度——4

00:03:32.186 --> 00:03:34.336
減去能量塔本身的高度——1

00:03:34.336 --> 00:03:36.346
即 4 減 1 得 3

00:03:36.346 --> 00:03:41.808
第三欄同理：左 4、右 4、高 3 格

00:03:41.808 --> 00:03:46.537
故可蓄積 4 減 3 格，即 1 格

00:03:46.537 --> 00:03:50.957
第四、五欄靠右都沒有更高的塔框住

00:03:50.957 --> 00:03:53.427
所以，這兩欄都不能蓄積任何能量

NOTE Paragraph

00:03:53.427 --> 00:03:57.245
這個概念可用一個演算法實踐：

00:03:57.245 --> 00:04:01.025
凌杰每次以一欄塔作參照點

00:04:01.025 --> 00:04:05.436
靠左，逐欄找最高一座塔的高度

00:04:05.436 --> 00:04:08.156
又挨右，找最高一座塔的高度

00:04:08.156 --> 00:04:12.833
兩者以較低者為蓄積後的平整高度

00:04:12.833 --> 00:04:15.963
結果若高於此欄本身的高度

00:04:15.963 --> 00:04:18.537
就減去原來的塔高

00:04:18.537 --> 00:04:23.454
得出這座塔會蓄積到多少格能量

00:04:23.454 --> 00:04:27.194
相反，結果若少於或等於原來塔高

00:04:27.194 --> 00:04:29.397
能量就不會留住，往左右流走

NOTE Paragraph

00:04:29.397 --> 00:04:32.917
凌杰可用一個迴圈橫越整個能量池

00:04:32.917 --> 00:04:38.662
從最左一欄塔開始，每次一欄向右移

00:04:38.662 --> 00:04:41.166
逐欄塔重複相同的幾個步驟：

00:04:41.166 --> 00:04:43.671
先向左找最高一欄

00:04:43.671 --> 00:04:45.254
再向右找最高一欄

00:04:45.254 --> 00:04:49.318
取二者較低者，減去原來欄高

00:04:49.318 --> 00:04:53.178
若是正數，則加進蓄積格數的總計

00:04:53.178 --> 00:04:56.848
有多少欄，迴圈就重複多少次

NOTE Paragraph

00:04:56.848 --> 00:04:58.823
這個方法雖然行得通

00:04:58.823 --> 00:05:00.798
但能量池大的話就很費時

00:05:00.798 --> 00:05:05.328
每個步驟凌杰都要向左、向右查看

00:05:05.328 --> 00:05:10.280
若有 N 座塔，就要看 N 次

00:05:10.280 --> 00:05:12.260
有更快的方法嗎？

NOTE Paragraph

00:05:12.260 --> 00:05:15.608
有一個省時妙計：一開始可先取巧

00:05:15.608 --> 00:05:17.993
凌杰從最左開始一邊數一邊做小抄

00:05:17.993 --> 00:05:21.338
以流水帳方式記下當前最高的欄高

00:05:21.338 --> 00:05:23.218
範例中，首欄是 2

00:05:23.218 --> 00:05:25.098
然後也是 2，因為第一欄較高

00:05:25.098 --> 00:05:27.848
接著是 4、4、4

00:05:27.848 --> 00:05:30.628
之後就輪到靠右的最高欄高

00:05:30.628 --> 00:05:33.755
做法是從右往左重複一遍：

00:05:33.755 --> 00:05:36.882
1、3、4、4、4

00:05:36.882 --> 00:05:40.722
最後凌杰記憶中就有一個這樣的表

00:05:40.722 --> 00:05:43.341
現在凌杰只消多一重功夫

00:05:43.341 --> 00:05:45.961
用先前同一條等式

00:05:45.961 --> 00:05:50.001
去計算每欄塔上可框住多少格能量：

00:05:50.001 --> 00:05:53.638
小抄中儲存的左值、右值取較低者

00:05:53.638 --> 00:05:56.708
減去該能量塔原來的高度

NOTE Paragraph

00:05:56.708 --> 00:06:02.293
N 座塔本來要看 N 次，現在只消 3 次

00:06:02.293 --> 00:06:04.573
即是所謂的線性時間

00:06:04.573 --> 00:06:07.814
這個解題方案還可以進一步優化

00:06:07.814 --> 00:06:10.564
但已可解燃眉之急了

NOTE Paragraph

00:06:10.564 --> 00:06:12.614
彥霖、凌杰雙劍合璧

00:06:14.992 --> 00:06:18.836
第一關如沐春風，翻手之間就竄升

00:06:21.573 --> 00:06:23.783
第二關稍有難度

00:06:33.051 --> 00:06:36.911
第三關規模龐大，有數十座能量塔

00:06:36.911 --> 00:06:41.344
計時器快歸零，幸好編寫程式夠快

00:06:41.344 --> 00:06:44.308
彥霖及時轉好輪盤

00:06:49.015 --> 00:06:52.345
能量階梯把他們昇起，直達創造之泉

NOTE Paragraph

00:06:55.640 --> 00:06:58.353
當一切如風，餘下也只有真相

00:06:58.353 --> 00:07:01.067
哪似水流年的記憶再浮現眼前：

00:07:01.067 --> 00:07:03.187
「創世機」翻天覆地打造世界大同

00:07:03.187 --> 00:07:05.962
彥霖身為機器人總工程師看在眼裡

00:07:05.962 --> 00:07:08.906
怵惕惻隱之心不禁戚戚

00:07:08.906 --> 00:07:11.946
當「八達圍」築起，把人圍堵城牆內

00:07:11.946 --> 00:07:14.586
專恣跋扈之甚
已離經叛道天地不容了

00:07:14.586 --> 00:07:17.067
彥霖決心撥亂反正，創造了三枚瑰寶

00:07:17.067 --> 00:07:21.221
讓力量、創造、記憶歸真，回歸人民

00:07:21.221 --> 00:07:24.131
並暗中散落於三處社區，潛藏民間

00:07:24.131 --> 00:07:26.449
彥霖還來不及說出運用之法

00:07:26.449 --> 00:07:28.204
政府就發現她的叛逆

00:07:28.204 --> 00:07:29.959
派遣機器打造的土龍芻狗大肆搜捕

00:07:29.959 --> 00:07:31.889
想把彥霖及其他程式設計師一網打盡

00:07:31.889 --> 00:07:34.575
在最後關頭，彥霖再一次善用創世機

00:07:34.575 --> 00:07:36.682
創造了一個機器人，囑託他至死守護

00:07:36.682 --> 00:07:39.644
這台天地間的橐籥、造化萬物的玄機

00:07:39.644 --> 00:07:42.329
並埋藏巨型迷宮內
免於平庸無知之惡

00:07:42.329 --> 00:07:44.743
彥霖給了守護機器人一個名字：凌杰

NOTE Paragraph

00:07:51.801 --> 00:07:55.631
能量階梯一閃消失，送上無情的迫降