求sumBetween函数的循环不变量——算法新手求助

云原生阿岚

2026-5-20

理解sumBetween函数的循环不变量

先把你给出的代码贴出来方便讨论：

int sumBetween (int x , int y){
    //pre-condition : x<=y
    //post : returns the sum x+(x+1)+(x+2)+.........+y
    int sum=0;
    for(int i=x; i!=y+1; i++) {
        sum+=i;
    }
}

嘿，作为算法新手能琢磨到循环不变量这一步已经超棒了！先给你吃个定心丸：你自己想到的那个循环不变量完全正确，而且它就是这个循环最合适的选择——在每次循环迭代开始前，变量sum的值等于从x到i-1的所有整数之和。

下面我拆解一下这个不变量在循环的各个阶段为什么都成立，帮你彻底吃透：

初始化阶段（循环启动前）：
此时i = x，sum = 0。按照不变量的描述，我们要算从x到i-1（也就是x到x-1）的整数和——这是一个空区间，数学上定义为空和，值就是0，和sum的初始值完全匹配，不变量成立。
迭代保持阶段：
假设某次迭代开始前，不变量是成立的（也就是当前sum确实等于x到i-1的和）。执行sum += i后，sum就变成了x到i的和；紧接着i自增1，变成i+1。这时候下一次迭代开始前，i的新值是i+1，那么i-1就是原来的i，所以sum依然等于x到(新i)-1的和，不变量继续保持成立。
循环终止阶段：
循环结束的条件是i == y+1。根据不变量，此时sum等于x到i-1（也就是x到y）的所有整数之和，完美命中函数的后置条件，这也直接证明了这个函数的逻辑是正确的。