0

私は現在、ループの不変条件を研究していますが、線形探索アルゴリズムの不変条件の選択に問題があります。

Inpput: A[1 ... n] of integers, k an integer value
Output: true if k belongs to A[1 ... n] false otherwise

LSearch(A,k)
i := 1
found := false
 WHILE i<=n AND found=false DO
   IF A[i] = k THEN
     found := true
   i:=i+1
return found

私が選んだ主張は次のとおりです。

  • A[1] と A[i] の間に k が存在する場合、見つかった値は true または false です。

最初の反復の前は保持されます。その時点では A[1] は単一の要素であり、見つかったのは false に初期化されているためです。

ループの後、i は等しい i := 1 found := falseto n および/または found は true (while 条件) になる可能性があるため、アサーションは i<=n を考慮して同じままです。
これは正しいと思いますか。

4

1 に答える 1

-1

主張は正しいが、役に立たない。found はブール値であり、A のプロパティに関係なく、True または False が含まれます。これは、アルゴリズムの正しさを証明するのに役立ちません。

これは多肢選択式の質問でしたか? 他の選択肢は何でしたか？

于 2013-03-22T17:09:35.573 に答える