java - Javaループ不変条件

Question

int logarithmCeiling(int x) {
    int power = 1;
    int count = 0;

    while (power < x) {
        power = 2 *power;
        count = count +1;
    }
    return count;
}

上記のコードは、whileループを使用して、指定された正の整数の下位対数を計算して返すためのJavaのメソッドであることが意図されています。上記のループに不変条件をどのように提供しますか？つまり、開始前、ループ本体が終了するたび、およびループ条件の否定が保持されます。

score 1 · Accepted Answer

電力は、ループの開始時と終了時に常に2^countに等しくなります。否定の場合、ループが終了すると、x <= power = 2^countになります。

score 0 · Accepted Answer

メソッドの部分的な正しさを証明するのに適した不変量を探していると思いますか？それ以外の場合、「true」または「false」は常に不変です。私はこのようなもので行きます：

I: {(power <= x) AND (power == 2 ^ count) AND (x > 2 ^ count -1) AND (power >= 1)}

rhsは初期化から暗示され、xの下限を確保するのに役立ちます。否定されたループ条件とともに、後で暗示することができます。

{(x <= 2 ^ count) AND (x > 2 ^ (count -1))}

これは、関数全体の部分的な正しさを示すためにまさに必要なものです。

score 0 · Accepted Answer

powerの値とcount：power = ^2countの値の間には単純な関係があります。これはループの開始と終了に当てはまりますが、ループ本体の特定の場所には当てはまりません。

score 0 · Accepted Answer

常に真である変数または条件を探します。各反復カウントは常に1ずつ増加し、累乗は常に2で乗算されます。この関数の目的は、指定された引数の下位対数を見つけることであるため、ループ不変条件は、カウントが常にの対数に等しいことであると言えます。 x、切り捨て。もう1つは、カウントが常に電力の対数に等しいということです。

java - Javaループ不変条件

4 に答える 4

Related

Reference