我在读CLRS的《算法导论》。在第二章中,作者提到了“循环不变量”。什么是循环不变量?
当前回答
《如何思考算法》的定义,Jeff Edmonds著
循环不变式是放置在循环和循环顶部的断言 每次计算返回到循环的顶部时,这必须成立。
其他回答
《如何思考算法》的定义,Jeff Edmonds著
循环不变式是放置在循环和循环顶部的断言 每次计算返回到循环的顶部时,这必须成立。
对不起,我没有评论权限。
正如你提到的@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
It is hard to keep track of what is happening with loops. Loops which don't terminate or terminate without achieving their goal behavior is a common problem in computer programming. Loop invariants help. A loop invariant is a formal statement about the relationship between variables in your program which holds true just before the loop is ever run (establishing the invariant) and is true again at the bottom of the loop, each time through the loop (maintaining the invariant). Here is the general pattern of the use of Loop Invariants in your code:
... // the Loop Invariant must be true here while ( TEST CONDITION ) { // top of the loop ... // bottom of the loop // the Loop Invariant must be true here } // Termination + Loop Invariant = Goal ... Between the top and bottom of the loop, headway is presumably being made towards reaching the loop's goal. This might disturb (make false) the invariant. The point of Loop Invariants is the promise that the invariant will be restored before repeating the loop body each time. There are two advantages to this:
Work is not carried forward to the next pass in complicated, data dependent ways. Each pass through the loop in independent of all others, with the invariant serving to bind the passes together into a working whole. Reasoning that your loop works is reduced to reasoning that the loop invariant is restored with each pass through the loop. This breaks the complicated overall behavior of the loop into small simple steps, each which can be considered separately. The test condition of the loop is not part of the invariant. It is what makes the loop terminate. You consider separately two things: why the loop should ever terminate, and why the loop achieves its goal when it terminates. The loop will terminate if each time through the loop you move closer to satisfying the termination condition. It is often easy to assure this: e.g. stepping a counter variable by one until it reaches a fixed upper limit. Sometimes the reasoning behind termination is more difficult.
应该创建循环不变量,以便当达到终止条件时,且不变量为真,则达到目标:
不变+终止=>目标 它需要实践来创建简单而相关的不变式,这些不变式捕获了除了终止之外的所有目标实现。最好使用数学符号来表示循环不变量,但当这导致过于复杂的情况时,我们依赖于清晰的散文和常识。
在这种情况下,不变量意味着在每次循环迭代的某一点上必须为真条件。
在契约编程中,不变量是在调用任何公共方法之前和之后必须为真(通过契约)的条件。
简单地说,循环不变量是对循环的每次迭代都成立的某个谓词(条件)。例如,让我们看一个简单的For循环,它是这样的:
int j = 9;
for(int i=0; i<10; i++)
j--;
在这个例子中,i + j == 9(对于每个迭代)是正确的。一个较弱的不变式也是成立的 I >= 0 && I <= 10。