【TIS-100 攻略】TIS-NET 第 18 关：缺失数字补全器

本文首发于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原创不易，转载请注明出处。

TIS-NET 第 18 关《缺失数字补全器》（Sequence Gap Interpolator）关卡展示

本关的 IN 会不断提供一些以 0 结尾的序列，每个序列的最小值和最大值之间缺了一个数。例如，现在你收到了 [78, 77, 74, 75, 0] 这个序列。这个序列的最小值是 74，最大值是 78。在 74~78 之间有 5 个数字，但是这个序列里却只有 4 个数字，缺失了 76。你要做的就是把这个缺失了的数字找出来并输出。

我们可以通过求和的方式来找出序列中缺失的数。设收到的序列为 s，缺失的数为 miss，最小值为 min，最大值为 max，易得：

用没有缺失任何数字的序列之和，减去缺失了一个数字的序列之和，就找到了那个缺失的数字。本题的 C 语言代码如下：

转写成的 TIS-100 代码如下：

本关虽然有两个栈，但本关没有反复读取历史数据的需求，所以两个栈完全用不上。

IN 下方的节点，收到第 1 个数后，将它分别传给左边和下面的节点（分别用来存储 min 和 ans 的值）（mov up acc, mov acc left, mov acc down）。从第 2 个数开始（mov up acc），就要判断是否收到了序列末端的 0。未收到 0 时按顺序执行，收到 0 时跳到第 9 行执行（jez 9）。尚未收到 0 时，需要给左边计算 min 的节点发送一个 1 信号，然后把当前收到的数给左边发两次，给下方计算 ans 的节点发一次（mov 1 left, mov acc left, jmp 2, mov acc left, mov acc down）。收到序列末端的 0 后，给左边发送一个 5 信号（mov 5 left），给下边发送一个 -999（mov -999 down），然后从左边接收 min，然后根据下方节点的指令，依次给下方发送 min、min+1、min+2……直到最终的 max 值（jro down, mov acc down, add 1, jmp c）。

左上角的节点就是计算序列里的最小值的，套路都很熟悉了：将右边传来的首数字放入 acc，暂时视为 min（mov right acc）。然后我们会收到两种信号（jro right）：

• 收到 1 信号时，说明尚未到达序列末端，我们向下跳 1 行，将历史最小和新的挑战值做差值运算（sub right），差值为正时，挑战者 < 历史最小，挑战成功，跳回第 1 行，将挑战者作为新的 min（jgz 1, mov right acc）；差值为 0 或负时，挑战者 >= 历史最小，挑战失败，令差值加回挑战者的值，将 min 还原成历史值（add right, jmp 2）。

• 收到 5 信号时，说明到达了序列末端。我们向下跳 5 行，将当前找到的 min 发给右边（mov acc right），然后跳回第 1 行，丢弃掉当前的 min，准备计算下一个序列的 min。

然后是中央节点。第一阶段，我们将 acc 设置为 +999 的偏置（mov 999 acc），然后上方会发来序列里的所有值，我们求出 999 - sum(s) 的值（sub up, jgz 2）。当读到了序列末端时，上方会突然发来一个 +999，这时候我们的 sub up 指令会清除原先的 +999 偏置，acc 会突然变成负数，值为 -sum(s)。

第二阶段，上方会依次将 min, min+1, min+2……的值发来，我们每发送一条 1 指令（mov 1 up），上方就会给我们发一个数，我们将收到的数加回到 acc 里（add up）。尚未加到正数时，说明刚才加上的数还不是 max，此时跳回第 4 行继续加（jlz 4）。直到 acc 变为正数后，我们就得到了当前序列里缺失的数，此时给上方发送 -11，让上方跳回第 1 行，接收下一个序列的首数字（mov -11 up），自己则是将找到的缺失数字发给下方（mov acc down）。

下方节点没啥好说的，纯粹传话（mov up down）。

点击左下角的【RUN】，稍等片刻，便会弹出结算界面：