algorithm - 循环不变并用于解决算法？

Question

因此，如果我有以下代码：

public int sumSquares(int n){
   int sum = 0;
   for(int i = 1; i <=n; i++){
      sum += i*i;
   }
   return sum;
}

我现在必须找到一个循环不变量。有人告诉我，对于这样的循环，Y = i^2 的不变量被认为是循环不变量，但是我不知道我是否知道如何证明它是循环不变量。因为 Y 只是某物，所以在循环之前、期间和之后它总是正确的，因为它是 i*i 是什么......这是它是不变量的有效证明吗？

此外，在用不变量证明算法时，是否正确说 sum = i*i 的从 1 到 n 的总和（或 Y，循环不变量）= n(n+1)(2n+1 )/6

然后用归纳法证明那是正确的？是否正确使用循环不变量来证明算法？

希望得到一些帮助:)

score 1 · Accepted Answer

不变量应该是，在循环的入口处，对于任何i，

sum = 0 + 1*1 + 2*2 + ... + (i-1)*(i-1)

上述主张可以通过归纳来证明。设sum为循环开始的变量，循环sum'结束的变量，则：

sum' = sum + i*i = 0 + 1*1 + ... + i*i

这允许您使用这样一个事实，此外，当循环终止i=n+1时，当程序终止时，您会得到：

sum = 0 + 1*1 + ... + n*n

1 回答 1