【TIS-100 攻略】TIS-NET 第 2 关：数列求和计算器

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

TIS-NET 第 2 关《数列求和计算器》（Integer Series Calculator）关卡展示

本关的 IN 会提供给你一些数字，每收到一个数字，就输出 1 + 2 + ... + IN 之和。

相信闯关到这一步的你，做个累加器已经绰绰有余了吧：

上方节点将 IN 里的值传给中央节点。

中央节点将 IN 到 1 的值依次传给下方节点，最后传一个 999。

下方节点将 acc 初始化为 -999 的偏置，并从上方接收数字，将收到的数全部累加起来，当 acc 突然变成正数时，输出答案。

都是老套路了。我们点击左下角的【RUN】运行程序：

使用【查表法】提高运行速度

如果这篇攻略到此结束了，那也太没劲了。这里我们再设计一个能显著提高运行速度的解决方案。

本关要求的是 1 + 2 + ... + n 之和。根据等差数列求和公式（高斯公式）

可得，当 n = 44 时，∑ (k=1, n) k = 44 × 45 / 2 = 990；而当 n = 45 时，∑ (k=1, n) k = 45 × 46 / 2 = 1035。因此，使得结果不超过 999 的最大 n 为 44。也就是说我们从 IN 里收到的数字只有 1~44 这几种，虽说 TIS-100 里没有提供乘法指令，但我们完全可以用查表的方式获得这 44 种答案中的一种，而不需要刻意去算出每一个答案。本关需要使用 4 个节点（即 4 张表）来存储 n = 1~44 时对应的答案。查表法的代码如下：

右边的三个节点，以及左下角的节点堆满了密密麻麻的数字，它们分别是 1~4 号表。

右上角的 1 号表存储了 n 为 32~44 时 ∑ (k=1, n) k 的值。当 32 <= n <= 44 时，你需要向 1 号表传入 n-31 的值，将 32~44 映射为 1~13，利用 jro 指令跳转到对应的位置去执行，从而得到答案。传入的参数与答案的对应关系如下表所示：

中间靠右的 2 号表存储了 n 为 19~31 时 ∑ (k=1, n) k 的值。当 19 <= n <= 31 时，你需要向 2 号表传入 n-18 的值，将 19~31 映射为 1~13，利用 jro 指令跳转到对应的位置去执行，从而得到答案。传入的参数与答案的对应关系如下表所示：

右下角的 3 号表存储了 n 为 9~18 时 ∑ (k=1, n) k 的值。当 10 <= n <= 18 时，你需要向 3 号表传入 n-9 的值，将 10~18 映射为 1~9，利用 jro 指令跳转到对应的位置去执行，从而得到答案。传入的参数与答案的对应关系如下表所示：

左下角的 4 号表存储了 n 为 1~9 时 ∑ (k=1, n) k 的值。当 1 <= n <= 9 时，你需要向 4 号表传入 n 的值，利用 jro 指令跳转到对应的位置去执行，从而得到答案。传入的参数与答案的对应关系如下表所示：

位于第 2 列的上、中、下三个节点是用来对四个表发出查表指令的。上方节点检查 n 是否大于 31，即减去 31 后（mov -31 acc, add up）是否大于 0。若满足条件，说明 n 在 32~44 范围内，跳到第 8 行执行（jgz 8）。由第 1 张表格的信息可知，32 <= n <= 44 时，向 1 号表传入 n-31 可以得到 ∑ (k=1, n) k 的值。此时的 acc 已经是 n-31，所以直接将 acc 发给 1 号表（mov acc right），然后给中央节点发送一个 12 信号（mov 12 down），再将 1 号表发来的返回值传给中央节点（mov right down）。当 n 不在 32~44 范围内时，上方节点是无能为力的。此时我们将目光跳回到第 4 行，令 acc 加回 31（add 31），将 acc 由 n-31 变回成 n 后，给中央节点发一个 1 信号（mov 1 down），再将 n 值交给中央节点处理（mov acc down, jmp 1）。

中央节点首先监听上方节点的信号（jro up）。上方节点发送 12 信号时，表示 n 在 32~44 范围内，紧接着它会把答案也一并发来。这时候我们向下跳 12 行，给下方节点发送一个 11 信号（mov 11 down），再将答案向下发（mov up down）就完事了，我们不需要再继续查表。

而当上方节点发送 1 信号时，表示 n 不在 32~44 范围内，需要由我们来进一步处理。此时我们向下跳 1 行，检查 n 是否大于 18，即减去 18 后（mov -18 acc, add up）是否大于 0。若满足条件，说明 n 在 19~31 范围内，跳到第 9 行执行（jgz 9）。由第 2 张表格的信息可知，19 <= n <= 31 时，向 2 号表传入 n-18 可以得到 ∑ (k=1, n) k 的值。此时的 acc 已经是 n-18，所以直接将 acc 发给 2 号表（mov acc right），然后给下方节点发送一个 11 信号（mov 11 down），再将 2 号表发来的返回值传给下方节点（mov right down, jmp 1）。当 n 不在 19~31 范围内时，中央节点也是无能为力的。此时我们将目光跳回第 5 行，令 acc 加回 18（add 18），将 acc 由 n-18 变回成 n 后，给下方节点发一个 1 信号（mov 1 down），再将 n 值交给下方节点处理（mov acc down, jmp 1）。

下方节点首先监听中央节点的信号（jro up）。中央节点发送 11 信号时，表示 n 在 32~44 或 19~31 范围内，以上两个节点中的任意一个已经查表得到答案了，我们只需要往下跳 11 行，把接下来的答案送给 OUT 就行了（mov up down）。

而当中央节点发送 1 信号时，表示 n 既不在 32~44 范围内，也不在 19~31 范围内，上面两个节点都无能为力了，只能由我们来查表了。此时我们向下跳 1 行，检查 n 是否大于 9，即减去 9 后（mov -9 acc, add up）是否大于 0。若满足条件，说明 n 在 10~18 范围内，跳到第 9 行执行（jgz 9）。由第 3 张表格的信息可知，10 <= n <= 18 时，向 3 号表传入 n-9 可以得到 ∑ (k=1, n) k 的值。此时的 acc 已经是 n-9，所以直接将 acc 发给 3 号表（mov acc right），并将返回值发给 OUT（mov right down, jmp 1）。

当 n 不在 10~18 范围内时，就只剩下了最后的 1~9 范围。由第 4 张表格的信息可知，1 <= n <= 9 时，向 4 号表传入 n 自身可以得到 ∑ (k=1, n) k 的值。此时我们将目光跳回第 5 行，令 acc 加回 9（add 9），将 acc 由 n-9 变回成 n 后发给 4 号表（mov acc left），并将返回值发送给 OUT（mov left down, jmp 1）。

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

581 周期的运行时长，一骑绝尘，但代价是大量的用于建表和查表的代码行数。