Aufgabe Vorschlag C1 - Aufgabe 5 · Abitur Hessen Informatik LK 2022

WHILE-Programme

WHILE-Programme sind ein Berechnungsformalismus, der an traditionelle Programmiersprachen angelehnt ist.

WHILE-Programme bestehen aus:

Variablen ($x0, x1, x2, \dots$), Konstanten ($0, 1, 2, \dots$), Trennsymbolen ($;,:=$),

Operationszeichen ($+, -, \neq$) und Schlüsselwörtern ( WHILE, DO, END).

WHILE-Programme sind wie folgt definiert:

Jede Wertzuweisung mit den Variablen $xi$ und $xj$ und der Konstanten $c \in \mathbb{N}_0$ der Form $xi:= xj + c$ bzw. $xi:= xj - c$ ist ein WHILE-Programm.

Falls $P_1$ und $P_2$ WHILE-Programme sind, dann ist auch $P_1; P_2$ ein WHILE-Programm.

Falls $P$ ein WHILE-Programm ist und $xi$ eine Variable, dann ist auch WHILE $xi \neq 0$ DO $P$ END ein WHILE-Programm.

Bei der Wertzuweisung $xi:= xj + c$ wird der Variablen $xi$ die Summe der Werte von $xj$ und $c$ zugewiesen. Bei der Wertzuweisung $xi:= xj - c$ ist dies entsprechend die Differenz, wenn der Wert nicht negativ ist. Ist $xj - c < 0$, wird der Variablen $xi$ der Wert $0$ zugewiesen.

Die Komposition $P_1; P_2$ wird so interpretiert, dass zuerst $P_1$ und anschließend $P_2$ ausgeführt wird.

Innerhalb einer WHILE-Schleife WHILE $xi \neq 0$ DO $P$ END ist das Programm $P$ solange wiederholt auszuführen, wie der Wert von $xi$ ungleich Null ist.

Material 1

WHILE-Programm für die WHILE-berechenbare Funktion $f(a, b) = a * b$

01 x3:= x1 + 0;

02 WHILE x2 ≠ 0 DO

03 WHILE x1 ≠ 0 DO

04 x0:= x0 + 1;

05 x1:= x1 - 1

06 END;

07 x1:= x3 + 0;

08 x2:= x2 - 1

09 END Hinweis: In den Variablen $x1$ und $x2$ stehen anfangs die Werte $a$ und $b$. Die restlichen Variablen sind mit dem Wert $0$ vorbelegt.

Material 2

WHILE-Programm für die WHILE-berechenbare Funktion $f(a, b) = a^b$

01 x0:= x0 + 1;

02 WHILE x2 ≠ 0 DO

03 x0:= x0 * x1;

04 x2:= x2 - 1

05 END Hinweis: Zur Abkürzung wurde hier x0:= x0 * x1; verwendet, da dieser Ausdruck WHILE-berechenbar ist (siehe Material 1). Die Vorbelegung der Variablen $x0$, $x1$ und $x2$ entspricht der in Material 1 beschriebenen.

Material 3

Beispiel eines WHILE-Programms

01 x2:= x1 + 0;

02 WHILE x2 ≠ 0 DO

03 x3:= x3 + 1;

04 x2:= x2 - 2

05 END;

06 WHILE x3 ≠ 0 DO

07 x2:= x2 + 2;

08 x3:= x3 - 1

09 END;

10 WHILE x1 ≠ 0 DO

11 x2:= x2 - 1;

12 x1:= x1 - 1

13 END;

14 WHILE x2 ≠ 0 DO

15 x1:= x1 + 1;

16 END Hinweis: $x3$ ist mit dem Wert $0$ vorbelegt.

Die Laufzeit $TIME_P(a, b)$ eines WHILE-Programms $P$ ist die Anzahl der Schritte, die durchlaufen werden, wenn $P$ mit dem Wert $a$ in der Variable $x1$ und Wert $b$ in der Variable $x2$ gestartet wird. Jede Wertzuweisung und jede Auswertung einer Schleifenbedingung wird als ein Schritt gezählt.

Bestimmen Sie die Laufzeit $TIME_P(a, b)$ des WHILE-Programms in Material 1 in Abhängigkeit von $a$ und $b$.

[3 BE]