本文首發(fā)于 B 站《深圳 IO》文集（https://www.bilibili.com/read/readlist/rl569860）。原創(chuàng)不易，轉(zhuǎn)載請(qǐng)注明出處。

關(guān)卡展示

這一關(guān)我們要做的是根據(jù)實(shí)時(shí)的 x, y 值輸出映射的電源值。具體的映射規(guī)則需要參考數(shù)據(jù)手冊(cè)：

不難發(fā)現(xiàn)，電源值 p 和 x, y 之間滿足以下規(guī)律：

其中：

那么，我們用一塊芯片根據(jù) x, y 的值算 Δp 的值，另一塊芯片根據(jù) x 和 Δp 的值計(jì)算 p 的值并輸出即可。代碼如下：

我們說過，用連續(xù) + 號(hào)串聯(lián)的測試指令間構(gòu)成【與】關(guān)系。那么我們看左邊的芯片，僅當(dāng) x > 39（tgt p1 39）且 x < 80（+ tlt p1 80）且 y > 39（+ tgt p0 39）且 y < 80（+ tlt p0 80）時(shí)，Δp 才是 50（+ mov 50 x1）；以上任何一個(gè)條件不滿足時(shí)，Δp 都是 0（- mov 0 x1）。

然后我們看右邊的芯片。因?yàn)楫?dāng) 20 ≤ x < 60 時(shí)，p = 0 + Δp = Δp，所以當(dāng) x > 19（tgt p0 19）且 x < 60（+ tlt p0 60）時(shí)，直接將 Δp 原封不動(dòng)地傳給【電源】端口就 OK 了（+ mov x1 p1）。以上任何一個(gè)條件不滿足時(shí)，都需要將?Δp 加上 30 再傳給【電源】端口（- mov x1 acc, - add 30, - mov acc p1）。這里我們沒有像上一關(guān)那樣使用 slx 指令等待同步，是因?yàn)閮蓧K芯片很明確地每一秒鐘都需要通信，并不是不確定什么時(shí)候要讀，所以不需要用 slx 指令等待同步。

點(diǎn)擊左下角的【模擬】，稍等片刻，便會(huì)彈出結(jié)算界面：

優(yōu)化電量

我們知道，在【與】邏輯里，僅當(dāng)所有條件都成立時(shí)，最終的邏輯值才能為真，而只要任意一個(gè)條件不成立，最終的邏輯值均為【假】。我們現(xiàn)在看上面的計(jì)算 Δp 值的那塊芯片。如果最終 Δp 的值是 50，那么一定是經(jīng)過了四次判斷才確定的，這一部分的電量無論如何都省不下去。問題在于如果最終?Δp 的值是 0，那么是經(jīng)過幾次判斷后得出的呢？1~4 次都有可能。那么，如果我們能正確調(diào)整這四個(gè)條件的判斷順序，使得芯片盡可能在早期就判斷出?Δp 的值為 0，那么就可以在運(yùn)行時(shí)間里大量節(jié)省判斷的次數(shù)，從而達(dá)到節(jié)省電量的目的。

我們?cè)诖酥埃瓤紤]一個(gè)簡化版的問題：一個(gè)隨機(jī)數(shù)生成器每秒鐘都會(huì)生成一個(gè) 1~10 范圍內(nèi)的整數(shù)，每個(gè)數(shù)字的出現(xiàn)概率相等。你每秒鐘都需要判斷當(dāng)前的隨機(jī)數(shù)是否在 2~4 之間。你該如何設(shè)計(jì)算法才能讓代碼盡可能高效運(yùn)行？

我們先考慮“先判斷是否 >1，再判斷是否 <5”這樣的情況：

可以看到，如果“先判斷是否 >1，再判斷是否 <5”，那么只有 10% 的情況只判斷一次，90% 的情況都是要判斷兩次才能得出結(jié)論的。1 秒鐘的平均耗電為 1 × 10%?+ 2 × 90% = 1.9。那么如果我們調(diào)換一下順序，“先判斷是否 <5，再判斷是否 >1”會(huì)怎樣呢？

此時(shí)就不一樣了，有 60% 的可能性在第一次判斷時(shí)就得出了結(jié)論。此時(shí) 1 秒鐘的平均耗電為：1 × 60% + 2 × 40% = 1.4，相比于上一版方案，每秒鐘平均減少了 0.5 次判斷。

相信聰明的你此時(shí)已經(jīng)發(fā)現(xiàn)了規(guī)律：多個(gè)條件在一起做【與】運(yùn)算時(shí)，為了提高運(yùn)行效率，應(yīng)當(dāng)優(yōu)先判斷成立概率低的條件，盡最大可能在前期就篩掉不滿足條件的輸入量。

像上面我舉的那個(gè)例子，一個(gè) 1~10 的隨機(jī)數(shù)里，有 90% 的可能性 >1，有 40% 的可能性 <5。那么我們?cè)谂袛嗟臅r(shí)候，就應(yīng)當(dāng)先判斷是否 <5，這樣我們就有 60% 的可能性在第一輪判斷中就得出結(jié)論，和先判斷是否 >1 相比，能大大提高效率。

回到我們的題目，Δp 的值是和四個(gè)條件相關(guān)的，僅當(dāng)四個(gè)條件都成立時(shí)才是 50。這四個(gè)條件依次是：x > 39，x < 80，y > 39，y < 80。那么，如果?Δp 的值是 0，我們?cè)撛趺凑{(diào)整判斷順序，才能盡快地得出結(jié)論呢？現(xiàn)在我們已知 x 和 y 都在 0~100 范圍內(nèi)。那么，我們列出這四個(gè)條件的成立概率：

• x > 39（61 / 101 = 60.4%）

• x < 80（80 / 101 = 79.2%）

• y > 39（61 / 101 =?60.4%）

• y < 80（80?/ 101 =?79.2%）

根據(jù)“優(yōu)先判斷成立概率低的條件”這條原則，我們應(yīng)當(dāng)先判斷 x > 39 和 y > 39 這兩個(gè)條件，再判斷 x < 80 和 y < 80 這兩個(gè)條件。

然后再看計(jì)算 p 值的部分。p 值僅和 x，以及剛剛計(jì)算好的，可以視為常數(shù)的 Δp 相關(guān)。僅當(dāng) x > 19 和 x < 60 同時(shí)成立時(shí)，p = Δp；任何一條不成立時(shí)，p = 30 + Δp。那么同樣地，我們將這兩個(gè)條件的成立概率列出來：

• x > 19（81 / 101 = 80.2%）

• x < 60（60 / 101 = 59.4%）

所以，這里我們需要先判定 x < 60 這個(gè)條件，再判定 x > 19 這個(gè)條件。綜上所述，我們將代碼改寫成如下的樣子并運(yùn)行：

在我們剛才的概率統(tǒng)計(jì)里，x > 39 和 y > 39 的概率是一樣的。以上代碼中，先判斷 y > 39 是嘗試出來的結(jié)果，在這道題的 80 個(gè)測試樣例里，先判斷 y > 39 比先判斷 x > 39 要省 6 格電。x < 80 和 y < 80 的先后順序同理，也是嘗試出來的結(jié)果，前者比后者省 2 格電。這些是受具體測試樣例而影響的，但也側(cè)面說明了：兩個(gè)概率相等的條件的判定先后順序，對(duì)整體電量的影響很小。

優(yōu)化代碼行數(shù)

將右邊芯片的【與】邏輯改為【或】邏輯（即測試指令間用 - 串聯(lián)），即可省掉一行代碼行數(shù)，代價(jià)是耗電量會(huì)稍有增加。具體算法如下：先將 Δp 的值存入 acc，然后 x < 20 及 x > 59 有任意一條成立時(shí)，acc 在原值的基礎(chǔ)上 +30，都不成立則 acc 維持原狀。最后將 acc 送入【電源】端口。

【或】邏輯的條件書寫順序和【與】邏輯正好相反，應(yīng)當(dāng)先寫成立概率高的條件。因?yàn)椤净颉窟壿嬛荒芏搪返贸觥菊妗拷Y(jié)論，所以我們應(yīng)當(dāng)盡快得出【真】結(jié)論。而顯然，優(yōu)先判斷成立概率高的條件更容易快速得出【真】結(jié)論。所以這里優(yōu)先判斷 x > 59，再判斷 x < 20。代碼如下：