4

ループ不変式が問題の正しさを証明するためのものであることは知っていますが、問題がどんなに些細なものであっても、どのようにループ不変式を作成するのかがよくわかりません。これが例です。誰かが私が考え出すために考慮すべきステップは何かを指摘できますか. ループ内で変化するすべての値が不変条件に含まれている必要があることはわかっています。この問題について教えてください。事後条件も見つける必要があります。説明は答えよりも価値があります。助けてください。

{M > 0 and N >= 0 }

a = M;
b = N;
k = 1;

while (b > 0) {
    if (b % 2 == 0) {
        a = a * a;
        b = b / 2
    } else {
        b = b – 1;
        k = k * a;
    }
}

{ ? ? }
4

2 に答える 2

1

ループ不変条件の難しい部分は、常に「正しい」答えを保証する (私が知っている) アルゴリズムがないことです。

まず、質問のアルゴリズムについて、プログラムをたどってみて、アルゴリズムの目的を見つけてください (ヒント: 指数は楽しいものです)。トレース中は、変数 a、b、および k を追跡します。

たとえば、 と を使用M = 2しN = 1,2,3,...ます。N のいくつかの値の後、変数 a、b、および k の間に関係が生じ始めることに気付くでしょう。

ループの不変条件が分かれば、事後条件は簡単に思い付くはずです。

これがあなたのためにボールを転がしてくれることを願っています!

于 2015-10-25T20:18:34.127 に答える
0

さて、あなたはこれを少し後退させています。あなたが言ったように、ループ不変条件の目的は、プログラムの正しさを証明するのを助けることです。私はあなたがこのプログラムを書いていないと思います -- そうでなければ、あなたはそれが何のためにあるのかを知っていて、ループを書く前にループ不変条件を思いついたでしょう。それはループが正しいことを理解するための鍵だからです。

それで... 何のためのプログラムですか？それが正しいってどうやってわかるの？ループ不変条件は、2 番目の質問に対する回答の一部になります。

次のように聞こえます: すべての反復の開始時と終了時に、k=...b.... . ループ後、b==0 となるので .... となり、プログラムは正しいことになります。

答えを詳しく説明したくはありません。おそらく宿題であり、自分で見つけた場合にのみ学ぶことができるからです。

于 2015-10-25T21:05:42.413 に答える