Schleifenvariante für eine while-Schleife, die gelegentlich nicht abnimmt?

7

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.

f1=a+2b+1
Andrew Raleigh
quelle
1
Sehr schön! Ich denke, Sie sollten daraus eine Antwort machen (oder sogar die Antwort).
Anton Trunov

Antworten:

7

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:SD1f2:SD2S(D1,1)(D2,2)12D1×D2(x1,y1)(x2,y2)x11x2x1=x2,y12y2

Also, wenn sind, dassf1,f2

  • f1 erhöht sich nie und
  • wenn nicht abnimmt, tut ,f1f2

dann ist die Karte eine Variante, die die Beendigung beweist.(f1,f2):SD1×D2

Klaus Draeger
quelle
Danke für den Tipp! Wir haben keine lexikografischen Kombinationen erstellt, ich werde mich jetzt darum kümmern. Können Sie erklären, wie dies zu einer Verringerung in allen Fällen führen würde?
Andrew Raleigh
@ AndrewRaleigh Ich habe einige Details hinzugefügt
Klaus Draeger
Das macht sehr viel Sinn, ich habe es nie so gesehen. in diesem Fall und ? Obwohl es gelegentlich gleich bleibt und die Vorlesungsfolien nichts darüber aussagen, ob dies erlaubt ist oder nicht.
f1=a
f2=ba
Andrew Raleigh
1
Das Problem mit ist, dass es zunehmen kann (wenn getauscht werden). Versuchen Sie, einen Ausdruck zu finden, der in diesem Fall gleich bleibt und im anderen abnimmt (wenn dekrementiert wird). f1=aa,ba
Klaus Draeger
1

Hier ist ein Ansatz, der nur eine Abbildung umfasst: einfache Fallanalyse kann zeigen, dass immer abnimmt, wenn Sie die Schleife durchlaufen.

f=(a+1)(b+1)+(ba)
f
Anton Trunov
quelle