問題タブ [loop-invariant]

二分探索に関する Jon Bentley の章を含む複数の記事を読みました。これは、正しいバイナリ検索ロジックについて私が理解していることであり、私が行った簡単なテストで機能します。

ソートされた重複で最初の出現を見つけるには、ミッドを返すのではなく、条件が続行する場合に 3 行目をチャンスとします。

同様に、繰り返される要素の最高のインデックスを取得するには、次の場合に実行しlow = mid + 1て続行しますarr[mid]==k

このロジックは機能しているようですが、複数の場所でループ不変式が次のように表示されます

low + 1 < high混乱しており、の代わりにいつ使用したいのかを理解したいと思っていますlow < high。

上記で説明したロジックではlow + 1 < high、単純な例でテストすると、状態がエラーになります。

low + 1 < highの代わりにwhileループで使用する理由とタイミングを誰かが明確にすることはできますかlow < high?

次のコードでループ不変条件を見つけようとしています。

最も近い対 Iter(A) を見つける:

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

ループの不変条件を見つけて、それらの正式なステートメントを書く方法を理解するのに苦労しています。したがって、ループ不変条件は、ループの各反復の直前と直後に真である条件にすぎません。コードがスワップを行っているようです。次の要素が配列内で現在の要素よりも大きい場合は、場所を切り替えます。つまり、ループ不変式の定義から、実際には i < 100 のように聞こえますが、それはループが実行されるためには true でなければならないためですが、私にはよくわかりません。いくつかの説明をいただければ幸いです。

このコードのループ不変条件を見つけようとしています。通常、私は実際に入力を使用してコードを調べ、それを理解しようとします。しかし、このアプローチは常に機能するとは限りません。ループの不変式を見つけるためのより良い方法はありますか? どんなアドバイスでも大歓迎です！