【TIS-100 攻略】TIS-NET 第 1 關(guān)：序列合并器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。
恭喜你完成了 TIS-100 SEGMENT MAP 系列里的所有關(guān)卡，現(xiàn)在請點擊右上角的【TIS-100 NET DIRECTORY】按鈕，開始挑戰(zhàn)難度更大的 TIS-NET 系列關(guān)卡。
TIS-NET 第 1 關(guān)《序列合并器》（Sequence Merger）關(guān)卡展示
IN.A 和 IN.B 會不斷給你提供一些以 0 結(jié)尾的序列（兩者長度不一定相等）。你收到的兩個序列里的數(shù)字都已按從小到大的順序排好序。請你將 IN.A 和 IN.B 這兩個序列合并成一個序列，同時確保合并后的序列仍然有序。
將兩個序列里的數(shù)都放進(jìn)棧里，再使用第 21 關(guān)的做法對棧里的數(shù)字排序是一種容易想到的做法。但問題在于，本關(guān)的兩個棧相隔太遠(yuǎn)，傳話非常不便。而且這樣做也沒有利用【得到的序列已經(jīng)有序】這樣的特征。
其實，兩個有序數(shù)組合并成一個數(shù)組，是有專門的算法的，這叫做【雙指針?biāo)惴ā俊蓚€指針 i、j 一開始分別指向兩個數(shù)組的頭部，然后我們比較兩個數(shù)字的大小，選擇其中較小的一項輸出，然后指向較小項的指針向后移動，指向較大項的指針不動。中途若有一個指針指向了數(shù)組末端，那么剩下的元素就全從另一個數(shù)組里拿。如圖所示：
我們將以上算法寫成 C 語言代碼（a?和 b?數(shù)組一定以 0 結(jié)尾，表示數(shù)組的末端）：
以上的算法里，兩個數(shù)組的哨兵都是 0?？紤]到每次都是選擇兩個目標(biāo)數(shù)中的較小數(shù)，如果我們把哨兵換成一個足夠大的數(shù)（比如 999），那么當(dāng)其中一個量到達(dá)數(shù)組末端，另一個量卻沒到達(dá)時，比較大小時就一直是另一個小，我們在合并的時候就不需要特殊判定兩個指針是否指到了末端。當(dāng)兩者中的較小值都為 999 時，我們自然會知道，兩個指針都指向了末端，此時輸出最后的 0。改進(jìn)后的算法代碼如下：
現(xiàn)在我們將以上 C 語言代碼轉(zhuǎn)寫成 TIS-100 的匯編代碼，如下：
本關(guān)用到了?6?個節(jié)點，我分別用它們所在的方向（左上、右上、左、中、右、下）來指代。
左上和左下的節(jié)點分別把?IN.A 和 IN.B 提供的值發(fā)給中路靠左和中路靠右的節(jié)點（mov up down）。接下來是中路靠左的節(jié)點：
中路靠左的節(jié)點會收到左上發(fā)來的【指針 i 所指向的數(shù)】，即 a[i]，將它存入 acc（mov up acc）。
此時判斷收到的數(shù)是否為哨兵 0。若不是哨兵?0，跳到第 4 行執(zhí)行（jnz 4），
否則令 acc 加上 999，將哨兵 0 變?yōu)樯诒?999（add 999）。
到了第 4 行后，左節(jié)點會將 a[i] 的值發(fā)給中央節(jié)點（mov acc right），
然后聽從中央節(jié)點的指令（jro right）。中央節(jié)點發(fā)送 -1 時，表示保留住當(dāng)前的 a[i]，指針 i 不向后移動，那么我們就跳回第 4 行，繼續(xù)向中央節(jié)點發(fā)送當(dāng)前的 a[i]；而當(dāng)中央節(jié)點發(fā)送 -4 時，表示丟棄掉當(dāng)前的 a[i]，指針 i 向后移動，那么我們就跳回第 1 行，從左上節(jié)點接收下一個?a[i]。
接下來看中路靠右的節(jié)點：
中路靠右的節(jié)點會收到右上發(fā)來的【指針 j 所指向的數(shù)】，即 b[j]，將它存入 acc（mov up acc）。
此時判斷收到的數(shù)是否為哨兵 0。若不是哨兵 0，跳到第 4 行執(zhí)行（jnz 4），
否則令 acc 加上 999，將哨兵 0 變?yōu)樯诒?999（add 999）。
到了第 4 行后，右節(jié)點會將 b[j] 的值向中央節(jié)點發(fā)兩遍（mov acc left）
（mov acc left）。我們在之前的攻略里反復(fù)強調(diào)了：取出兩者中的較?。^大值時，其中一方必然要將自己的數(shù)提供兩遍。我的代碼里選擇了把 b[j] 提供兩遍，其實改為把 a[i] 提供兩遍的話，道理也是一樣的。
把 b[j] 發(fā)送兩遍后，右節(jié)點開始聽從中央節(jié)點的指令（jro left）。中央節(jié)點發(fā)送 -2 時，表示保留住當(dāng)前的 b[j]，指針 j 不向后移動，那么我們就跳回第 4?行，繼續(xù)向中央節(jié)點發(fā)送當(dāng)前的 b[j]；而當(dāng)中央節(jié)點發(fā)送 -5 時，表示丟棄掉當(dāng)前的 b[j]，指針 j 向后移動，那么我們就跳回第 1 行，從右上節(jié)點接收下一個 b[j]。
中央節(jié)點是算法的核心部分。
首先我們計算 a[i]?和 b[j] 的差值（mov left acc）
（sub right）
差值大于 0 時，跳到第 11 行執(zhí)行（jgz b）。
那么第 4 行僅當(dāng)差值小于等于 0 時能執(zhí)行到。差值小于等于?0 時，我們肯定是輸出 a[i] 并令指針 i 后移。首先必然給左邊節(jié)點發(fā)送 -4，讓左邊節(jié)點丟棄掉當(dāng)前的 a[i]（mov -4 left）。
然后我們注意到，中央節(jié)點的 acc 的值是 a[i] - b[j] 的值，此時我們加回右邊節(jié)點第二次提供的 b[j]，讓 acc 變成 a[i] - b[j] + b[j] = a[i]（add right）。
到了這一步，我們還不能直接輸出這個值，我們需要進(jìn)一步判定 a[i] 是不是哨兵 999。因此我們再將 acc 減去 999（sub 999）并判定 acc 是否變成了 0。
如果變成了 0，說明 i、j 指針都指向了各自的末端，右邊節(jié)點自然也要把當(dāng)前的 b[j] 給丟棄掉。acc 為 0 時，我們空降到第 13 行，給右邊節(jié)點發(fā)送 -5，讓右邊節(jié)點丟棄掉當(dāng)前的 b[j]，并將最后的 0 往下發(fā)（jez d, mov -5 right, mov acc down）。
acc 不為 0 時，說明 i 指針尚未到達(dá) a 數(shù)組的末端，a[i] 并不是哨兵 999。這時候只有 i 指針向后移動，j 指針不變，我們按照規(guī)則，向右邊節(jié)點發(fā)送 -2，令右邊節(jié)點保持當(dāng)前的 b[j] 不動（mov -2 right）。
接著我們將 acc 加回一個 999，得到原始的 a[i] 值（add 999），
然后跳過第 11~13 行的互斥邏輯，直接空降到第 14 行，將得到的 a[i] 值往下發(fā)（jmp e, mov acc down）。
第 11~13 行僅當(dāng) a[i] - b[j] 的差值大于 0 時才能執(zhí)行到。差值大于 0 時，說明 b[j] 比 a[i] 小，那么當(dāng)前項我們自然是輸出較小的 b[j]，并令 j 指針向后移動。我們從右邊節(jié)點拿到第二次提供的 b[j]，放入 acc 暫存（mov right?acc）。
接下來，i 指針不動，按照規(guī)則，向左邊節(jié)點發(fā)送 -1，令左邊節(jié)點保持當(dāng)前的 a[i] 不動（mov -1 left）；
j 指針需要后移一格，按照規(guī)則，向右邊節(jié)點發(fā)送 -5，令右邊節(jié)點丟棄掉當(dāng)前的 b[j]（mov -5 right）。
最后，我們將 acc 中的值發(fā)給下方節(jié)點（mov acc down）。
下方的節(jié)點沒啥好說的，老老實實把中央節(jié)點傳來的數(shù)送給 OUT.S 端口就 OK 了（mov up down）。
點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
