3

次の関数のループ不変条件を正しく識別するのに苦労しています。

F(y)
    X <-- 1
    while (y > 1)
        do x <-- x * y
           y <-- y - 1
    return (x)

x = 1 OR x = y!そのステートメントが前提条件として真であり、事後条件として真であるため、ループ不変条件を特定しました。

たとえば、y = 3の場合、ループの最初の反復でx = 1 * 3になり、3ではなく3になります。たとえば、すべての反復に当てはまるとは限りません。これは6に相当します。

これは私の混乱が本当に私が推測するところです。いくつかの本の記事は、ループ不変条件は、ループの最初またはループ（したがって前提条件）で真に等しくなければならず、ループの終わり（したがって事後条件）でも真でなければならないステートメントであると述べていますが、必ずしもそうする必要はありませんループの途中で真を保持します。

上記の関数の正しいループ不変条件は何ですか？

4

2 に答える 2

6

可能なループ不変条件はx⋅yです！= y 0！ここで、y 0は、関数に渡されるyの初期値です。このステートメントは、ループがすでに何回繰り返されていても、常に当てはまります。

ループが開始する前に前提条件が保持される必要があり、ループが終了した後に事後条件が保持される必要があり、ループの反復が何回行われたとしても不変条件が保持される必要があります（これが「不変条件」と呼ばれる理由です。 tそれが真実であることを変更します）。

一般に、同じループに対して異なる可能性のある不変条件が存在する可能性があります。たとえば、1 = 1はどのループの不変量としても真になりますが、アルゴリズムの正当性を示すには、通常、より強力な不変量を見つける必要があります。

于 2011-12-05T23:39:15.393 に答える
1

ループ不変条件は、事後条件、少しの直感、および代数のような推論から導き出すことができます。

事後条件の一部を知っています：x == Y!、ここで、Yは引数として与えられた初期値です。 y値が変化する変数です。そして、それはポスト条件の残りです、ところで：y == 1。

各パスで何が真実ですか？逆の理由。

最後のパスでx == Y*Y-1*...*2 and y == 2。

それ以前は？ x == Y*Y-1*...*3 and y == 3。

それ以前は？

最初は何が本当y == Yですか？

ついに。事後条件と不変条件を考えると、物事を動かすために必要なステートメントの最も弱いセットはどのような前提条件ですか？コードは、を示唆してx=1 and y=Yいます。

ループを通過するたびに、何かが変化し、プログラムが状態を事後状態に向けて確実に進める必要があることを知っています。本当？証明可能なものがゼロに向かって減少するループ状態の自然値関数はありますか？（変数がそれを簡単に行うように見えるので、これはトリックの質問のyように思えます。多くの実際のループでは明らかではないので、ループの設計について質問する必要があります。）

于 2011-12-06T01:00:07.490 に答える