アルゴリズム

Question

k :=0 
for i ←1 to n 
    c←a[i] 
      k←k+1 

この変化をdoesntのものが要素

Answer 1

技術の数を知る的アルゴリズムである、はい、k <= iは不変ではなく、非常に便利なものをです。不変量を使う理由は、ループの後の状態を証明するためにそれらを使うことができるからです。あなたの不変量を使って、ループの後にk <= nが保持されていることを証明できます。非常に真実ですが、ループが実際に何をしているかを証明しようとするのは本当に役に立ちません。

したがって、どのような不変式が有用でしょうか？ kがaとbの両方の要素数に等しいことを証明したいと考えています。 aの要素をループしているので、kはa[i]までの要素の数と同じで、bにもなります。

---

この不変式が成り立つことを証明する必要があります。私はそれを少しスケッチで保つつもりですので、これを正式化することはあなた次第です。

当初、k = 0はa[1]の前の要素の数であり、それもbであることを示す必要があります。そのような要素はありませんので、k = 0が正しいです。

ここで、a[i]までの要素の数がbであるとすると、不変量がi+1の場合に成り立つことを証明する必要があります。 2つのオプションがあります：a[i+1]がbにあるかどうか。 bで

• a[i+1]場合、bにあるa[i + 1]までの要素の数はbにあるa[i]までの要素の数よりも大きいものです。不変量を使うと、ki+1 = ki + 1を表示する必要があります。
• bでないa[i+1]場合は、次にbにあるa[i + 1]までの要素の数はbにあるa[i]までの要素の数に等しいです。我々の不変量を使って、したがって、それはki+1 = kiを示す必要があります。

私はそれらを証明するためにあなたに任せます。