什么是循环不变？ [英] What is a loop invariant?

问题描述

我正在阅读算法简介CLRS。作者正在谈论循环不变量，在第2章（插入排序）中。我不知道这是什么意思。

解决方案

简单来说，循环不变量是一些谓词（条件）这适用于循环的每次迭代。例如，我们来看看一个简单的 $ 循环，如下所示：

  int j = 9; （int i = 0; i< 10; i ++）
 j--; 
  

在这个例子中，这是真的（对于每一个迭代）， i + j == 9 。一个较弱的不变量也是如此，
i> = 0&& i< 10 （因为这是连续条件！）或 j< = 9&& j> = 0 。

I'm reading "Introduction to Algorithm" CLRS. and the authors are talking about loop invariants, in chapter 2 (Insertion Sort). I don't have any idea of what it means.

解决方案

In simple words, a loop invariant is some predicate (condition) that holds for every iteration of the loop. For example, let's look at a simple for loop that looks like this:

int j = 9;
for(int i=0; i<10; i++)  
  j--;

In this example it is true (for every iteration) that i + j == 9. A weaker invariant that is also true is that i >= 0 && i < 10 (because this is the continuation condition!) or that j <= 9 && j >= 0.

这篇关于什么是循环不变？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！