Terminierung einer Schleife < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 02:59 So 13.05.2012 | | Autor: | halonol |
| Aufgabe | Weisen Sie mit der auf Vorlesungsfolie 49 beschriebenen Methode nach, dass die while-Schleife im folgenden Programmabschnitt terminiert. Halten Sie sich dabei exakt an das auf der Folie beschriebene Verfahren: Geben Sie zunächst an, wie ui aus den Werten der Variablen a und b zu berechnen ist. Begründen Sie dann für jeden der Punkte 1 bis 3 der Folie kurz, warum er zutrifft.
// Es gilt n > 0:
int a = 2;
int b = n;
while(a < b + 10) {
a = a * 2;
b = b + 1;
} |
Man soll zu den "Iterationen 0,1,... eine Folge von Werten u 0, u1, u2 ..., die sich jeweils nach einer
festen Formel aus den Werten von Programmvariablen ergeben, konstruieren, und zwar für u0 bei Eintritt in die Schleife und für ui am Ende der i-ten Iteration (for: nach Inkrement)
Zum Beweis der Terminierung genügt dann nachzuweisen, dass:
1. u0 > 0
2. [mm] u_i+1 [/mm] < [mm] u_i [/mm] - d für alle i und einen festen Wert d > 0
3. Für ui ≤ 0 wird die Schleife nach der i-ten Iteration verlassen".
Ich habe mir als Folge u=b-a+2 gewählt.
Für [mm] u_0 [/mm] gilt dann:
[mm] u_0=n-2+2=n>0. [/mm] Also ist die erste Bedingung erfüllt.
Zur zweiten Bedingung:
2.
[mm] u_i=b-a+2=n-a+2
[/mm]
[mm] u_i+1=b+1-2a+2=n-2a+3
[/mm]
Vergleicht man dies, muss man ja nur -a+2 und -2a+3 vergleichen.
Da a>=2 ist, gilt natürlich -a+2<-2a+3. Im Gesamten folgt also die zweite Bedingung.
3. Punkt 3 habe ich allerdings Schwierigkeiten zu beweisen.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.java-forum.org/java-basics-anfaenger-themen/136180-terminierung-schleifen.html#post898030
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:20 Di 15.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
