Die Aufgabe
Aufgabe 3.3
Gegeben ist eine Schale mit h hellen und d dunklen Pralinen (h und d beliebig) sowie eine Vorratsschale mit unendlich vielen dunklen Pralinen. Betrachtet werde der folgende Algorithmus:
Wiederholen Sie folgende Schritte
- Entnehmen Sie der Schale zufällig zwei Pralinen.
- Falls Sie zwei Pralinen derselben Sorte erwischen, essen Sie beide Pralinen auf und legen aus der Vorratsschale wieder eine dunkle Praline in die Schale nach.
- Falls Sie eine helle und eine dunkle Praline erwischt haben, dürfen Sie nur die dunkle Praline essen, die helle muss zurück in die Schale gelegt werden.
bis nur noch eine einzige Praline in der Schale liegt.
- Erstellen Sie das Flussdiagramm für den beschriebenen Algorithmus.
- Sind die Forderungen nach Endlichkeit und Determiniertheit erfüllt?
- Welchen Output liefert dieser Algorithmus, d. h. kann man eine Aussage über die in der Schale verbleibende Praline machen?
In der Schale liegen h helle und d dunkle Pralinen; h und d sind beliebige natürliche Zahlen (0, 1, 2, …). Daneben steht ein Vorrat, aus dem man immer eine dunkle Praline nachlegen kann. Eine Runde heißt: zwei Pralinen ziehen und nach Regel 2 oder 3 behandeln.
Annahme: Am Anfang liegen mindestens zwei Pralinen in der Schale (h + d ≥ 2). Sonst kann man keine zwei ziehen. Liegt nur eine darin, ist sie schon die letzte.
Merke: Um etwas über das Ende eines Ablaufs zu sagen, sucht man eine Größe, die sich in jeder Runde auf dieselbe Art verändert, oder eine, die gleich bleibt.
- (a) Das Flussdiagramm aus den drei Regeln aufbauen.
- (b) Zählen, wie viele Pralinen jede Runde verschwinden; daraus Endlichkeit. Dann prüfen, was der Zufall am Ablauf und am Ergebnis ändert.
- (c) Zeigen, dass „h gerade oder ungerade“ sich nie ändert; daraus folgt die Farbe der letzten Praline.