【深圳 IO 攻略】第 12 关：设备 2A27

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

关卡展示

这一关我们要做的是根据实时的 x, y 值输出映射的电源值。具体的映射规则需要参考数据手册：

不难发现，电源值 p 和 x, y 之间满足以下规律：

其中：

那么，我们用一块芯片根据 x, y 的值算 Δp 的值，另一块芯片根据 x 和 Δp 的值计算 p 的值并输出即可。代码如下：

我们说过，用连续 + 号串联的测试指令间构成【与】关系。那么我们看左边的芯片，仅当 x > 39（tgt p1 39）且 x < 80（+ tlt p1 80）且 y > 39（+ tgt p0 39）且 y < 80（+ tlt p0 80）时，Δp 才是 50（+ mov 50 x1）；以上任何一个条件不满足时，Δp 都是 0（- mov 0 x1）。

然后我们看右边的芯片。因为当 20 ≤ x < 60 时，p = 0 + Δp = Δp，所以当 x > 19（tgt p0 19）且 x < 60（+ tlt p0 60）时，直接将 Δp 原封不动地传给【电源】端口就 OK 了（+ mov x1 p1）。以上任何一个条件不满足时，都需要将 Δp 加上 30 再传给【电源】端口（- mov x1 acc, - add 30, - mov acc p1）。这里我们没有像上一关那样使用 slx 指令等待同步，是因为两块芯片很明确地每一秒钟都需要通信，并不是不确定什么时候要读，所以不需要用 slx 指令等待同步。

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

优化电量

我们知道，在【与】逻辑里，仅当所有条件都成立时，最终的逻辑值才能为真，而只要任意一个条件不成立，最终的逻辑值均为【假】。我们现在看上面的计算 Δp 值的那块芯片。如果最终 Δp 的值是 50，那么一定是经过了四次判断才确定的，这一部分的电量无论如何都省不下去。问题在于如果最终 Δp 的值是 0，那么是经过几次判断后得出的呢？1~4 次都有可能。那么，如果我们能正确调整这四个条件的判断顺序，使得芯片尽可能在早期就判断出 Δp 的值为 0，那么就可以在运行时间里大量节省判断的次数，从而达到节省电量的目的。

我们在此之前，先考虑一个简化版的问题：一个随机数生成器每秒钟都会生成一个 1~10 范围内的整数，每个数字的出现概率相等。你每秒钟都需要判断当前的随机数是否在 2~4 之间。你该如何设计算法才能让代码尽可能高效运行？

我们先考虑“先判断是否 >1，再判断是否 <5”这样的情况：

可以看到，如果“先判断是否 >1，再判断是否 <5”，那么只有 10% 的情况只判断一次，90% 的情况都是要判断两次才能得出结论的。1 秒钟的平均耗电为 1 × 10% + 2 × 90% = 1.9。那么如果我们调换一下顺序，“先判断是否 <5，再判断是否 >1”会怎样呢？

此时就不一样了，有 60% 的可能性在第一次判断时就得出了结论。此时 1 秒钟的平均耗电为：1 × 60% + 2 × 40% = 1.4，相比于上一版方案，每秒钟平均减少了 0.5 次判断。

相信聪明的你此时已经发现了规律：多个条件在一起做【与】运算时，为了提高运行效率，应当优先判断成立概率低的条件，尽最大可能在前期就筛掉不满足条件的输入量。

像上面我举的那个例子，一个 1~10 的随机数里，有 90% 的可能性 >1，有 40% 的可能性 <5。那么我们在判断的时候，就应当先判断是否 <5，这样我们就有 60% 的可能性在第一轮判断中就得出结论，和先判断是否 >1 相比，能大大提高效率。

回到我们的题目，Δp 的值是和四个条件相关的，仅当四个条件都成立时才是 50。这四个条件依次是：x > 39，x < 80，y > 39，y < 80。那么，如果 Δp 的值是 0，我们该怎么调整判断顺序，才能尽快地得出结论呢？现在我们已知 x 和 y 都在 0~100 范围内。那么，我们列出这四个条件的成立概率：

• x > 39（61 / 101 = 60.4%）

• x < 80（80 / 101 = 79.2%）

• y > 39（61 / 101 = 60.4%）

• y < 80（80 / 101 = 79.2%）

根据“优先判断成立概率低的条件”这条原则，我们应当先判断 x > 39 和 y > 39 这两个条件，再判断 x < 80 和 y < 80 这两个条件。

然后再看计算 p 值的部分。p 值仅和 x，以及刚刚计算好的，可以视为常数的 Δp 相关。仅当 x > 19 和 x < 60 同时成立时，p = Δp；任何一条不成立时，p = 30 + Δp。那么同样地，我们将这两个条件的成立概率列出来：

• x > 19（81 / 101 = 80.2%）

• x < 60（60 / 101 = 59.4%）

所以，这里我们需要先判定 x < 60 这个条件，再判定 x > 19 这个条件。综上所述，我们将代码改写成如下的样子并运行：

在我们刚才的概率统计里，x > 39 和 y > 39 的概率是一样的。以上代码中，先判断 y > 39 是尝试出来的结果，在这道题的 80 个测试样例里，先判断 y > 39 比先判断 x > 39 要省 6 格电。x < 80 和 y < 80 的先后顺序同理，也是尝试出来的结果，前者比后者省 2 格电。这些是受具体测试样例而影响的，但也侧面说明了：两个概率相等的条件的判定先后顺序，对整体电量的影响很小。

优化代码行数

将右边芯片的【与】逻辑改为【或】逻辑（即测试指令间用 - 串联），即可省掉一行代码行数，代价是耗电量会稍有增加。具体算法如下：先将 Δp 的值存入 acc，然后 x < 20 及 x > 59 有任意一条成立时，acc 在原值的基础上 +30，都不成立则 acc 维持原状。最后将 acc 送入【电源】端口。

【或】逻辑的条件书写顺序和【与】逻辑正好相反，应当先写成立概率高的条件。因为【或】逻辑只能短路得出【真】结论，所以我们应当尽快得出【真】结论。而显然，优先判断成立概率高的条件更容易快速得出【真】结论。所以这里优先判断 x > 59，再判断 x < 20。代码如下：