Question
the following pseudo code returns the nth Fibonacci number:
if n = 0 then
return 0
a ← 1
b ← 1
for i = 1 to n − 1 do
c ← b − i
b ← c + a
a ← c + 2*i + 1
return b
I am trying to find any loop invariant for the variables a and b, (as i understand it has to be valid before and after the loop, but i can't seem to be able to come up with anything, except maybe b >= i
, but I'm not sure that counts as an invariant). As far as I get it, simply saying b = b - i + a
wouldn't really mean anything. Any help on the subject would be greatly appreciated.
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange