【TIS-100 攻略】TIS-NET 第 16 關(guān)：反向索引查詢(xún)器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請(qǐng)注明出處。
TIS-NET 第 16 關(guān)《反向索引查詢(xún)器》（Back Reference Reifier）關(guān)卡展示
本關(guān)的 IN.A 會(huì)不斷給你提供一些數(shù)字，然后：
當(dāng)你從 IN.R 里收到 0 時(shí)，你需要向 OUT 輸出 IN.A 中的當(dāng)前數(shù)字；
當(dāng)你從 IN.R 里收到 -1 時(shí)，你需要向 OUT 輸出 IN.A 中的前 1 個(gè)數(shù)字；
當(dāng)你從 IN.R 里收到 -2 時(shí)，你需要向 OUT 輸出 IN.A 中的前 2 個(gè)數(shù)字；
當(dāng)你從 IN.R 里收到 -3?時(shí)，你需要向 OUT 輸出 IN.A 中的前 3?個(gè)數(shù)字；
當(dāng)你從 IN.R 里收到 -4?時(shí)，你需要向 OUT 輸出 IN.A 中的前 4?個(gè)數(shù)字。
IN.R 的最小值為 -4，也就是最多查詢(xún)到前?4 個(gè)數(shù)字。
我們可以借用第一章第 18 關(guān)《信號(hào)窗口篩選器》里的【滑動(dòng)窗口】算法思想，維護(hù)最近 5 個(gè)值，并選擇請(qǐng)求的值輸出即可（傳送門(mén)：【TIS-100 攻略】第 18 關(guān)：信號(hào)窗口篩選器）。問(wèn)題在于，本關(guān)的版面上沒(méi)有提供任何棧，所以我們只能通過(guò)節(jié)點(diǎn)來(lái)存儲(chǔ)這最近的 5 個(gè)值。設(shè)當(dāng)前值為 a[0]，前 4 個(gè)值分別為 a[-1] ~ a[-4]，那么以下的示意圖里提供了一種維護(hù)最近 5 個(gè)值的方法：
至此：
當(dāng)前數(shù)字變?yōu)榱?a[1]；
節(jié)點(diǎn) A 的 acc 為當(dāng)前數(shù)字的前 2 個(gè)數(shù)字 a[-1]，bak 為當(dāng)前數(shù)字的前 1 個(gè)數(shù)字 a[0]；
節(jié)點(diǎn) B 的 acc 為當(dāng)前數(shù)字的前 4 個(gè)數(shù)字 a[-3]，bak 為當(dāng)前數(shù)字的前 3 個(gè)數(shù)字 a[-2]。將以上下標(biāo)全部減去 1，我們就又回到了第一步時(shí)的樣子。
節(jié)點(diǎn) C 會(huì)依次收到 a[-4] ~ a[0]，但我們只能選擇其中 1 個(gè)量輸出，其余 4 個(gè)量都要丟棄。那么我們?cè)谳敵鲋?，要丟棄掉多少個(gè)量呢？
當(dāng) R 為 0?時(shí)，我們要輸出 a[0]，要丟棄前方的?a[-4] ~ a[-1] 共 4 個(gè)量；
當(dāng) R 為?-1 時(shí)，我們要輸出 a[-1]，要丟棄前方的 a[-4] ~ a[-2] 共 3 個(gè)量；
當(dāng) R 為?-2?時(shí)，我們要輸出 a[-2]，要丟棄前方的 a[-4]?~?a[-3]?共 2?個(gè)量；
當(dāng) R 為?-3?時(shí)，我們要輸出 a[-3]，要丟棄前方的 a[-4]?共?1?個(gè)量；
當(dāng) R 為?-4?時(shí)，我們要輸出 a[-4]，沒(méi)有量可以丟棄。
因此，輸出前要丟棄的量 n 和?R?的關(guān)系為：
如果輸出的不是 a[0]，那么輸出完畢后，剩余的量也要丟棄。不過(guò)這部分量我們可以用【監(jiān)測(cè)哨兵】的方法來(lái)丟棄：上方的節(jié)點(diǎn)將 a[-4]~a[0] 全部發(fā)送完畢后，最終發(fā)送一個(gè)哨兵 0。當(dāng)節(jié)點(diǎn) C 接收到最終的哨兵 0 時(shí)，停止丟棄。本關(guān)的思路就是這樣，代碼如下：
IN.R 下方的節(jié)點(diǎn)將收到的 R 值傳給右邊的 A 節(jié)點(diǎn)（mov up right）。
A 節(jié)點(diǎn)和 B 節(jié)點(diǎn)首先接力將本次的 R 傳給 C 節(jié)點(diǎn)（mov left down, mov up down）。接下來(lái) A 節(jié)點(diǎn)和 B 節(jié)點(diǎn)按照上方示意圖的指示，向 C 節(jié)點(diǎn)發(fā)送 a[-4] ~ a[0] 的值。
首先是 B 節(jié)點(diǎn)，先傳 acc 里的 a[-4]（mov acc down），并接收?A 節(jié)點(diǎn)傳來(lái)的 a[-2]，覆蓋掉原先的 a[-4]（mov up acc）。然后傳 bak 里的 a[-3]（swp, mov acc down, swp）和 acc 里的 a[-2]（mov acc down）。接著，A 節(jié)點(diǎn)會(huì)將 a[-1] 和 a[0] 發(fā)過(guò)來(lái)，我們?cè)獠粍?dòng)地將這兩個(gè)數(shù)傳下去（mov up down, mov up down）。最后，發(fā)送哨兵 0（mov 0 down），并將 acc 和 bak 交換（swp）。
A 節(jié)點(diǎn)簡(jiǎn)單一些，先傳 acc 里的 a[-2]（mov acc down），然后從 IN.A 接收 a[0]，覆蓋掉原先的 a[-2]（mov up acc），接著傳 bak 里的 a[-1]（swp, mov acc down, swp）和 acc 里的 a[0]（mov acc down），最后將 acc 和 bak 交換（swp）。
C 節(jié)點(diǎn)按照計(jì)劃，首先丟棄前 4+R 個(gè)量：
將 acc 設(shè)為 4+R（mov 4 acc）
（add up）
若 4+R 為 0，則不丟棄任何量，直接跳到第 7 行（jez 7），
否則每丟棄一個(gè)量（mov up nil），
就令 acc 減去 1（sub 1），
一直如此做直到 acc 減到 0 為止（jnz 4）。
將該丟棄的量悉數(shù)丟棄后，將下一個(gè)量送到輸出口（mov up down），
然后繼續(xù)丟棄剩下的量（mov up acc），
直到遇到哨兵 0 為止（jnz 8）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會(huì)彈出結(jié)算界面：
也許我以上說(shuō)的前 4 個(gè)數(shù)的維護(hù)方案不是最優(yōu)的，我的運(yùn)行時(shí)長(zhǎng)離直方圖最左端還有不少距離。如果讀者有更好的維護(hù)方案，請(qǐng)留言告訴我。
