我需要用给定的规范构造和证明一个循环不变量:
{n > 0} P {q = | {j: a[j]=x and 0 <= j < n} |}
其中|A| 是集合 A 的元素数。这意味着q等于数组a中等于x的元素数。
代码P指定为:
{
int i = 0, q = 0;
while (i != n){
if (a[i] == x)
q = q + 1;
i = i + 1;
}
我知道循环不变量必须是真的:
- 在循环开始之前
- 在循环的每次迭代之前
- 循环结束后
但我不知道如何找到正确的循环不变量,这将允许我在之后显示 P 的部分正确性。我已经尝试查看循环的每一次迭代以及随机n、x和a[0...n-1] 的变量,以查看在循环工作时哪些组合的值是恒定的,但这没有帮助。