-
Prof. Martin Hofmann, PhD Ludwig-Maximilians-Universitat
MunchenDr. Steffen Jost Institut fur Informatik
4. November 2015
3. Ubung zur Vorlesung
Einfuhrung in die Programmierung
A3-1 Simpler Taschenrechner Implementieren Sie zum Aufwarmen
einen einfachenTaschenrechner! Es sollen solange Zahlen von der
Tastatur eingelesen und aufaddiert werden,bis der Benutzer den
String end eingetippt hat. Beispiel:
Dies ist ein Taschenrechner. (Eingabe "end" zum Beenden)
Zustand: 0 Gib bitte eine ganze Zahl ein: 77
Zustand: 77 Gib bitte eine ganze Zahl ein: -2
Zustand: 75 Gib bitte eine ganze Zahl ein: acht
Das war keine ganze Zahl! (Eingabe "end" zum Beenden)
Zustand: 75 Gib bitte eine ganze Zahl ein: -6
Zustand: 69 Gib bitte eine ganze Zahl ein: end
Endstand ist: 69
Um unnotige Tipparbeit zu ersparen, gibt es auf der
Vorlesungshomepage eine unverbindlicheDateivorlage, welche Sie
benutzen konnen, wenn Sie wollen.
A3-2 Hoare-Tripel Entscheiden Sie, ob folgende Hoare-Tripel
gultig sind:
a) {a + b > 0} n = a + b {n > 0}b) {i < j} i = i + 3 {i
+ 3 < j}c) {n = a + b} c = a + 1; a = b 1; b = c; {n = a +
b}
Alle benutzten Variablen sind initalisiert (mit unbekanntem
Wert) und haben den Typ int.
A3-3 Hoare-Logik: While-SchleifeHier ist noch einmal zur
Erinnerung die Hoare-Regel fur die While-Schleifen von 4-153:
{I b}c{I} P I I b Q{P}while(b)c{Q}
Beweisen Sie durch Anwendung dieser Regel, dass fur das
Programmfragmentint x = 1;
while (x+y > n) {
x = x + 2;
y = y - x;
}
aus der Vorbedingung {z 69} die Nachbedingung {y < nz >
42} hergeleitet werden kann!
-
Hinweise: Das Problem mit der Anwendung der Hoare-Regel fur
While-Schleifen ist, dassdie Formel I nur in den Pramissen der
Regel (also uber dem Strich) auftaucht. Wahrend P ,Q und der Code
durch die Aufgabenstellung schon vorgegeben sind, mussen wir I
irgendwiepassend wahlen. Oft gibt es dazu auch mehrere
Moglichkeiten es reicht aber naturlich aus,lediglich eine richtige
Moglichkeit zu finden.
Es ist daher oft zweckmaig, die Regel Ruckwarts zu rechnen. Die
Nachbedingung muss ausder Negation der Schleifenbedingung und der
Invariante herleitbar sein, d.h. wir mussen dieInvariante stark
genug wahlen, damit die Nachbedingung zusammen mit der negierten
Schlei-fenbedingung ausreicht. Danach schaut man, ob die Pramisse
stark genug ist, die gewahlteInvariante zu implizieren. Ist dies
nicht der Fall, muss man die Invariante entsprechend ab-schwachen.
Danach pruft man, ob diese schwachere Invariante trotzdem noch
stark genug ist,mit der negierten Schleifenbedingung die
Nachbedingung herzuleiten, usw.
Zur Erinnerung: Die logische Negation einer Formel A notiert man
mit A, die logi-sche UND-Verknupfung zweier aussagenlogischer
Formeln mit A B, die logische ODER-Verknupfung A B und die
Implikation mit A B (oder auch mit (A) B).
H3-1 Hoare-Tripel II (3 Punkte; Abgabe: H3-1.txt oder
H3-1.pdf)
d) {0 < n+ 1 n < m} n = n + 1 {0 < n n m}e) {n > 0}
n = a + b {n = a + b a + b > 0}f) {z = x + y} if(z%2 == 0) x = x
+ 1; else y = y + 1; {x + y > z}
H3-2 Hoare-Logik: While-Schleife II (6 Punkte; Abgabe: H3-2.txt
oder H3-2.pdf)
Sei P das folgende Programmstuck, wobeia, b, c und n Variablen
des Typs int sind.
a = 0;b = 0;c = 1;while (b != n) {a = a + c;b = b + 1;c = c + 6
* b;
}
Schleifendurchlauf n a b c
0 5 0 0 1
1
Erganzen Sie in der Tabelle rechts die Werte der Variablen n, a,
b und c, und zwar jeweilsam Ende eines Schleifendurchlaufs. Die
erste Zeile darin enthalt die Werte von n, a, b und c,vor Eintritt
in die Schleife. Fur die Tabelle nehmen wir zusatzlich n = 5 an; im
Folgendemist n aber beliebig.
Zeigen Sie nun die Gultigkeit des Hoare-Tripels {n > 0} P {a
= n3}!Hilfestellung: Die Aussage c = (b + 1)3 b3 ist Teil einer
moglichen Invariante.
-
H3-3 Code Verstandnis (0 Punkte; Abgabe: H3-3.txt oder
H3-3.pdf)
Gegeben ist das rechts abgedrucktefurchterliche Programm.
Berechnen Siedie Ausgabe des furchterlichen Pro-gramms mit Papier
& Bleistift, also ohneComputer. Geben Sie zusatzlich Schrittfur
Schritt an, welche Variable in wel-cher Programmzeile welchen
absolutenWert zugewiesen bekommt (d.h. Anga-ben wie Zeile 5: x = 28
und nicht Zei-le 5: x = y+8).Beispiel:Fur das kleine Programm
10 int x = 0;
20 int y = 3;
30 for (int i = 1; i y)
060 {
070 int z = x / y;
080 z*=2; //Kurz fur z=z*2
090 z++; //Kurz fur z=z+1
100 y+= z; //Kurz fur y=y+z
110 if (z
