Hallo,
ich habe große Schwierigkeiten die Korrektheit eines Algorithmus zu beweisen und würde das ganze mal ganz gerne an dem Beispiel zu Berechnung der Fakultät durchspielen und benötige dafür eure Hilfe.
code:
1:
2:
3:
4:
5:
6:
7:
i = 1
f = 1
while i <= n
f = f*i
i = i+1
end while
Invariante: f = (i-1)!
I.A.:
I.V.: f = (i-1)! (Invariante)
I.S.: ZZ. i --> i+1
f = (i+1-1)! = i!
Stimmt das so? Wahrscheinlich nicht oder? Mein Problem ist, dass ich gar nicht so richtig weiß, was im Induktionsschritt herauskommen muss, damit ich gezeigt habe, dass die Invariante auch im i+1 Durchlauf der Schleife korrekt ist.
Wäre super, wenn mir das mal jemand erklären könnte.