浙江 2009 · 数学 q06

冷启动：先把框图翻译成三行字，然后就可以不看图了

这类题的全部难度都在「读图」上。读完一张框图，手里应该只剩三行字：

• 初值：$k=0$，$S=0$；
• 循环体：$S=S+2^{S}$，然后 $k=k+1$；
• 判断框：写着 $S<100$，位置在循环体之前——成立走「是」，进循环体跑一轮再绕回来重判；不成立走「否」，输出 $k$，结束。

三行字里有三件事必须当场读死，读错一件，答案就差一位：

1. 判断框在循环体前面，所以是「先判再做」：条件一上来就不成立的话，循环体一轮都不跑。这道题里初值 $S=0<100$ 成立，所以至少跑一轮。
2. 循环体里两条赋值互不牵连：$S$ 的更新不用 $k$，$k$ 的更新不用 $S$。所以这道题在「先更新谁」上很宽容——换成别的题就未必了。
3. 输出的是 $k$ 不是 $S$。$S$ 涨到四位数，而 $k$ 只从 $0$ 数到几。

看一眼选项：$4$、$5$、$6$、$7$，两两只差 $1$。这不是巧合——出题人就是冲着「判断了几次」与「跑了几轮」、「跳出的那一轮算不算」这两处来的。所以下面每条解法都会把「第几轮」这件事写得明明白白。

解法一：照框图逐轮跑一遍——每一轮写成一行

轮数这么少，没有比老老实实跑一遍更快的路。要点只有一条：处理框里的 $S=S+2^{S}$ 是「把右边算出来的数装进 $S$」，右边两个 $S$ 用的都是这一轮进来时的旧值。把「进来时的 $S$」单独列一栏，这一条就不会读歪。

第 5 次走到判断框时 $S=2059$，$2059<100$ 不成立，于是一步都没再进循环体，$k$ 就停在 $4$。

答案 A。

三个错项分别是怎么来的，值得各看一眼。

• 选 B（$5$）：多半是把「判断框一共经过了 5 次」记成了「循环体跑了 5 轮」。判断次数总比轮数多一次——最后那次判断正是为了让它跳出去的，那一次并没有跑循环体。
• 选 C（$6$）：常见于把 $2^{11}$ 记成 $2^{11}=22$ 之类的粗错，或者干脆没注意到第 4 轮一步就冲过了 $100$，又往下多凑了两轮。
• 选 D（$7$）：往往是把 $S=S+2^{S}$ 读成了 $S=S+2S$（也就是每轮翻三倍），$0,0,0,\dots$ 卡住或者涨得太慢，只好一路凑数。

顺带说清「$k$ 为什么这次恰好等于轮数」。 这不是通例，是这道题的三个条件凑出来的：$k$ 初值取了 $0$、$k$ 的加一写在循环体里、判断框又摆在循环体之前。三件事任改一件，$k$ 与轮数就会差开——把初值改成 $k=1$，输出就是 $5$；把判断框挪到循环体之后，第 4 轮跑完再判，输出还是 $4$，但「至少跑一轮」的保证就从条件变成了结构。

解法二：把循环体读成一条递推——先证有去无回，再找第一个越线的下标

逐轮跑的麻烦在于每一轮都要回头看一眼判断框。其实可以先把判断框搁一边，只跟着 $S$ 走，最后一次性算账。

① 写成递推。 记第 $n$ 轮结束时 $S$ 的值为 $S_{n}$（约定 $S_{0}=0$ 是进循环之前的初值），循环体给出

同时 $k$ 从 $0$ 起、每轮加一，所以第 $n$ 轮结束时 $k=n$。于是「输出多少」这个问题变成「跑到第几轮停」。

② 证明「有去无回」。 对任意实数 $S$ 都有 $2^{S}>0$，所以

这条数列严格递增。既然严格递增，那么一旦某个 $S_{N}\geqslant 100$，往后的 $S_{N+1},S_{N+2},\dots$ 只会更大，再也回不到 $<100$。

这一句是这条路的关键：它保证了退出只会发生一次，而且恰好发生在第一个满足 $S_{N}\geqslant 100$ 的下标 $N$ 处。不必再逐轮去确认「会不会又绕回来」。

③ 找那个 $N$。 只要把数列算到第一次越线为止：

$S_{3}=11<100$，而 $S_{4}=2059\geqslant 100$，所以 $N=4$，输出 $k=N=4$。

答案 A。

为什么四轮就够，其实一眼能看出来。 当 $S$ 涨到 $11$ 时，这一轮要加上去的是 $2^{11}=2048$——已经是 $100$ 的二十倍。也就是说 $S$ 一旦进到两位数，下一步必定一口气冲过任何三位数的关卡。这条数列不是「稳稳地涨」，是每一轮的增量都由当前值指数式地放大，所以从 $11$ 到 $2059$ 只需要一步。反过来看：把关卡 $100$ 换成 $1000$、换成 $2000$，答案统统还是 $4$；要想让它多跑一轮，关卡得抬到 $2059$ 以上才行。

这条路什么时候比解法一强。 轮数一多，逐轮列表就开始出错；而「写成递推 + 严格递增 + 找第一个越线的下标」这一套与轮数多少无关。判断框的条件换成 $S\leqslant 100$、换成 $S<M$，甚至循环体换成别的严格增量，整套话一字不改。

解法三：只跟 $S$——用一句循环不变式把 $k$ 一次读出来

上面两条都在同时盯着 $S$ 与 $k$ 两个变量。其实 $k$ 完全是个旁观者：它不参与判断，也不参与 $S$ 的更新，只是在数数。既然如此，就把它数的那件事明确写出来，然后整道题只剩一个变量。

① 写下不变式。 取的位置是判断框之前（退出恰好发生在这里）：

每次控制流走到判断框时，$k$ 的值等于已经跑完的循环体轮数。

② 一步归纳证掉它。

• 初次到达：还没跑过任何一轮，已跑轮数为 $0$；而初值正是 $k=0$。成立。
• 保持：设某次到达判断框时已跑 $m$ 轮且 $k=m$。若条件成立，走「是」进循环体，其中 $k=k+1$ 把 $k$ 变成 $m+1$；跑完这一轮后已跑轮数也变成 $m+1$，控制流回到判断框。两边同时加一，等式照旧成立。

归纳完成——注意这个证明一次就够，与循环跑 $4$ 轮还是 $10^{6}$ 轮无关。

③ 只跟 $S$，数它改了几次。 把 $k$ 丢开，$S$ 的轨迹是

从初值开始一共改了 4 次，第 4 次之后 $S=2059$ 使判断条件失效、退出。也就是说退出时已跑 $4$ 轮。

④ 代退出状态。 把「已跑 $4$ 轮」代进不变式：输出的 $k=4$。

答案 A。

这一绕值不值。 对这道题而言，解法一更快；这条路真正的价值在于它把「$k$ 等于几」这件事从凭感觉变成了有依据。四个选项 $4,5,6,7$ 全是差一位的陷阱，而差一位恰恰来自三处可调的设定：$k$ 的初值、$k$ 的加一写在循环体的哪一步、判断框摆在循环体之前还是之后。把不变式写出来，这三处就被逼着一次性交代清楚：

• 初值改成 $k=1$ → 不变式变成「$k=$ 已跑轮数 $+1$」→ 输出 $5$；
• $k=k+1$ 挪到 $S=S+2^{S}$ 之前 → 因为两条赋值互不牵连，不变式不变 → 输出仍是 $4$；
• 判断框挪到循环体之后（先做后判）→ 循环体至少跑一轮，不变式在「判断框之前」这个位置上仍是「$k=$ 已跑轮数」→ 本题输出仍是 $4$，但如果初值改成 $S=200$，先判再做会一轮不跑输出 $0$，先做后判则会跑一轮输出 $1$。

换个关卡试试，检验这套话是不是真站得住。 把判断条件里的 $100$ 换成 $2059$：第 4 轮末 $S=2059$，而 $2059<2059$ 不成立，仍是跑完 4 轮就退出，输出 $4$。再换成 $2060$：$2059<2060$ 成立，于是第 5 轮跑起来，$S$ 变成天文数字 $2059+2^{2059}$，$k=5$，下一次判断必然失败，输出 $5$。两次改动都没有重跑归纳，只是把退出状态换了一下——这正是不变式想买到的东西。