欢迎光临散文网 会员登陆 & 注册

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

2022-11-06 15:44 作者:ココアお姉ちゃん  | 我要投稿

本文首发于 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 归零。示意图如下所示:

首先,建立一个长度和最大输入值一致的数组,用于记录每个输入的数字各出现了多少次。初始值均为 0,最大频数 maxF 也为 0
读入一个 3,令 f[3] 加上 1。此时因为 f[3] > maxF,将 ans 更新为 3,将 maxF 加上 1。
读入一个 1,令 f[1] 加上 1。此时因为 f[1] = maxF,将 ans 更新为 0,maxF 不变。
读入一个 4,令 f[4] 加上 1。此时因为 f[4] = maxF,将 ans 更新为 0,maxF 不变。由于 ans 在上一步时已经是 0,所以本步 ans 没有变化。
读入一个 1,令 f[1] 加上 1。此时因为 f[1] > maxF,将 ans 更新为 1,将 maxF 加上 1。
读入一个 5,令 f[5] 加上 1。此时因为 f[5] < maxF,maxF 和 ans 都不变。
读入一个 9,令 f[9] 加上 1。此时因为 f[9] < maxF,maxF 和 ans 都不变。至此,所有输入的数字均已读完,ans=1 即为找到的众数。

C 语言代码如下:

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

我们在开始分析前要初始化一个长度为 5 的 f 数组,分析结束后要将数组销毁。2 号节点干的就是这样的事:

  1. 首先用循环的方法向左上角的栈里塞入 5 个 0,分别是 f[5] ~ f[1] 的初始值(mov 5 acc)

  2. (mov 0 up)

  3. (sub 1)

  4. (jnz 2)

  5. 塞完后向 3 号节点发送一个 1 的启动信号(mov 1 right)。

  6. 本轮分析完成后,2 号节点会从 3 号节点收到一个 5(mov right acc),

  7. 这时候我们再将左上角栈里的 f[1] ~ f[5] 取出并销毁(mov up nil)

  8. (sub 1)

  9. (jnz 7)

2 号节点就做两件事——初始化,以及销毁。然后我们来看 1 号节点。

  1. 1 号节点每从 in 收到一个数 num(mov up acc),

  2. 就将这个 num 向下传一份(mov acc down),然后判断:

  3. 如果收到的 num 是 0,说明到达了序列末端,跳回第 1 行,准备开始分析下一个序列(jez 1)。

  4. 收到的 num 不为 0 时,需要将 f[num] 加上 1,并将改写后的 f[num] 值也发给下方。我们先将 num 值复制一份到 bak 里备用(sav),

  5. 然后从左上角里弹出前 num 个数字 f[1] ~ f[num],将这些数字全部送往右上角的栈暂存(mov left right)

  6. (sub 1)

  7. (jnz 5)

  8. 至此,右上角的栈的栈顶便是 f[num] 的值,我们将它取出(mov right acc),

  9. 加上 1(add 1)

  10. 并发给下面后(mov acc down),

  11. 放回原处(mov acc right)。

  12. 更新完 f[num] 的值后,我们要将放在右上角栈里的 f[num] ~ f[1] 共 num 个数字放回左上角的栈里(swp)

  13. (mov right left)

  14. (sub 1)

  15. (jnz d)

3 号节点的 acc 用来接收上方发来的 num,bak 用来存储众数 ans:

  1. 3 号节点首先需要等待 2 号节点完成对 f 数组的初始化过程,将 5 个 0 放入左上角的栈,并发来一个 1 后才能启动(jro left)。

  2. 启动后,我们会从 1 号节点处收到 num 的值(mov up acc),判断它是否是 0。

  3. 收到的 num 为 0 时,说明到达了序列末端,跳到第 10 行执行(jez a)。

  4. 收到的数字不为 0 时,我们先给 4 号节点发一个 3 信号(mov 3 right),

  5. 然后将上方发来的 f[num] 交给 4 号节点(mov up right),

  6. 并根据 4 号节点的反馈(jro right)执行不同的任务:当 f[num] < maxF 时,4 号节点会发来一个 -4,我们往上跳 4 行,不更新 bak 里存放的 ans 的值,直接继续接收下一个 num;

  7. 当 f[num] = maxF 时,4 号节点会发来一个 1,我们往下跳 1 行,将 bak 里的 ans 强制置零(sub acc)

  8. 当 f[num] > maxF 时,4 号节点会发来一个 2,我们往下跳 2 行,将 bak 里的 ans 更新为当前的 num 值(sav)

  9. (jmp 2)

  10. 如此往复,直到从 1 号节点收到 0 后,我们跳到第 10 行执行。注意我上面分析 2 号节点时说的:【本轮分析完成后,2 号节点会从 3 号节点收到一个 5,这时候我们再将左上角栈里的 f[1] ~ f[5] 取出并销毁。】这时候我们自然是给 2 号节点发这个 5,让它开始清理左上角的栈(mov 5 left)。

  11. 然后我们将 bak 里的 ans 值(swp)

  12. 往下传(mov acc down),

  13. 最后给 4 号节点发一个 1 信号(mov 1 right)。

4 号节点则是用来维护实时的 maxF 的,它的 bak 用来存储实时的 maxF,acc 则是用来和发来的 f[num] 做差值运算。每次计算完成后,acc 和 bak 的值要保持一致,以便随时准备下一次差值运算。

  1. 4 号节点会从 3 号节点收到两种信号,3 信号和 1 信号(jro left)。

  2. 收到 1 信号时,说明 3 号节点已经分析完了当前序列,我们向下跳 1 行,把 acc 清零(sub acc),

  3. 然后直接跳到第 15 行(jmp f),执行 sav 指令,将表示 maxF 的 bak 清零,准备分析下一个序列里的众数。

  4. 收到 3 信号后,3 号节点会紧跟着发来当前的 f[num]。我们往下跳 3 行,将 maxF 与 f[num] 做差(sub left),并根据差值的符号选择不同的代码块执行:

  5. 差值为负时按顺序执行,差值为正时跳到第 13 行执行(jgz d),

  6. 差值为 0 时跳到第 11 行执行(jez b)。

  7. 差值为负时,说明 maxF < f[num],按照规则,此时需要更新 ans 和 maxF。因此,给 3 号节点发送 2,令其更新 ans(mov 2 left),

  8. 然后将自己的 maxF(swp)

  9. 加上 1(add 1)

  10. 并覆盖 acc(jmp f, sav)。

  11. 差值为 0 时,说明 maxF = f[num],按照规则,此时需要将 ans 归零,maxF 不变。因此,给 3 号节点发送 1,令其清零 ans(mov 1 left),

  12. 然后自己的 maxF 保持不变,并覆盖 acc(jmp e, swp, sav);

  13. 差值为正时,说明 maxF > f[num],按照规则,此时 ans 和 maxF 均不变。因此,给 3 号节点发送 -4,让其直接从 2 号节点接收下一个 num(mov -4 left),

  14. 然后自己的 maxF 保持不变,并覆盖 acc(swp)

  15. (sav)

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


【TIS-100 攻略】TIS-NET 第 10 关:序列众数计算器的评论 (共 条)

分享到微博请遵守国家法律