So finden Sie den Loop Invariant in Hire Triples

Question

Hey, ich bin neu, um Triples zu hoare, und ich kann nicht verstehen, die Loop-Invarianten in der Hypothese zu finden.Zum Beispiel diese während der Schleife

generasacodicetagpre.

Der Invariante ist [2x + y> 5], aber ich verstehe nicht, wie man es finden kann.Ein Schritt für Schritt Erläuterung, wie er findet, wird er sehr geschätzt.

Answer 1

Verstehen Sie zuerst die Bedeutung des Schleifens invariant. Es bedeutet eine Erkrankung, die bei jeder Iteration des Programms / Algorithmus an der Beginn sowie bei der Kündigung der Schleife trifft. Ihr Programm ist so etwas.

$$ x> 1 \ text {und} y> 1 $$

$$ \ Text {während} x> 0 $$

$$ \ HSPACE {4cm} \ text {do} x:= x - 1, y:= y + 2 $$

$$ \ Text {ende} $$

$$ x + y> 5 $$

$ 2x + y> 5 $ ist ein Invariante wie Sie beschrieben. Es ist aus dem Programm sichtbar, das sowohl $ x $ und $ y $ größer als $ 1 $ während der ersten Iterataion der Schleife. Also in der ersten Iteration während der Schleife $ 2x + y> 5 $ (Sie können es beweisen). HINWEIS In jeder Iteration der While-Schleife wird der Wert des $ x $ REDIEREN ZURÜCK VON VALUE $ 1 $ und Der Wert von y wird zunehmen um zwei, so dass sich die Ungleichung $ 2x + y> 5 $ erfüllt sein wird. Sie können es beweisen. Kommt jetzt zur Kündigung, an diesem Punkt $ x $ wird eine negative Zahl sein und mein Anspruch ist Wert von $ y $ wird mindestens $ 5 $ sein. Somit der Invariante $ 2x + y> 5 $ SI TRUET durch die Iteration der While-Schleife.

Beispiel:

lass $ x= 2 $ und $ y= 2 $ , dann $ 2 \ mal 2 + 2= 6> 5 $ ist zufrieden. Nun in der zweiten Iteration $ x= 1, y= 4 $ so $ 1 \ mal 2 + 4> 5 $ Zufrieden. Jetzt $ x= 0, y= 6 $ , Schleife terminiert, $ 2 \ mal 0 + 6> 5 $ .