✔ Kopfgesteuerte Schleife nach Anweisungsvorschrift nicht terminieren lassen

[ZodiacXP]

int a, b; 
...  // Definition der Inhalte von a und b 
while (a != b) {  
  if (a > b) 
    a = a - b; 
  else 
    b = b - a; 
}
System.out.println(a);

Terminiert diese Schleife bei allen int-Eingabewerten?

Meine Annahme: Selbst wenn a=MAX_INTEGER und b=-1 wird aus a durch overflow MIN_INTEGER, der sicherlich wieder bei genügender Addition b=-1 trifft.
Ist a allerdings beliebig ungerade und b beliebig gerade so kann die Schleife nicht terminieren.

Bei beiden Annahmen bin ich mir sehr unsicher wüsste aber nicht wie ich das zeigen kann. Am besten natürlich ohne Beispiel, ganz allgemein.

 

[Kai008]

Nein, sie beendet nicht, solange beide Zahl negativ sind. Wenn man eine Negative subtrahiert wird sie addiert, wodurch sich b von a wegbewegt.
Wenn man dem Overflow ignoriert und a bspw. "-5" und b -1 ist, tritt die else in Kraft, wodurch b - a ist, also 4, dann 9 usw ist.
Beachtet man den Overflow, wird a zu "-2147483648", welches zu b addiert wird, und dadurch einen Overflow in b auslöst. Danach wird es nocheinmal addiert, wodurch es wieder -1 ist.

 

[Matthias Reitinger]

int a, b; 
...  // Definition der Inhalte von a und b 
while (a != b) {  
  if (a > b) 
    a = a - b; 
  else 
    b = b - a; 
}
System.out.println(a);

Terminiert diese Schleife bei allen int-Eingabewerten?

Diese Schleife terminiert nur für a>0 && b>0 (Überläufe außer acht gelassen).

Meine Annahme: Selbst wenn a=MAX_INTEGER und b=-1 wird aus a durch overflow MIN_INTEGER, der sicherlich wieder bei genügender Addition b=-1 trifft.

Die Überlegung ist falsch. Sobald a MIN_INTEGER ist, gilt b > a, also wird die Zuweisung b = b - a; durchgeführt.

Ist a allerdings beliebig ungerade und b beliebig gerade so kann die Schleife nicht terminieren.

Wie kommst du darauf? Für a=1 und b=2 terminiert die Schleife doch beispielsweise.

Bei beiden Annahmen bin ich mir sehr unsicher wüsste aber nicht wie ich das zeigen kann. Am besten natürlich ohne Beispiel, ganz allgemein.

Für Programm-Verifikation allgemein verwendet man z.B. das wp-Kalkül oder das Hoare-Kalkül.

Grüße, Matthias

 

[ZodiacXP]

Gut. Danke!
Damit wären die Sachen bei denen ich mir ganz unsicher war auch gegessen.

Demnach terminiert die Schleife unter Berücksichtigung vom Overflow immer.

(Korrigiert mich wenns falsch ist - bin so schon fitter als die Klausur es fordern wird aber liebe halt so besondere Sachen )

 

[Matthias Reitinger]

Demnach terminiert die Schleife unter Berücksichtigung vom Overflow immer.

Ähm… nein? Niemand hier hat das behauptet. Überleg dir einfach für den Fall a=INT_MAX und b=-1 mal was nacheinander passiert.

 

[ZodiacXP]

Grob jeweils Schleifenanfang:
Durchgang 1, a=MAX und b=-1
Durchgang 2, a=MIN und b=-1
Durchgang 3, a=MIN und b=MAX
2, 3 wiederholt sich ab hier

Woah. Ich sollte vielleicht ein bisschen weiterdenken und nicht so vorschnell seien bei meinen Überlegungen. Sorry, übelst dummer Fehler
Alles klar. Danach hab ich gesucht Danke!!