深圳SHENZHENIO第23关污染监测智能窗攻略

深圳IO是一款硬核的编程游戏，有着严谨的游戏内容，那么一起来看看第23关的污染监测智能窗的攻略吧。

主界面

由于游戏过分硬核，先放个手册中的图看看冰山一角：

不过这也正对应了嵌入式开发中会遇到的海量数据手册，相当程度上还原了嵌入式日常开发的情景。

游戏中设计到部分的编程有些类似于汇编语言，这里上手还是有一些些难度的，大家请做好准备，继续直接扔核弹：

不用害怕，在游戏过程中，会逐步引导你学会使用新的指令，对于新的器件，也是随着主线的进行逐步开放的

在游戏中，你不仅可以完成指定的基本目标，还可以挑战全网玩家，看谁能达成最佳优化目标。

鱼和熊掌不可兼得，多数情况下想要达成更好的性能就要增加成本啦，不过这正是优秀的嵌入式开发人员的意义所在——比你好，还比你的便宜。

第 23 关：污染监测智能窗

关卡展示

本关要求当(包括当前时间在内的)前 8 秒内，污染监测传感器的平均值大于等于 50 时关闭窗户，平均值小于 50 时开启窗户。题目保证前 7 秒的平均值不会大于等于 50。因此问题等价于：前 8 秒内的污染值总和大于等于 400 时关闭窗户，小于 400 时开启窗户。

初版方案：

用 RAM 记录现在和过往的污染值，每一秒钟我们都统计前 8 秒的污染值总和是否小于 400，然后决定是否打开窗户就行了。由于 RAM 可以记 14 个数字，所以记住前 8 秒的污染值那是绰绰有余。电路图和代码如下：

首先我们将当前的污染值存入 RAM(mov p0 x0)，然后准备开始统计前 8 秒的污染值总和。设当前 RAM 的指针地址是 a，则我们需要统计 a-8 ~ a-1 地址范围内的污染值总和。由于读取一次 RAM 后地址会自增，所以最终地址是 a-1+1 = a 自己。我们将最终地址 a 放入 dat 寄存器(mov x1 dat)，然后将 RAM 的地址置为首地址 a-8，准备计算前 8 秒的污染值总和(mov x1 acc, sub 8, mov acc x1)。计算总和之前，我们需要将 acc 清零(mov 0 acc)。然后开始不断读 RAM，并将读到的值加到 acc 里(add x1)。每读一个值，都判定一次是否到达结束地址(teq x1 dat)。尚未到达结束地址时，跳回第 7 行继续累加(- jmp 7)，直到读完前 8 秒的污染值后，计算这些污染值的总和是否小于 400(tlt acc 400)。小于 400 时打开窗户(+ mov 100 p1)，否则关闭窗户(- mov 0 p1)。做完这些操作后，休眠一秒，进入下一个时钟周期(slp 1)。

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

利用【滑动窗口】算法提高运行效率

我们的初版算法达到了惊人的 1.5K 耗电量。这是因为我们在计算前 8 秒的污染值总和时涉及到了太多重复的计算。设 v(i) 为第 i 秒时的污染值，S(j, k) 为第 j~k 秒的污染值总和。那么，我们的初版算法里，是这样计算污染值总和的：

S(1, 8) = v(1) + v(2) + ... + v(8)

S(2, 9) = v(2) + v(3) + ... + v(9)

S(3, 10) = v(3) + v(4) + ... + v(10)

...

可以看到，每次都要读取 8 个数进行累加。如果我们使用动态计算的思维(下一个结果由上一个结果动态推导而出)，就可以大大减少计算量：

S(1, 8) = v(1) + v(2) + ... + v(8)

S(2, 9) = S(1, 8) - v(1) + v(9)，无需重复计算 v(2) + v(3) + ... + v(8)

S(3, 10) = S(2, 9) - v(2) + v(10)，无需重复计算 v(3) + v(4) + ... + v(9)

...

可以看到，改进的算法里，下一秒的污染总和，只需要在上一秒的基础上减去一个值再加上一个值就可以了，只需要读两个数字。相比于初版方案，减少了大量重复计算，效率大大提升。这种通过移动左右边界，动态计算区间和的算法就叫做【滑动窗口】算法，简称【滑窗】算法。正好这道题也是个【滑窗】问题。

改进后的电路图和代码如下：

首先我们将右边界置为 8，左边界保持为 0，视为从第 8 秒开始统计，第 0~7 秒的污染值之和为 0(mov 8 x3)。每到达新的一秒，我们将 acc 的值减去原先左边界的值(sub x0)，然后加上新值(add p0)，并将新值存入原先的右边界所指向的空间(mov p0 x2)。操作完成后，左边界和右边界会各向右移动一格。此时我们便完成了一次【滑窗】计算，acc 的值为前 8 秒内的污染值总和。判断该值是否小于 400(tlt acc 400)，小于 400 时打开窗户(+ mov 100 p1)，否则关闭窗户(- mov 0 p1)。做完这些操作后，休眠一秒，进入下一个时钟周期(slp 1)。

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

电量由 1.5K 骤降到 277，代码行数也由 13 行降到 8 行，质的飞跃!