寻找循环不变量 - Hoare Triple

Question

从下面的代码中，我需要deduce/choose一个循环不变量。

(|true|)
x = 0 ;
s = 0 ;
while ( x <= n ) {
    s = s + x ;
    x = x + 1 ;
}
(|s = n(n + 1)/2|)

给出的解决方案是

s = (x-1)*x/2 ∧ (x ≤ n +1)

我不太明白它是如何达到上面的解决方案的。

请帮助我如何从代码中推导出这样的解决方案或其他循环不变式。

Answer 1

鉴于不变量，您可以轻松地在循环之前、之中和之后检查它是否为真（是的，将 1 到 n 的整数相加得到 (n+1)*n/2 -见 triangular numbers ）。由于它涵盖了循环中的所有相关变量（x 和 s），并且无法进一步细化（好吧，你可以添加 ^ x >= 0） , 它确实不变量。

要自己推导，恐怕需要事先了解三角数（或二分之一平方数）公式。您当然可以为该部分写出 s = sum of integers from 1 to x ，而我个人会将其视为有效的不变量。 x <= n+1这部分比较简单。

外行寻找不变量的方法是尝试写出循环变量在循环内的生命周期内所做的事情：

s 始终保存最大为 x
x 遍历从 0 到 n 的整数，包括在内

然后用数学写出来。

寻找循环不变量 - Hoare Triple

Finding a loop invariant - Hoare Triple

logic

while-loop

predicates

hoare-logic

loop-invariant