34

Introduction to Algorithms ( http://mitpress.mit.edu/algorithms ) に見られるように、演習では次のように述べられています。

入力:配列A[1..n]と値v

出力: Index i、 whereA[i] = vまたはNILifvが見つからないA

シーケンスをスキャンして v を探す LINEAR-SEARCH の疑似コードを記述します。ループ不変式を使用して、アルゴリズムが正しいことを証明します。(ループ不変条件が 3 つの必要なプロパティ (初期化、保守、終了) を満たしていることを確認してください。)

アルゴリズムの作成に問題はありませんが、得られないのは、ループの不変条件をどのように決定できるかということです。ループ不変の概念、つまり、ループの開始前、各反復の終了/開始時に常に真であり、ループが終了しても真である条件を理解したと思います。通常はこれが目標です。たとえば、sort の挿入、 の繰り返し、jから始まる要素は常にソートされます。これは私には理にかなっています。しかし、線形検索の場合は？ループ不変条件を考えるには単純すぎるように思えます。私は何か間違ったことを理解しましたか？次のような明白なものしか考えられません（NILまたは0とnの間のいずれかです）。よろしくお願いします！j = 2A[1..j-1]

4

7 に答える 7

19

index を調べた後、まだi見つからない場合、配列の前の部分と後の部分についてv何が言えますか?vii

于 2011-04-07T17:28:13.343 に答える
8

線形検索の場合、ループ バリアントは index(output) の保存に使用されるバッキング ストアになります。

バッキング ストアに、最初は NIL に設定されているインデックスとして名前を付けます。ループ バリアントは、次の 3 つの条件に従う必要があります。

  • 初期化: この条件は、インデックス変数に当てはまります。結果の結果である可能性のある NIL が含まれているため、最初の反復の前に当てはまります。
  • メンテナンス : index は、項目 v が見つかるまで NIL を保持します。繰り返しの前と次の繰り返しの後も同様です。比較条件が成功した後、ループ内で設定されます。
  • 終了 : index には項目 v の NIL または配列インデックスが含まれます。

.

于 2016-05-05T06:02:28.070 に答える
5

ループ不変条件は

永遠に 0 <= i < k、ここで、k はループ反復変数の現在の値、A[i] != v

ループ終了時:

A[k] == v の場合、ループは終了し、k を出力します

A[k] != v かつ k + 1 == n (リストのサイズ) の場合、ループは値 nil で終了します

正しさの証明: 演習として残します

于 2011-04-07T17:37:00.880 に答える
0

私が書いた LS アルゴリズムは -

LINEARSEARCH(A, v)
  for i=0 to A.length-1
    if(A[i] == v)
      return i
  return NIL

線形検索の正確性をチェックするために、ループ不変条件について独自の仮定を作成しました。

  1. Initialisation- at i = 0 では、i = 0 で v を検索しています。

  2. 連続する反復では、i < A.length-1 まで v を探します。

  3. 終了時- i = A.length で、A.length まで v を探し続けました。

于 2016-08-10T15:42:40.413 に答える