浙江 2014 · 数学 q11

冷启动：先把框图翻译成三行字

框图看着吓人，能用的信息只有三行：

• 初值：$S=0$，$i=1$；
• 循环体：$S=2S+i$，然后 $i=i+1$；
• 退出条件：判断 $S\ge n$，成立就输出 $i$，不成立就绕回循环体。

本题 $n=50$。翻译完就可以把图合上了——剩下的全是数列的事。

两个细节要在这一步钉死，后面三条路都靠它：

1. 判断框在循环体后面。所以是「先做后判」，循环体至少跑一次；每一轮的顺序永远是「先更新 $S$，再更新 $i$，最后才判断」。
2. 循环体里 $S$ 用的是本轮的 $i$，而 $i$ 在判断之前就已经加过了。于是退出时看到的 $i$，属于「下一轮准备用的那个」，比跑过的轮数多 $1$。

把第 $k$ 轮结束时的 $S$ 记作 $S_k$，第 $k$ 轮用的正是 $i=k$，于是循环体就是一条递推：

$$S_0=0,\qquad S_k=2S_{k-1}+k\quad(k\ge 1),$$

而输出值 $=k^{*}+1$，其中 $k^{*}$ 是使 $S_k\ge 50$ 成立的最小下标。

解法一：照着框图跑五轮，把 S 和 i 摞成一张表

轮数少，直接跑。每一轮做三件事：算 $S$、加 $i$、判 $S\ge 50$。

第五轮末 $S=57\ge 50$，判断框走「是」，输出此刻的 $i$：

$$\boxed{6}$$

表里那一栏「轮末的 $i$」是这道题的全部风险所在。循环体只跑了五轮，答案却是 $6$；漏掉这一栏、直接数行数的人会写 $5$。

解法二：把循环体当递推，配两个常数凑成等比

$S_k=2S_{k-1}+k$ 是一条非齐次线性递推：齐次部分是「乘 $2$」，多出来的 $k$ 是一次的。标准动作是给它配一个一次式，让新数列变成等比。

设 $b_k=S_k+\lambda k+\mu$，要它满足 $b_k=2b_{k-1}$，即

$$S_k+\lambda k+\mu=2\bigl(S_{k-1}+\lambda(k-1)+\mu\bigr) \ \Longrightarrow\ S_k=2S_{k-1}+\lambda k+(\mu-2\lambda).$$

与 $S_k=2S_{k-1}+k$ 逐项比对，得 $\lambda=1$、$\mu-2\lambda=0$，即 $\mu=2$。于是

$$b_k=S_k+k+2,\qquad b_k=2b_{k-1},\qquad b_0=S_0+0+2=2,$$

$\{b_k\}$ 是首项 $2$、公比 $2$ 的等比数列，$b_k=2^{k+1}$，回代得通项

$$S_k=2^{\,k+1}-k-2 .$$

核对一下：$S_1=4-3=1$，$S_2=8-4=4$，$S_3=16-5=11$，$S_4=32-6=26$，$S_5=64-7=57$，与表格逐格吻合。

再解退出条件 $2^{\,k+1}-k-2\ge 50$，即 $2^{\,k+1}\ge k+52$。左边翻倍、右边只加一，最多试两个数：

$$k=4:\ 32<56;\qquad k=5:\ 64\ge 57 .$$

最小的 $k^{*}=5$。

最后一步不能省：要把下标 $k$ 换回框图里的 $i$。第 $k$ 轮的循环体先做 $S=2S+i$（这一刻 $i=k$）， 再做 $i=i+1$（$i$ 变成 $k+1$），最后才判断 $S\ge n$；条件成立时输出的就是此刻的 $i$。 所以退出那一轮的输出值是

$$i=k^{*}+1=5+1=6 .$$

$k^{*}$ 是轮数、$i$ 是计数器，两者差 $1$；停在 $k^{*}=5$ 就答错了。

通项的好处不在这一问，而在换个输入立刻能答：$n$ 变成 $500$、$5000$，手推要跑八九轮，通项只要再试一次 $2^{k+1}$。

解法三：只看增量，增量自己也是「乘 2 加 1」

不解通项也行——盯住每一轮涨了多少。记 $d_k=S_k-S_{k-1}$，两条相邻的递推相减：

$$S_{k+1}-S_k=\bigl(2S_k+k+1\bigr)-\bigl(2S_{k-1}+k\bigr)=2\bigl(S_k-S_{k-1}\bigr)+1,$$

也就是 $d_{k+1}=2d_k+1$。这是最简单的一类：两边同加 $1$ 就成等比，

$$d_{k+1}+1=2(d_k+1),\qquad d_1+1=S_1-S_0+1=2 \ \Longrightarrow\ d_k+1=2^{k},\ \ d_k=2^{k}-1 .$$

增量依次是 $1,3,7,15,31,\dots$——把表格里 $S$ 那一列的相邻差算一遍，正是这串数。再累加法回去，用等比数列前n项和公式收口：

$$S_k=\sum_{j=1}^{k}\bigl(2^{j}-1\bigr)=\bigl(2^{\,k+1}-2\bigr)-k .$$

与解法二同一条通项。$S_4=26<50\le 57=S_5$，输出 $6$。

这条路的价值是它不需要「配 $\lambda k+\mu$」这个技巧：作一次差就把带 $k$ 的非齐次项消成了常数 $1$，剩下的是最基础的「乘 $2$ 加常数」。

输出 6 的输入区间有多宽

把 $n$ 放开看会更清楚这道题在问什么。输出 $k+1$ 当且仅当 $S_{k-1}<n\le S_k$，于是

$50$ 稳稳落在 $[27,57]$ 里，离两端都远。出题人挑的是一个「不卡边界」的输入：真正卡在 $n=57$ 上时，$S\ge n$ 与 $S>n$ 两种读法就会给出 $6$ 和 $7$ 两个答案。原卷解析收口写的是「$S=57>50$」，用的是严格不等号，而框图上印的是 $S\ge n$——本题两者同真，所以没出事，但这正是这类题最爱埋的雷。

三条路怎么选

考场上就走解法一：$2^{k+1}$ 涨得飞快，五轮之内必然收口。解法二、解法三是把这道题从「算术题」升级成「数列题」的读法，也是它真正的知识落点。

一句话带走

循环体是递推，判断框是退出条件，输出的是计数器而不是轮数——$S_k=2^{k+1}-k-2$ 在 $k=5$ 首次越过 $50$，此时 $i$ 已经加成了 $6$。