Warum terminiert dieser Algo? < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo liebe Leute,
habe mal wieder ein kleines Problem. Habe jetzt (ein anderes) Java-Programm, welches einen Algorithmus implementiert zur Berechnung der einer Folge von ganzen Zahlen.
Meine Frage jetzt: wie zeige/beweise ich hier, dass das folgende Programm terminiert? Hier habe ich ja jetzt nicht mehr ein reines for-Schleifen-Programm (-> LOOP-Programm), sondern eine (problematische) while-Schleife.
Vielen Dank für Eure Hilfe und liebe Grüße,
Janine
|
|
| |
|
Hallo und guten Morgen,
die Frage ist nur, warum der Algorithmus terminiert. Dafuer ist nur die erste if-Anweisung innerhalb der while-Schleife verantwortlich.
Entweder rdach wird um 1 erhöht (was nur n mal oder so hintereinander geschehen kann) oder ldach wird um 1 erhoeht und dabei rdach evtl erniedrigt.
Jedenfalls wird ldach nie erniedrigt, rdach nur dann erniedrigt, wenn dabei ldach um 1 erhoeht wird, und damit ist nach sowas wie [mm] n^2 [/mm] Schritten die
Bedingung der while-Schleife nicht mehr erfuellt und das Programm terminiert.
Gruss,
Mathias
|
|
|
| |
|
Hi Mathias,
vielen Dank für deine Antwort - das ist genau das worauf ich nicht gekommen bin. Die Inkrementation macht's (natürlich)! 
Liebe Grüße, Janine
|
|
|
|
