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

TIS-NET 第 18 關(guān)《缺失數(shù)字補(bǔ)全器》（Sequence Gap Interpolator）關(guān)卡展示

本關(guān)的 IN 會(huì)不斷提供一些以 0 結(jié)尾的序列，每個(gè)序列的最小值和最大值之間缺了一個(gè)數(shù)。例如，現(xiàn)在你收到了 [78, 77, 74, 75, 0] 這個(gè)序列。這個(gè)序列的最小值是 74，最大值是 78。在 74~78 之間有 5 個(gè)數(shù)字，但是這個(gè)序列里卻只有 4 個(gè)數(shù)字，缺失了 76。你要做的就是把這個(gè)缺失了的數(shù)字找出來(lái)并輸出。

我們可以通過(guò)求和的方式來(lái)找出序列中缺失的數(shù)。設(shè)收到的序列為 s，缺失的數(shù)為 miss，最小值為 min，最大值為 max，易得：

用沒(méi)有缺失任何數(shù)字的序列之和，減去缺失了一個(gè)數(shù)字的序列之和，就找到了那個(gè)缺失的數(shù)字。本題的 C 語(yǔ)言代碼如下：

轉(zhuǎn)寫成的 TIS-100 代碼如下：

本關(guān)雖然有兩個(gè)棧，但本關(guān)沒(méi)有反復(fù)讀取歷史數(shù)據(jù)的需求，所以兩個(gè)棧完全用不上。

IN 下方的節(jié)點(diǎn)，收到第 1 個(gè)數(shù)后，將它分別傳給左邊和下面的節(jié)點(diǎn)（分別用來(lái)存儲(chǔ) min 和 ans 的值）（mov up acc, mov acc left, mov acc down）。從第 2 個(gè)數(shù)開始（mov up acc），就要判斷是否收到了序列末端的 0。未收到 0 時(shí)按順序執(zhí)行，收到 0 時(shí)跳到第 9 行執(zhí)行（jez 9）。尚未收到 0 時(shí)，需要給左邊計(jì)算 min 的節(jié)點(diǎn)發(fā)送一個(gè) 1 信號(hào)，然后把當(dāng)前收到的數(shù)給左邊發(fā)兩次，給下方計(jì)算 ans 的節(jié)點(diǎn)發(fā)一次（mov 1 left, mov acc left, jmp 2, mov acc left, mov acc down）。收到序列末端的 0 后，給左邊發(fā)送一個(gè) 5 信號(hào)（mov 5 left），給下邊發(fā)送一個(gè) -999（mov -999 down），然后從左邊接收 min，然后根據(jù)下方節(jié)點(diǎn)的指令，依次給下方發(fā)送 min、min+1、min+2……直到最終的 max 值（jro down, mov acc down, add 1, jmp c）。

左上角的節(jié)點(diǎn)就是計(jì)算序列里的最小值的，套路都很熟悉了：將右邊傳來(lái)的首數(shù)字放入 acc，暫時(shí)視為 min（mov right acc）。然后我們會(huì)收到兩種信號(hào)（jro right）：

• 收到 1 信號(hào)時(shí)，說(shuō)明尚未到達(dá)序列末端，我們向下跳 1 行，將歷史最小和新的挑戰(zhàn)值做差值運(yùn)算（sub right），差值為正時(shí)，挑戰(zhàn)者 < 歷史最小，挑戰(zhàn)成功，跳回第 1 行，將挑戰(zhàn)者作為新的 min（jgz 1, mov right acc）；差值為 0 或負(fù)時(shí)，挑戰(zhàn)者 >= 歷史最小，挑戰(zhàn)失敗，令差值加回挑戰(zhàn)者的值，將 min 還原成歷史值（add right, jmp 2）。

• 收到 5 信號(hào)時(shí)，說(shuō)明到達(dá)了序列末端。我們向下跳 5 行，將當(dāng)前找到的 min 發(fā)給右邊（mov acc right），然后跳回第 1 行，丟棄掉當(dāng)前的 min，準(zhǔn)備計(jì)算下一個(gè)序列的 min。

然后是中央節(jié)點(diǎn)。第一階段，我們將 acc 設(shè)置為 +999 的偏置（mov 999 acc），然后上方會(huì)發(fā)來(lái)序列里的所有值，我們求出?999 - sum(s) 的值（sub up, jgz 2）。當(dāng)讀到了序列末端時(shí)，上方會(huì)突然發(fā)來(lái)一個(gè)?+999，這時(shí)候我們的 sub up 指令會(huì)清除原先的 +999 偏置，acc 會(huì)突然變成負(fù)數(shù)，值為 -sum(s)。

第二階段，上方會(huì)依次將 min, min+1, min+2……的值發(fā)來(lái)，我們每發(fā)送一條 1 指令（mov 1 up），上方就會(huì)給我們發(fā)一個(gè)數(shù)，我們將收到的數(shù)加回到 acc 里（add up）。尚未加到正數(shù)時(shí)，說(shuō)明剛才加上的數(shù)還不是 max，此時(shí)跳回第 4 行繼續(xù)加（jlz 4）。直到 acc 變?yōu)檎龜?shù)后，我們就得到了當(dāng)前序列里缺失的數(shù)，此時(shí)給上方發(fā)送 -11，讓上方跳回第 1 行，接收下一個(gè)序列的首數(shù)字（mov -11 up），自己則是將找到的缺失數(shù)字發(fā)給下方（mov acc down）。

下方節(jié)點(diǎn)沒(méi)啥好說(shuō)的，純粹傳話（mov up down）。

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