Hi,
Also dass da NICHT ungleich 0 stehen sollte, wurde ja schon geklärt. Was mir aber nicht ganz verständlich ist, ist dies:
invariant hat geschrieben: ↑10. Mai 2017 11:21
Wenn in den Elementen 0...h-1 schon ein Element ungleich 0 vorgekommen wäre, wäre der Algorithmus schon terminiert, ergo wäre dieser Iterationsschritt nicht vorhanden. Wenn wir also in der h-ten Iteration sind können wir davon ausgehen, dass der Algorithmus in den Iterationen 0...h-1 nicht terminiert ist, also keine Elemente ungleich 0 vorgekommen sind.
Mein Problem damit: Die Invariante muss doch nach der Terminierung (dem letzten Iterationsschritt) korrekt sein? so verstehe ich zumindest das AlgoWiki:
The invariant of a loop consists of all assertions that are true immediately before the first iteration, immediately after the last iteration, and between two iterations. These assertions are called the invariant assertions of this loop.
Da wir bei Position 0 anfangen würden wir doch in h = 3 Position 2 der Liste anschauen. Nun wäre also dort ein key != 0. Also terminieren wir mit true. Die Invariante würde nun aber sagen, dass an Position 0...2 von head kein key != 0 ist. Was ja falsch ist.
Muss also die Invariante nach Terminierung gar nicht mehr stimmen oder wird der Schritt in dem Terminiert wird nicht als Iteration gezählt?
Vielen Dank für eine Antwort
LG Robin
