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])

ループの不変条件は mi​​n = Distance(A[i],A[j]) なので、 A の最も近い点は A[p] と a[q] だと思います。プログラムの正しさを示そうとしています。ここでは、i を定数にして内側のループを証明したいと思います。内側のループを証明したら、それをループ不変式に置き換えて、外側のループを証明します。ちなみに宿題です。どんな助けでも大歓迎です。

4

1 に答える 1

0

内側のループをそのループ不変式に置き換えることの意味を完全に理解しているかどうかはわかりません。ループ不変条件は、ループの前とループの各反復 (最後の反復を含む) の後に保持される条件です。
そうは言っても、あなたの宿題を台無しにしたくないので、答えをあまり教えずにあなたを助けるために最善を尽くします. 私が試してみましょう：

アルゴリズムには、非常に重要な値を保持する 3 つの変数 ( min、pおよびq) があります。アルゴリズムがポイントの各ペアを通過するときに、これらの値について何が正しいかを自問する必要があります(A[i], A[j])。

より単純な例では、リスト内の値を合計するアルゴリズムを設計している場合sum、ループの前に呼び出される変数を作成し、それに0を割り当てます。次に、ループを介して要素を 1 つずつ合計し、変数を返しますsum。
この変数はループ内で「見られる」すべての要素の合計を保持するのは事実であり、メイン ループの後、アルゴリズムはリスト内のすべての要素を「見た」ため、sum変数は必然的にすべての値の合計を保持します。リスト。この場合、ループの不変式は次のようになります。sum変数は、これまでに「見た」すべての要素の合計を保持します。

宿題頑張ってください！

于 2013-11-11T05:00:26.170 に答える