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

關(guān)卡展示

本關(guān)要求當(dāng)（包括當(dāng)前時間在內(nèi)的）前 8 秒內(nèi)，污染監(jiān)測傳感器的平均值大于等于 50 時關(guān)閉窗戶，平均值小于 50 時開啟窗戶。題目保證前 7 秒的平均值不會大于等于 50。因此問題等價于：前 8 秒內(nèi)的污染值總和大于等于 400 時關(guān)閉窗戶，小于 400 時開啟窗戶。

初版方案：用 RAM 記錄現(xiàn)在和過往的污染值，每一秒鐘我們都統(tǒng)計前 8 秒的污染值總和是否小于 400，然后決定是否打開窗戶就行了。由于 RAM 可以記 14 個數(shù)字，所以記住前 8 秒的污染值那是綽綽有余。電路圖和代碼如下：

首先我們將當(dāng)前的污染值存入 RAM（mov p0 x0），然后準備開始統(tǒng)計前 8 秒的污染值總和。設(shè)當(dāng)前 RAM 的指針地址是 a，則我們需要統(tǒng)計 a-8 ~ a-1 地址范圍內(nèi)的污染值總和。由于讀取一次 RAM 后地址會自增，所以最終地址是 a-1+1 = a 自己。我們將最終地址 a 放入 dat 寄存器（mov x1 dat），然后將 RAM 的地址置為首地址 a-8，準備計算前 8 秒的污染值總和（mov x1 acc, sub 8, mov acc x1）。計算總和之前，我們需要將 acc?清零（mov 0 acc）。然后開始不斷讀 RAM，并將讀到的值加到 acc 里（add x1）。每讀一個值，都判定一次是否到達結(jié)束地址（teq x1 dat）。尚未到達結(jié)束地址時，跳回第 7 行繼續(xù)累加（- jmp 7），直到讀完前 8 秒的污染值后，計算這些污染值的總和是否小于 400（tlt acc 400）。小于 400 時打開窗戶（+ mov 100 p1），否則關(guān)閉窗戶（- mov 0 p1）。做完這些操作后，休眠一秒，進入下一個時鐘周期（slp 1）。

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

利用【滑動窗口】算法提高運行效率

我們的初版算法達到了驚人的 1.5K 耗電量。這是因為我們在計算前 8 秒的污染值總和時涉及到了太多重復(fù)的計算。設(shè) v(i)?為第 i 秒時的污染值，S(j, k) 為第 j~k 秒的污染值總和。那么，我們的初版算法里，是這樣計算污染值總和的：

• S(1, 8) = v(1) + v(2) + ... + v(8)

• S(2, 9) = v(2) + v(3) + ... + v(9)

• S(3, 10) = v(3) + v(4) + ... + v(10)

• ...

可以看到，每次都要讀取 8 個數(shù)進行累加。如果我們使用動態(tài)計算的思維（下一個結(jié)果由上一個結(jié)果動態(tài)推導(dǎo)而出），就可以大大減少計算量：

• S(1, 8) = v(1) + v(2) + ... + v(8)
  

• S(2, 9) = S(1, 8) - v(1) + v(9)，無需重復(fù)計算 v(2) + v(3) + ... + v(8)

• S(3, 10) = S(2, 9) - v(2) + v(10)，無需重復(fù)計算 v(3) + v(4) + ... + v(9)

• ...

可以看到，改進的算法里，下一秒的污染總和，只需要在上一秒的基礎(chǔ)上減去一個值再加上一個值就可以了，只需要讀兩個數(shù)字。相比于初版方案，減少了大量重復(fù)計算，效率大大提升。這種通過移動左右邊界，動態(tài)計算區(qū)間和的算法就叫做【滑動窗口】算法，簡稱【滑窗】算法。正好這道題也是個【滑窗】問題。

改進后的電路圖和代碼如下：

首先我們將右邊界置為 8，左邊界保持為 0，視為從第 8 秒開始統(tǒng)計，第 0~7 秒的污染值之和為 0（mov 8 x3）。每到達新的一秒，我們將 acc 的值減去原先左邊界的值（sub x0），然后加上新值（add p0），并將新值存入原先的右邊界所指向的空間（mov p0 x2）。操作完成后，左邊界和右邊界會各向右移動一格。此時我們便完成了一次【滑窗】計算，acc 的值為前 8 秒內(nèi)的污染值總和。判斷該值是否小于 400（tlt acc 400），小于 400 時打開窗戶（+ mov 100 p1），否則關(guān)閉窗戶（- mov 0 p1）。做完這些操作后，休眠一秒，進入下一個時鐘周期（slp 1）。

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

電量由 1.5K 驟降到 277，代碼行數(shù)也由 13 行降到 8 行，質(zhì)的飛躍！