Ich arbeite an Übungsproblemen für einen Test, den ich habe, und jedes Beispiel einer Schleifenvariante nahm mit jeder Iteration der Schleife ab. In diesem Fall bleiben die Werte gleich, wenn a <b. Meine Versuche haben mir auch eine Schleifenvariante gebracht, die die Chance auf ein Negativ hat, da gelegentlich a größer als b wird und umgekehrt. Irgendwelche Ratschläge zum Versuch, die Schleifenvariante für diese Frage zu finden und zu beweisen?
def mystery(a,b):
# Precondition: a >= 0 and b >= 0
while a >= 0 and b >= 0:
if a < b:
a, b = b, a
else:
a = a - 1
return a
EDIT: Für alle, die sich für diese Frage interessieren, ist meine beste Lösung wie folgt.
algorithms
loops
loop-invariants
Andrew Raleigh
quelle
quelle
Antworten:
Nur ein Hinweis für den Moment, da dies ein Übungsproblem ist: Betrachten Sie eine lexikografische Kombination von Befehlen.
Im Detail: Angenommen, Sie haben zwei Zuordnungen und aus Ihren Programmzuständen in fundierte geordnete Domänen und . Die lexikografische Kombination von und ist die Reihenfolge auf die durch wenn entweder oder . Es ist auch begründet.f1:S→D1 f2:S→D2 S (D1,≤1) (D2,≤2) ≤1 ≤2 ≤ D1×D2 (x1,y1)≤(x2,y2) x1≤1x2 x1=x2,y1≤2y2
Also, wenn sind, dassf1,f2
dann ist die Karte eine Variante, die die Beendigung beweist.(f1,f2):S→D1×D2
quelle
Hier ist ein Ansatz, der nur eine Abbildung umfasst: einfache Fallanalyse kann zeigen, dass immer abnimmt, wenn Sie die Schleife durchlaufen.
quelle