【TIS-100 攻略】TIS-NET 第 10 关:序列众数计算器

本文首发于 B 站《TIS-100》文集(https://www.bilibili.com/read/readlist/rl626023)。原创不易,转载请注明出处。
TIS-NET 第 10 关《序列众数计算器》(Sequence Mode Calculator)关卡展示

本关的 IN 会不断给你一些以 0 结尾的序列,你需要找出序列中的众数,即出现次数最多的那个数。若有多个数的出现次数并列第一,则改为输出 0。
本关需要用到类似于计数排序的思想:每读入一个数 num,就将该数的频数 f[num] 加上 1,并和历史最大频数 maxF 比较:
若 f[num] < maxF,输出值 ans 不变;
若 f[num] = maxF,输出值 ans 归零;
若 f[num] > maxF,输出值 ans 强制更改为 num,且令 maxF 加 1。
读完序列中的所有数字后,输出 ans,并将 maxF 归零。示意图如下所示:







C 语言代码如下:
本题的输入量不会超过 5,因此 f 数组最大下标到 5 就足够了。转写成的 TIS-100 代码如下:

我们在开始分析前要初始化一个长度为 5 的 f 数组,分析结束后要将数组销毁。2 号节点干的就是这样的事:
首先用循环的方法向左上角的栈里塞入 5 个 0,分别是 f[5] ~ f[1] 的初始值(mov 5 acc)
(mov 0 up)
(sub 1)
(jnz 2)
塞完后向 3 号节点发送一个 1 的启动信号(mov 1 right)。
本轮分析完成后,2 号节点会从 3 号节点收到一个 5(mov right acc),
这时候我们再将左上角栈里的 f[1] ~ f[5] 取出并销毁(mov up nil)
(sub 1)
(jnz 7)
2 号节点就做两件事——初始化,以及销毁。然后我们来看 1 号节点。
1 号节点每从 in 收到一个数 num(mov up acc),
就将这个 num 向下传一份(mov acc down),然后判断:
如果收到的 num 是 0,说明到达了序列末端,跳回第 1 行,准备开始分析下一个序列(jez 1)。
收到的 num 不为 0 时,需要将 f[num] 加上 1,并将改写后的 f[num] 值也发给下方。我们先将 num 值复制一份到 bak 里备用(sav),
然后从左上角里弹出前 num 个数字 f[1] ~ f[num],将这些数字全部送往右上角的栈暂存(mov left right)
(sub 1)
(jnz 5)
至此,右上角的栈的栈顶便是 f[num] 的值,我们将它取出(mov right acc),
加上 1(add 1)
并发给下面后(mov acc down),
放回原处(mov acc right)。
更新完 f[num] 的值后,我们要将放在右上角栈里的 f[num] ~ f[1] 共 num 个数字放回左上角的栈里(swp)
(mov right left)
(sub 1)
(jnz d)
3 号节点的 acc 用来接收上方发来的 num,bak 用来存储众数 ans:
3 号节点首先需要等待 2 号节点完成对 f 数组的初始化过程,将 5 个 0 放入左上角的栈,并发来一个 1 后才能启动(jro left)。
启动后,我们会从 1 号节点处收到 num 的值(mov up acc),判断它是否是 0。
收到的 num 为 0 时,说明到达了序列末端,跳到第 10 行执行(jez a)。
收到的数字不为 0 时,我们先给 4 号节点发一个 3 信号(mov 3 right),
然后将上方发来的 f[num] 交给 4 号节点(mov up right),
并根据 4 号节点的反馈(jro right)执行不同的任务:当 f[num] < maxF 时,4 号节点会发来一个 -4,我们往上跳 4 行,不更新 bak 里存放的 ans 的值,直接继续接收下一个 num;
当 f[num] = maxF 时,4 号节点会发来一个 1,我们往下跳 1 行,将 bak 里的 ans 强制置零(sub acc)
当 f[num] > maxF 时,4 号节点会发来一个 2,我们往下跳 2 行,将 bak 里的 ans 更新为当前的 num 值(sav)
(jmp 2)
如此往复,直到从 1 号节点收到 0 后,我们跳到第 10 行执行。注意我上面分析 2 号节点时说的:【本轮分析完成后,2 号节点会从 3 号节点收到一个 5,这时候我们再将左上角栈里的 f[1] ~ f[5] 取出并销毁。】这时候我们自然是给 2 号节点发这个 5,让它开始清理左上角的栈(mov 5 left)。
然后我们将 bak 里的 ans 值(swp)
往下传(mov acc down),
最后给 4 号节点发一个 1 信号(mov 1 right)。
4 号节点则是用来维护实时的 maxF 的,它的 bak 用来存储实时的 maxF,acc 则是用来和发来的 f[num] 做差值运算。每次计算完成后,acc 和 bak 的值要保持一致,以便随时准备下一次差值运算。
4 号节点会从 3 号节点收到两种信号,3 信号和 1 信号(jro left)。
收到 1 信号时,说明 3 号节点已经分析完了当前序列,我们向下跳 1 行,把 acc 清零(sub acc),
然后直接跳到第 15 行(jmp f),执行 sav 指令,将表示 maxF 的 bak 清零,准备分析下一个序列里的众数。
收到 3 信号后,3 号节点会紧跟着发来当前的 f[num]。我们往下跳 3 行,将 maxF 与 f[num] 做差(sub left),并根据差值的符号选择不同的代码块执行:
差值为负时按顺序执行,差值为正时跳到第 13 行执行(jgz d),
差值为 0 时跳到第 11 行执行(jez b)。
差值为负时,说明 maxF < f[num],按照规则,此时需要更新 ans 和 maxF。因此,给 3 号节点发送 2,令其更新 ans(mov 2 left),
然后将自己的 maxF(swp)
加上 1(add 1)
并覆盖 acc(jmp f, sav)。
差值为 0 时,说明 maxF = f[num],按照规则,此时需要将 ans 归零,maxF 不变。因此,给 3 号节点发送 1,令其清零 ans(mov 1 left),
然后自己的 maxF 保持不变,并覆盖 acc(jmp e, swp, sav);
差值为正时,说明 maxF > f[num],按照规则,此时 ans 和 maxF 均不变。因此,给 3 号节点发送 -4,让其直接从 2 号节点接收下一个 num(mov -4 left),
然后自己的 maxF 保持不变,并覆盖 acc(swp)
(sav)
点击左下角的【RUN】,稍等片刻,便会弹出结算界面:
