找循环不变式

解题套路

不变式是一句只含循环变量的等式（或不等式），它在每次控制流经过同一个位置时都成立。 框图题里那个位置通常就选判断框之前——因为退出恰好发生在那里，不变式与退出条件一联立，答案就掉出来。

四步：

1. 翻译框图：写清初值、循环体的赋值次序、判断框的位置与条件。判断框在循环体之后是「先做后判」， 在循环体之前是「先判再做」——这一条决定循环体跑几次，不能含糊。
2. 跑两三轮，猜形状。把每轮的 $(\text{累积量},\ \text{计数器})$ 摞成一张小表，盯着同一行里两个量的关系 （不是盯累积量自己的规律）。例如 $(1,2),(\frac12,3),(\frac16,4)$ → 猜 $T=\frac{1}{(i-1)!}$。
3. 归纳一步：假设进入循环体前不变式成立，把循环体的赋值按框图的次序代一遍， 验证出来的还是同一句话。这一步是全部的证明，只需要做一次。
4. 代退出状态：由判断框解出退出瞬间计数器的值，代进不变式。

为什么它比逐轮模拟强

• 轮数无关。判断框的门槛从 $5$ 改成 $2012$，前三步一个字不用改，第四步换个数。
• 不怕算错一步。逐轮模拟里第三轮抄错，后面全废且没有交叉验证；不变式只有一步代数， 而且可以拿手推的头两轮来复核。
• 它顺手回答「输出的是谁」。不变式里同时含累积量与计数器，两者的错位关系写在等式里， 不用另外掰扯「跑了几轮」和「$i$ 现在是几」。

猜形状的两个惯用切口

• 累积量只被乘 / 除（$T=T\cdot i$、$T=\frac{T}{i}$）→ 猜阶乘型：$T=T_0\cdot(i-1)!$ 或 $T=\frac{T_0}{(i-1)!}$。
• 累积量被「乘常数再加计数器」（$S=2S+i$）→ 不变式一般不是初等闭式， 此时退回递推去做（构造辅助数列之类），别硬猜。

不变式猜不出来不丢人：它是加速器，不是必经之路。头两轮就能看出形状才用它。

一个提醒

不变式成立的位置要说清楚。同一句话在「循环体前」成立、在「循环体后」通常就不成立 （差的正是这一轮的赋值）。写不变式时把位置写在句子里——「每次走到判断框时」—— 比只写等式安全得多；位置错一格，代入退出条件时就会差一轮。