loops - 使用循环不变量的复杂示例

Question

任何人都可以使用示例提供一个复杂的示例，loop invariant例如sum(int n)如此微不足道以至于无法显示loop invariant. 我想要一个不那么明显的例子，我们可以使用类似的方法loop invariant来解决它。

Answer 1

维基百科的例子非常好：

for (int i = 0; i < n; i++) {
    x = y + z;
    a[i] = 6 * i + x * x;
}

可以移动两个不变量（y + z 和 x * x）。这个例子的好处是，在应用了 LCM 之后，你可以对代码进行其他优化，从而变得非常容易。

关于这方面的论文/幻灯片/课程有很多，你肯定能找到一个令人满意的例子。