我在读CLRS的《算法导论》。在第二章中,作者提到了“循环不变量”。什么是循环不变量?


当前回答

循环不变量是在循环执行前后为真的断言。

其他回答

简单地说,它是一个循环条件,在每次循环迭代中都为真:

for(int i=0; i<10; i++)
{ }

在这里,我们可以说i的状态是i<10并且i>=0

不变的意思是永不改变

这里循环不变量的意思是“发生在循环中的变量的变化(增加或减少)并没有改变循环条件,即条件是满足的”,因此循环不变量的概念就产生了

在这种情况下,不变量意味着在每次循环迭代的某一点上必须为真条件。

在契约编程中,不变量是在调用任何公共方法之前和之后必须为真(通过契约)的条件。

对不起,我没有评论权限。

正如你提到的@Tomas Petricek

另一个较弱的不变式也是成立的,即i >= 0 && i < 10(因为这是连续条件!)”

为什么它是循环不变量?

我希望我没有错,据我理解[1],循环不变将在循环开始时为真(初始化),它将在每次迭代(维护)之前和之后为真,它也将在循环结束后为真(终止)。但是在最后一次迭代之后,i变成了10。因此,条件i >= 0 && i < 10变为假值并终止循环。它违反了循环不变量的第三个性质(终止)。

[1] http://www.win.tue.nl/~kbuchin/teaching/JBP030/notebooks/loop-invariants.html

Loop invariant is a mathematical formula such as (x=y+1). In that example, x and y represent two variables in a loop. Considering the changing behavior of those variables throughout the execution of the code, it is almost impossible to test all possible to x and y values and see if they produce any bug. Lets say x is an integer. Integer can hold 32 bit space in the memory. If that number exceeds, buffer overflow occurs. So we need to be sure that throughout the execution of the code, it never exceeds that space. for that, we need to understand a general formula that shows the relationship between variables. After all, we just try to understand the behavior of the program.