Schere, Stein, Papier
AFB I–IIPia programmiert „Schere, Stein, Papier“ gegen den Computer: fünf Runden, der Computer wählt zufällig. Die Zahlen 0, 1, 2 stehen für Schere, Stein, Papier; Stein schlägt Schere, Papier schlägt Stein, Schere schlägt Papier.
#include <iostream> #include <string> #include <cstdlib> using namespace std; int main() { string namen[3] = {"Schere", "Stein", "Papier"}; int punkteSpieler = 0; int punkteComputer = 0; for (int runde = 1; runde <= 5; runde++) { int computer = rand() % 3; int spieler; cout << "Runde " << runde << " (0 Schere, 1 Stein, 2 Papier): "; cin >> spieler; cout << "Computer: " << namen[computer] << endl; if (spieler == computer) { cout << "Unentschieden" << endl; } else if (spieler == (computer + 1) % 3) { cout << "Punkt fuer dich" << endl; punkteSpieler++; } else { cout << "Punkt fuer den Computer" << endl; punkteComputer++; } } cout << "Endstand " << punkteSpieler << " : " << punkteComputer << endl; return 0; }
Pia spielt eine Partie. Danach setzt sich ihr Bruder Jan an den Rechner, startet das Programm neu — und gewinnt 5 : 0.
Runde 1 (0 Schere, 1 Stein, 2 Papier): 0 Computer: Stein Punkt fuer den Computer Runde 2 (0 Schere, 1 Stein, 2 Papier): 1 Computer: Stein Unentschieden Runde 3 (0 Schere, 1 Stein, 2 Papier): 2 Computer: Schere Punkt fuer den Computer Runde 4 (0 Schere, 1 Stein, 2 Papier): 0 Computer: Stein Punkt fuer den Computer Runde 5 (0 Schere, 1 Stein, 2 Papier): 1 Computer: Papier Punkt fuer den Computer Endstand 0 : 4
Runde 1 (0 Schere, 1 Stein, 2 Papier): 2 Computer: Stein Punkt fuer dich Runde 2 (0 Schere, 1 Stein, 2 Papier): 2 Computer: Stein Punkt fuer dich Runde 3 (0 Schere, 1 Stein, 2 Papier): 1 Computer: Schere Punkt fuer dich Runde 4 (0 Schere, 1 Stein, 2 Papier): 2 Computer: Stein Punkt fuer dich Runde 5 (0 Schere, 1 Stein, 2 Papier): 0 Computer: Papier Punkt fuer dich Endstand 5 : 0
Nach jeder Partie möchte Pia außerdem ein „Glücksrad“ drehen lassen, das zufällig 10, 20, 30, 40 oder 50 Bonuspunkte vergibt — jeden Wert gleich wahrscheinlich.
- Entnehmen Sie den beiden Probeläufen, welches Zeichen der Computer in den Runden 1 bis 5 jeweils wählt, und notieren Sie, was dabei auffällt.
- Erklären Sie diese Beobachtung und wie Pia das Programm verbessern muss. Gehen Sie auch darauf ein, an welcher Stelle die Verbesserung stehen muss.
- Stellen Sie einen C++-Ausdruck mit
rand()für die Bonuspunkte des Glücksrads auf und begründen Sie ihn schrittweise.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
rand() berechnet seine Zahlen aus einem Startwert. Welcher Startwert wird benutzt, wenn das Programm keinen festlegt? Welche Funktion setzt ihn, und womit bekommt man bei jedem Start einen anderen?Hinweis zu Aufgabe c)
rand() % n und formen Sie Schritt für Schritt um, bis der Wertebereich stimmt. Prüfen Sie am Ende den kleinsten und den größten Wert.Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| Runde | Pias Lauf | Jans Lauf |
|---|---|---|
| 1 | Stein | Stein |
| 2 | Stein | Stein |
| 3 | Schere | Schere |
| 4 | Stein | Stein |
| 5 | Papier | Papier |
Der Computer wählt in beiden Läufen genau dieselbe Folge: Stein, Stein, Schere, Stein, Papier. Jan kannte sie aus Pias Partie und hat jeweils das passende Gegenzeichen gewählt (Papier, Papier, Stein, Papier, Schere).
Erwartungshorizont zu Aufgabe b)
rand() erzeugt keine echten Zufallszahlen, sondern eine berechnete Folge (Pseudozufall), die vollständig vom Startwert abhängt. Ohne srand ist der Startwert immer derselbe (1) — also liefert jeder Programmstart dieselbe Folge.
Verbesserung: #include <ctime> ergänzen und srand(time(0)); einmal am Anfang von main, vor der Schleife, aufrufen. time(0) liefert die aktuelle Zeit in Sekunden, dadurch startet jeder Lauf mit einem anderen Startwert.
Nicht in die Schleife: Dann würde der Startwert in jeder Runde neu gesetzt. Folgen zwei Runden in derselben Sekunde aufeinander (z. B. bei schnellen Eingaben), bekommen sie denselben Startwert und damit dieselbe Wahl des Computers.
Erwartungshorizont zu Aufgabe c)
| Ausdruck | mögliche Werte | Schritt |
|---|---|---|
rand() % 5 | 0, 1, 2, 3, 4 | fünf gleich wahrscheinliche Werte |
rand() % 5 + 1 | 1, 2, 3, 4, 5 | + 1 verschiebt |
10 * (rand() % 5 + 1) | 10, 20, 30, 40, 50 | · 10 streckt |
Gleichwertig: 10 + 10 * (rand() % 5). Falsch wäre z. B. rand() % 50 + 10: Das liefert alle ganzen Zahlen von 10 bis 59. Ein Test mit 100 000 Drehungen ergab für jeden der fünf Werte rund 20 000 Treffer und keinen anderen Wert.
Der Computer rät mit
AFB II–IIIFür den Tag der offenen Tür planen Ole und Hanna ein umgekehrtes Zahlenraten: Die Besucher merken sich eine ganze Zahl von 1 bis 1000, und der Computer rät. Auf jeden Tipp antwortet man mit g („deine Zahl ist zu groß“), k („zu klein“) oder r („richtig“). Der Computer soll immer die Mitte des noch möglichen Bereichs tippen, die Versuche zählen und merken, wenn jemand widersprüchlich antwortet.
Hanna ist überzeugt: „Wenn der Computer immer halbiert, braucht er nie mehr als 10 Versuche. Und selbst bei Zahlen bis eine Million reichen 20.“
g oder k halbiert sich der mögliche Bereich ungefähr.- Entwerfen Sie einen Algorithmus für das Raten durch den Computer (in Worten oder als Struktogramm).
- Implementieren Sie Ihren Algorithmus als C++-Programm.
- Schätzen Sie ab, ob Hannas Angaben zu den höchstens nötigen Versuchen zutreffen.
Hinweise
Hinweis zu Aufgabe a)
g, was bei k? Woran erkennt man eine widersprüchliche Antwort?Hinweis zu Aufgabe b)
while-Schleife mit der Bedingung antwort != 'r' passt gut; initialisieren Sie antwort vorher mit einem anderen Zeichen. Ein einzelnes Zeichen lesen Sie mit char antwort; cin >> antwort;.Hinweis zu Aufgabe c)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
- Setze
unten= 1,oben= 1000,versuche= 0. - Wiederhole, bis die Antwort
rist:- Ist
unten>oben, gibt es keine passende Zahl mehr: Schummeln melden und beenden. tipp= (unten+oben) / 2 (ganzzahlig);versucheum 1 erhöhen; Tipp ausgeben, Antwort einlesen.- Bei
g:oben=tipp− 1. Beik:unten=tipp+ 1.
- Ist
- Anzahl der Versuche ausgeben.
Wichtig ist das „− 1“ bzw. „+ 1“: Der Tipp selbst ist ja schon ausgeschlossen. Ohne diese Korrektur kann der Computer bei zwei benachbarten Zahlen endlos dasselbe tippen.
Erwartungshorizont zu Aufgabe b)
#include <iostream> using namespace std; int main() { int unten = 1; int oben = 1000; int versuche = 0; char antwort = ' '; cout << "Zahl von 1 bis 1000 merken!" << endl; while (antwort != 'r') { if (unten > oben) { cout << "Geschummelt?" << endl; return 1; } int tipp = (unten + oben) / 2; versuche++; cout << "Ist es " << tipp << "? (g/k/r) "; cin >> antwort; if (antwort == 'g') { oben = tipp - 1; // Zahl ist kleiner } else if (antwort == 'k') { unten = tipp + 1; // Zahl ist groesser } } cout << versuche << " Versuche" << endl; return 0; }
Zahl von 1 bis 1000 merken! Ist es 500? (g/k/r) g Ist es 250? (g/k/r) k Ist es 375? (g/k/r) k Ist es 437? (g/k/r) r 4 Versuche
Das Programm wurde automatisch für alle Zahlen von 1 bis 1000 mit ehrlichen Antworten getestet: Es findet jede Zahl, höchstens nach 10 Versuchen. Bewertet werden: Grenzen richtig angepasst, Zähler, Abbruchbedingung, Schummel-Erkennung.
Erwartungshorizont zu Aufgabe c)
Mit 1 Versuch findet man sicher 1 Zahl, mit 2 Versuchen 3 Zahlen (Mitte, dann links oder rechts), mit 3 Versuchen 7 Zahlen — allgemein mit \(k\) Versuchen \(2^k - 1\) Zahlen.
1 bis 1000: \(2^9 - 1 = 511 < 1000\), aber \(2^{10} - 1 = 1023 \ge 1000\). Also reichen 10 Versuche immer, 9 nicht immer. (Der Test aus b) bestätigt das Maximum 10.)
1 bis 1 000 000: \(2^{20} - 1 = 1\,048\,575 \ge 1\,000\,000\) und \(2^{19} - 1 = 524\,287\) ist zu wenig. Also 20 Versuche.
Hanna hat recht. Eine Verdopplung des Bereichs kostet nur einen Versuch mehr; tausendmal so viele Zahlen (\(\approx 2^{10}\)) nur etwa zehn Versuche mehr.