問題タブ [loop-invariant]

長さ「l」の文字列が含まれる配列「line」と、長さ「p」の文字列が含まれる配列「nl」があります。注: "l" と "p" は、対応する各配列の長さである必要はありません。パラメーター "at" は、挿入が "line" 内で行われる位置になります。再開: 長さ "p" の配列が "line" に挿入され、位置 (at,i,at+p),'p' の位置の間で "line" のすべての文字が右に移動して挿入されます。

保証の私のロジックは、「行」に挿入された要素が同じ順序であり、「nl」に含まれる文字と同じであるかどうかを確認することです。

コードは次のとおりです。

これが私が受け取っている エラーです。

ありがとう。

次のループを検討してください。

^{y = b a}と結論付けたい

私はしばらく考えていましたが、それを結論付けるのに十分なほど強力なループ不変式を見つけ出すことができないようです。誰もこれにアプローチする方法を知っていますか?

どんな助けや洞察も深く感謝しています。

私は論理の世界に不慣れです。Hoare Logic と、プログラムの部分的および全体的な正しさを学んでいます。以下の質問を解決するために多くのことを試みましたが、失敗しました。

私の友人の一人が私に次の答えをくれましたが、それが正しいかどうかはわかりません.

この問題の解き方を順を追って教えてください。

更新しました

特定のクラスとそれぞれのメソッドを使用して以下に説明する、いくつかのダフニーの問​​題を解決する際の問題。他に何か必要な場合は、教えてください。事前に感謝します。また、rise4fun のこのすべてのコードでリンクが更新されます。

オンライズ4ファン

単純なプログラムの正しさを証明する方法を常に考えています。たとえば、First Missing Positiveのようなインタビューの問題です。プログラムは次のようになります。

このプログラムの不変式を構築する方法は? 単純なアルゴリズムの不変式を構築するための一般的なヒントは何ですか?

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

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

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]に等しい場合、検索していた要素が見つかったことを意味します。したがって、アルゴリズムは正しいです。

これらは正しいですか？