[TED-Ed 原創系列]
《時代女神 x 程式邏輯革命》
[地點:一九八樹林]
[第七集:覺醒]
踏進巨塔的底層
彥霖和凌杰要先越過能量布陣
才能觸及第二枚瑰寶:創造之泉
彥霖要藉三道能量流登上塔頂
足下一步,啟動計時器倒數 60 秒
在房間的盡頭,有一個能量池
一座座隱形能量塔一字排開
中間的空格可以蓄積能量
一分鐘後,能量會如急流般瀉下
每次填滿一個空格
力場則在前後防止流溢
在風平浪靜的 60 秒間
彥霖、凌杰要決定降下多少格能量
在三關挑戰中,每關都要調好份量
能量池滿而不溢才算圓滿
能量階梯就會將他們推上下一關
計較份量若有閃失,能量階梯便破解
一腳踩空,就是無情的迫降
牆上的示意圖,枚舉幾個例子
這範例蓄積恰恰兩格能量
範例二則蓄積四格:
第二欄 3 格、第三欄 1 格
範例三也是蓄積四格:
左右兩側框不住,能量會外溢
能量雨降下後會盡量往空子鑽進去
當所有空格填滿才會滿溢
凌杰可逐次顯現一座能量塔再數高度
但不能一窺整個能量池的全豹
彥霖要為凌杰設計一個怎樣的程式
來找出能量池框得下多少格能量?
若要自己動腦筋,就按一下暫停
這道題可以這樣入手:
但凡一個空格,要框得住能量
最左邊,必須總得有一堵牆框住
最右邊,也得有一堵牆框住
但凌杰每一格都左顧右盼會很費時
假如凌杰逐欄來看每一座能量塔呢
比如說,這裡框得住多少格能量?
[若要自己動腦筋,就按一下暫停]
回來剛才的例子,去分析這道題
能量格疊成塔,計有 5 欄
最左一欄已到頂,框不下任何能量
第二欄,上面可再加 3 格
左右這兩座四格塔,能量框得住
算法是將能量塔
最高平整的高度——4
減去能量塔本身的高度——1
即 4 減 1 得 3
第三欄同理:左 4、右 4、高 3 格
故可蓄積 4 減 3 格,即 1 格
第四、五欄靠右都沒有更高的塔框住
所以,這兩欄都不能蓄積任何能量
這個概念可用一個演算法實踐:
凌杰每次以一欄塔作參照點
靠左,逐欄找最高一座塔的高度
又挨右,找最高一座塔的高度
兩者以較低者為蓄積後的平整高度
結果若高於此欄本身的高度
就減去原來的塔高
得出這座塔會蓄積到多少格能量
相反,結果若少於或等於原來塔高
能量就不會留住,往左右流走
凌杰可用一個迴圈橫越整個能量池
從最左一欄塔開始,每次一欄向右移
逐欄塔重複相同的幾個步驟:
先向左找最高一欄
再向右找最高一欄
取二者較低者,減去原來欄高
若是正數,則加進蓄積格數的總計
有多少欄,迴圈就重複多少次
這個方法雖然行得通
但能量池大的話就很費時
每個步驟凌杰都要向左、向右查看
若有 N 座塔,就要看 N 次
有更快的方法嗎?
有一個省時妙計:一開始可先取巧
凌杰從最左開始一邊數一邊做小抄
以流水帳方式記下當前最高的欄高
範例中,首欄是 2
然後也是 2,因為第一欄較高
接著是 4、4、4
之後就輪到靠右的最高欄高
做法是從右往左重複一遍:
1、3、4、4、4
最後凌杰記憶中就有一個這樣的表
現在凌杰只消多一重功夫
用先前同一條等式
去計算每欄塔上可框住多少格能量:
小抄中儲存的左值、右值取較低者
減去該能量塔原來的高度
N 座塔本來要看 N 次,現在只消 3 次
即是所謂的線性時間
這個解題方案還可以進一步優化
但已可解燃眉之急了
彥霖、凌杰雙劍合璧
第一關如沐春風,翻手之間就竄升
第二關稍有難度
第三關規模龐大,有數十座能量塔
計時器快歸零,幸好編寫程式夠快
彥霖及時轉好輪盤
能量階梯把他們昇起,直達創造之泉
當一切如風,餘下也只有真相
哪似水流年的記憶再浮現眼前:
「創世機」翻天覆地打造世界大同
彥霖身為機器人總工程師看在眼裡
怵惕惻隱之心不禁戚戚
當「八達圍」築起,把人圍堵城牆內
專恣跋扈之甚
已離經叛道天地不容了
彥霖決心撥亂反正,創造了三枚瑰寶
讓力量、創造、記憶歸真,回歸人民
並暗中散落於三處社區,潛藏民間
彥霖還來不及說出運用之法
政府就發現她的叛逆
派遣機器打造的土龍芻狗大肆搜捕
想把彥霖及其他程式設計師一網打盡
在最後關頭,彥霖再一次善用創世機
創造了一個機器人,囑託他至死守護
這台天地間的橐籥、造化萬物的玄機
並埋藏巨型迷宮內
免於平庸無知之惡
彥霖給了守護機器人一個名字:凌杰
能量階梯一閃消失,送上無情的迫降