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;
}

2 つの不変式 (y + z および x * x) を移動できます。この例の利点は、LICM を適用した後、コードに他の最適化を適用して非常に簡単にできることです。

それについての論文/スライド/コースにはたくさんありますが、満足のいく例を見つけることができます.