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

TIS-NET 第 2 關(guān)《數(shù)列求和計(jì)算器》（Integer Series Calculator）關(guān)卡展示

本關(guān)的 IN 會(huì)提供給你一些數(shù)字，每收到一個(gè)數(shù)字，就輸出 1 + 2 + ... + IN 之和。

相信闖關(guān)到這一步的你，做個(gè)累加器已經(jīng)綽綽有余了吧：

上方節(jié)點(diǎn)將 IN 里的值傳給中央節(jié)點(diǎn)。

中央節(jié)點(diǎn)將 IN 到 1 的值依次傳給下方節(jié)點(diǎn)，最后傳一個(gè) 999。

下方節(jié)點(diǎn)將 acc 初始化為 -999 的偏置，并從上方接收數(shù)字，將收到的數(shù)全部累加起來，當(dāng) acc 突然變成正數(shù)時(shí)，輸出答案。

都是老套路了。我們點(diǎn)擊左下角的【RUN】運(yùn)行程序：

使用【查表法】提高運(yùn)行速度

如果這篇攻略到此結(jié)束了，那也太沒勁了。這里我們?cè)僭O(shè)計(jì)一個(gè)能顯著提高運(yùn)行速度的解決方案。

本關(guān)要求的是 1 + 2 + ... + n 之和。根據(jù)等差數(shù)列求和公式（高斯公式）

可得，當(dāng) n = 44 時(shí)，∑ (k=1, n) k = 44 × 45 / 2 = 990；而當(dāng) n = 45 時(shí)，∑ (k=1, n) k = 45 × 46 / 2 = 1035。因此，使得結(jié)果不超過 999 的最大 n 為 44。也就是說我們從 IN 里收到的數(shù)字只有 1~44 這幾種，雖說 TIS-100 里沒有提供乘法指令，但我們完全可以用查表的方式獲得這 44 種答案中的一種，而不需要刻意去算出每一個(gè)答案。本關(guān)需要使用 4 個(gè)節(jié)點(diǎn)（即 4 張表）來存儲(chǔ) n = 1~44 時(shí)對(duì)應(yīng)的答案。查表法的代碼如下：

右邊的三個(gè)節(jié)點(diǎn)，以及左下角的節(jié)點(diǎn)堆滿了密密麻麻的數(shù)字，它們分別是 1~4 號(hào)表。

右上角的 1 號(hào)表存儲(chǔ)了 n 為 32~44 時(shí)?∑?(k=1,?n)?k 的值。當(dāng) 32 <= n <= 44 時(shí)，你需要向 1 號(hào)表傳入 n-31 的值，將 32~44 映射為 1~13，利用 jro 指令跳轉(zhuǎn)到對(duì)應(yīng)的位置去執(zhí)行，從而得到答案。傳入的參數(shù)與答案的對(duì)應(yīng)關(guān)系如下表所示：

中間靠右的 2 號(hào)表存儲(chǔ)了 n 為 19~31 時(shí) ∑?(k=1,?n)?k 的值。當(dāng) 19 <= n <= 31 時(shí)，你需要向 2 號(hào)表傳入 n-18 的值，將 19~31 映射為 1~13，利用 jro 指令跳轉(zhuǎn)到對(duì)應(yīng)的位置去執(zhí)行，從而得到答案。傳入的參數(shù)與答案的對(duì)應(yīng)關(guān)系如下表所示：

右下角的 3 號(hào)表存儲(chǔ)了 n 為 9~18?時(shí)?∑?(k=1,?n)?k 的值。當(dāng) 10 <= n <= 18 時(shí)，你需要向 3 號(hào)表傳入 n-9 的值，將 10~18 映射為 1~9，利用 jro 指令跳轉(zhuǎn)到對(duì)應(yīng)的位置去執(zhí)行，從而得到答案。傳入的參數(shù)與答案的對(duì)應(yīng)關(guān)系如下表所示：

左下角的 4 號(hào)表存儲(chǔ)了 n 為 1~9?時(shí)?∑?(k=1,?n)?k 的值。當(dāng) 1 <= n <= 9 時(shí)，你需要向 4 號(hào)表傳入 n 的值，利用 jro 指令跳轉(zhuǎn)到對(duì)應(yīng)的位置去執(zhí)行，從而得到答案。傳入的參數(shù)與答案的對(duì)應(yīng)關(guān)系如下表所示：

位于第 2 列的上、中、下三個(gè)節(jié)點(diǎn)是用來對(duì)四個(gè)表發(fā)出查表指令的。上方節(jié)點(diǎn)檢查 n 是否大于 31，即減去 31 后（mov?-31 acc, add up）是否大于 0。若滿足條件，說明 n?在 32~44 范圍內(nèi)，跳到第 8 行執(zhí)行（jgz?8）。由第 1 張表格的信息可知，32 <= n <= 44 時(shí)，向 1 號(hào)表傳入 n-31 可以得到?∑?(k=1,?n)?k 的值。此時(shí)的 acc 已經(jīng)是 n-31，所以直接將 acc 發(fā)給 1 號(hào)表（mov acc right），然后給中央節(jié)點(diǎn)發(fā)送一個(gè) 12?信號(hào)（mov 12 down），再將 1 號(hào)表發(fā)來的返回值傳給中央節(jié)點(diǎn)（mov right down）。當(dāng)?n?不在 32~44 范圍內(nèi)時(shí)，上方節(jié)點(diǎn)是無能為力的。此時(shí)我們將目光跳回到第 4 行，令?acc 加回 31（add 31），將 acc 由 n-31 變回成 n 后，給中央節(jié)點(diǎn)發(fā)一個(gè) 1 信號(hào)（mov 1 down），再將 n 值交給中央節(jié)點(diǎn)處理（mov acc down, jmp 1）。

中央節(jié)點(diǎn)首先監(jiān)聽上方節(jié)點(diǎn)的信號(hào)（jro up）。上方節(jié)點(diǎn)發(fā)送 12 信號(hào)時(shí)，表示 n 在 32~44 范圍內(nèi)，緊接著它會(huì)把答案也一并發(fā)來。這時(shí)候我們向下跳 12 行，給下方節(jié)點(diǎn)發(fā)送一個(gè) 11 信號(hào)（mov 11 down），再將答案向下發(fā)（mov up down）就完事了，我們不需要再繼續(xù)查表。

而當(dāng)上方節(jié)點(diǎn)發(fā)送 1 信號(hào)時(shí)，表示 n 不在 32~44 范圍內(nèi)，需要由我們來進(jìn)一步處理。此時(shí)我們向下跳 1 行，檢查 n 是否大于 18，即減去 18 后（mov -18 acc, add up）是否大于 0。若滿足條件，說明 n 在 19~31 范圍內(nèi)，跳到第 9 行執(zhí)行（jgz 9）。由第 2 張表格的信息可知，19 <= n <= 31 時(shí)，向 2 號(hào)表傳入 n-18 可以得到?∑?(k=1,?n)?k 的值。此時(shí)的 acc 已經(jīng)是 n-18，所以直接將 acc 發(fā)給 2 號(hào)表（mov acc right），然后給下方節(jié)點(diǎn)發(fā)送一個(gè) 11 信號(hào)（mov 11 down），再將 2 號(hào)表發(fā)來的返回值傳給下方節(jié)點(diǎn)（mov right down, jmp 1）。當(dāng) n 不在 19~31 范圍內(nèi)時(shí)，中央節(jié)點(diǎn)也是無能為力的。此時(shí)我們將目光跳回第 5 行，令 acc 加回 18（add 18），將 acc 由 n-18 變回成 n 后，給下方節(jié)點(diǎn)發(fā)一個(gè) 1 信號(hào)（mov 1 down），再將 n 值交給下方節(jié)點(diǎn)處理（mov acc down, jmp 1）。

下方節(jié)點(diǎn)首先監(jiān)聽中央節(jié)點(diǎn)的信號(hào)（jro up）。中央節(jié)點(diǎn)發(fā)送 11 信號(hào)時(shí)，表示 n 在 32~44 或 19~31 范圍內(nèi)，以上兩個(gè)節(jié)點(diǎn)中的任意一個(gè)已經(jīng)查表得到答案了，我們只需要往下跳 11 行，把接下來的答案送給 OUT 就行了（mov up down）。

而當(dāng)中央節(jié)點(diǎn)發(fā)送 1 信號(hào)時(shí)，表示 n 既不在 32~44 范圍內(nèi)，也不在 19~31 范圍內(nèi)，上面兩個(gè)節(jié)點(diǎn)都無能為力了，只能由我們來查表了。此時(shí)我們向下跳 1 行，檢查 n 是否大于 9，即減去?9?后（mov -9?acc, add up）是否大于 0。若滿足條件，說明 n 在 10~18 范圍內(nèi)，跳到第 9 行執(zhí)行（jgz 9）。由第 3 張表格的信息可知，10 <= n <= 18 時(shí)，向 3 號(hào)表傳入 n-9?可以得到?∑?(k=1,?n)?k 的值。此時(shí)的 acc 已經(jīng)是 n-9，所以直接將 acc 發(fā)給 3 號(hào)表（mov acc right），并將返回值發(fā)給 OUT（mov right down, jmp 1）。

當(dāng) n 不在 10~18 范圍內(nèi)時(shí)，就只剩下了最后的 1~9 范圍。由第 4 張表格的信息可知，1 <= n <= 9?時(shí)，向 4 號(hào)表傳入 n?自身可以得到?∑?(k=1,?n)?k 的值。此時(shí)我們將目光跳回第 5 行，令 acc 加回 9（add 9），將 acc 由 n-9 變回成 n 后發(fā)給 4 號(hào)表（mov acc left），并將返回值發(fā)送給 OUT（mov left down, jmp 1）。

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

581?周期的運(yùn)行時(shí)長(zhǎng)，一騎絕塵，但代價(jià)是大量的用于建表和查表的代碼行數(shù)。