Loop invariant: decreasing a variable and swapping it
-
01-11-2019 - |
Question
As an example exercise, we were asked to find the loop invariant for this bit of code.
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
From what I can see, it first ensures that a >= b
.
After that, each loop iteration decreases the value of a
by 1.
This will continue until a
and b
are 0.
Then one final iteration terminates the loop with a == -1
.
However from what I can tell, if the loop invariant is something like a >= b
, it fails upon termination as a = -1 and b = 0
.
Could anyone tell me the actual loop invariant of this function as I'm a bit confused.
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange