1

線形検索ループの擬似コード:

for j = 1 to A.length 
   if(A[j] = v) 
      return j;
return NIL

私が書いたループ不変式：

for ループの各反復の開始時に、jはA[j-1]がvと等しくない場所の次のインデックスです。

初期化:

jが1の場合、それがA.lengthより小さいかどうかをチェックする前は、前のインデックスは0です。この場合、 A[0 ]はvと等しくありません。これは、このコンテキストではA[0]が存在しないためです。

メンテナンス：

A[j]がvに等しい場合、ループは終了します。つまり、次の反復がないということです。ただし、 vと等しくない場合は、ループの不変条件を維持しながら、ループの次の反復が実行されます。

終了：

for ループが終了する条件は、jがA.length より大きいか、vがA[j]に等しいことです。ループの反復ごとにjが1ずつ増えるため、 jがA.lengthよりも大きくなるまで、 A のすべての要素をvに対してチェックしました。したがって、アルゴリズムは正しいです。vがA[j]に等しい場合、検索していた要素が見つかったことを意味します。したがって、アルゴリズムは正しいです。

これらは正しいですか？

4

1 に答える 1

2

悪くはありませんが、いくつかの改善を加えることができます。

ループ不変: "next after where..." 言語はぎこちなく、アルゴリズムが正しいことの証明には使用しないため、維持する理由はありません。「各反復の開始時に、A[i] == v となるような i < j は存在しません」。

メンテナンス: A[j] != v の場合、ループは継続します。A[i] == v かつ A[j]!=v となるような i < j は存在しないため、次も存在しません。 i <= j で、A[i] == v であり、ループ不変条件は j の次に大きい値に対して保持されます。

次に、終了条件で使用できます。配列内で v が見つかり、そのインデックスが返されると、ループは早期に終了します。それ以外の場合、ループ不変式は j == length+1 に対して成り立ち、A[i]==v となる i <= length は存在しない、つまり v が配列に出現しないことが知られています。

于 2016-08-30T04:01:31.683 に答える