1

我试图在以下代码中找到循环不变量：

查找最接近的对 Iter(A) ：

# Precondition: A is a non-empty list of 2D points and len(A) > 1. 

# Postcondition: Returns a pair of points which are the two closest points in A.
    min = infinity
    p = -1
    q = -1
    for i = 0,...,len(A) - 1:`=
        for j = i + 1,...,len(A) - 1:
             if Distance(A[i],A[j]) < min:
                 min = Distance(A[i],A[j])
                 p = i
                 q = j
    return (A[p],A[q])

我认为循环不变量是 min = Distance(A[i],A[j]) 所以 A 中最近的点是 A[p] 和 a[q] 。我试图证明程序的正确性。在这里，我想通过让 i 成为一些常数来证明内循环，然后一旦我证明了内循环，就用它的循环不变量替换它并证明外循环。顺便说一句，这是家庭作业。任何帮助都感激不尽。

4

1 回答 1

0

我不确定我是否完全理解用循环不变量替换内部循环的意思。循环不变量是在循环之前和循环的每次迭代（包括最后一个）之后都成立的条件。
话虽如此，我不想破坏你的功课，所以我会尽力帮助你，但不会给出太多答案。让我试试：

您的算法中有三个变量具有非常重要的值（min和p）q。当算法遍历每一对点时，您应该问自己这些值的真实情况是什么(A[i], A[j])？

在一个更简单的示例中：如果您正在设计一个算法来对列表中的值求和，您将创建一个sum在循环之前调用的变量并将0分配给它。然后，您将通过循环将元素一一相加，然后返回变量sum。
由于该变量确实保存了循环中“看到”的每个元素的总和，并且由于在主循环之后算法将“看到”列表中的每个元素，因此该sum变量必然保存所有值的总和名单。在这种情况下，循环不变量将是：该sum变量保存到目前为止“看到”的每个元素的总和。

祝你的家庭作业好运！

于 2013-11-11T05:00:26.170 回答