Suchen mit System: Struktogramm und Zahlenraten

Lösung geprüft

Die Aufgabe der heutigen Stunde ist Suchen mit System, Teil 1! Zwei Aufgaben: einmal ein Struktogramm für eine Methode, die Sechser zählt, und einmal Zahlenraten zu zweit – letzteres ist die binäre Suche, nur dass es noch niemand so nennt.

Die Aufgabenstellung lautet

Aufgabe 1 b) Rechnerarbeit: Gegeben ist die Dokumentation der Methode int anzahlSechser(). Die Simulation hat 30 zufällige Würfelergebnisse erzeugt. Die Methode zählt die Sechser unter den Ergebnissen zusammen. Return: die Anzahl aller Sechser. Parameter: –. Entwerfen Sie ein Struktogramm für die Methode. Nehmen Sie die Fachmethode „Struktogramme" zu Hilfe. Implementieren und testen Sie in Java.

Aufgabe 2 Partnerarbeit: Spielen Sie zu zweit das Spiel Zahlenraten. Spieler A denkt sich eine Zahl aus einem zuvor festgelegten Bereich aus. Spieler B versucht mit möglichst wenigen Versuchen, die gedachte Zahl zu erraten. Nach jedem Versuch sagt Spieler A, ob die geratene Zahl zu klein, zu groß oder die richtige ist.

a) Spielen Sie mehrere Runden mit den Zahlbereichen 1–10, 1–20, 1–100 und 1–1000 und notieren Sie die Anzahl der benötigten Rateversuche.
b) Analysieren Sie Ihre Ergebnisse aus a), indem Sie eine Berechnungsformel für die maximale Anzahl an Rateversuchen entwickeln. Die Formel soll angeben, wie viele Versuche höchstens bei einem Zahlbereich mit n Zahlen benötigt werden.

Aufgabe 1 – Sechser zählen

Das Struktogramm

Struktogramm

+----------------------------------------------+
| int anzahlSechser()                          |
+----------------------------------------------+
| int anzahl = 0                               |
+----------------------------------------------+
|   for i = 0 to laenge(wuerfelergebnisse) - 1 |
|  +-----------------------------------------+ |
|  |        wuerfelergebnisse[i] == 6 ?      | |
|  | WAHR                          FALSCH    | |
|  +---------------------+-------------------+ |
|  | anzahl = anzahl + 1 |         (leer)    | |
|  +---------------------+-------------------+ |
+----------------------------------------------+
| return anzahl                                |
+----------------------------------------------+

Drei Bausteine, mehr braucht es nicht: eine Zuweisung am Anfang, eine Zählschleife, darin eine Verzweigung, und am Ende die Rückgabe. Die Verzweigung hat nur einen WAHR-Zweig – im FALSCH-Zweig steht nichts, weil bei einer 3 eben nichts zu tun ist. Im Struktogramm markiert man das mit dem leeren Kasten oder einem ø.

In Java

Wuerfelsimulation.java

/* meininfokurs.cmrg.site */

/**
 *
 * Sechser zaehlen in der Wuerfelsimulation
 *
 * @version 1.0 vom 14.09.2025
 * @meininfokurs.cmrg.site
 */

public class Wuerfelsimulation {

    private int[] wuerfelergebnisse = new int[30];

    public void wuerfeln() {
        for (int i = 0; i < wuerfelergebnisse.length; i++) {
            wuerfelergebnisse[i] = (int)(Math.random() * 6 + 1);
        }
    }

    /**
     * Zaehlt die Sechser unter den 30 Wuerfelergebnissen.
     *
     * @return Anzahl aller Sechser
     */
    public int anzahlSechser() {
        int anzahl = 0;
        for (int i = 0; i < wuerfelergebnisse.length; i++) {
            if (wuerfelergebnisse[i] == 6) {
                anzahl++;
            }
        }
        return anzahl;
    }

    public static void main(String[] args) {
        Wuerfelsimulation w = new Wuerfelsimulation();
        w.wuerfeln();
        System.out.println("Sechser: " + w.anzahlSechser() + " von 30");
    } // end of main

} // end of class Wuerfelsimulation

Zwei Kleinigkeiten, an denen man hängenbleibt. Erstens: anzahl wird vor der Schleife auf 0 gesetzt, nicht darin. Setzt du sie innerhalb, fängt sie bei jedem Durchlauf wieder bei 0 an und am Ende steht dort immer 0 oder 1.

Zweitens: es heißt == und nicht =. Ein einzelnes Gleichheitszeichen ist eine Zuweisung – damit würdest du jeden Würfel auf 6 setzen statt ihn zu vergleichen. Bei int-Werten meckert der Compiler immerhin, weil eine Zuweisung kein boolean ergibt.

Zum Testen: bei 30 Würfen sollten im Schnitt 5 Sechser rauskommen, denn 30 · 1/6 = 5. Schwankungen zwischen 1 und 10 sind völlig normal. Kommt bei dir immer 0 oder immer 30 raus, stimmt was nicht.

Aufgabe 2 – Zahlenraten

a) Die beste Strategie

Wer beim Zahlenraten bei 1 anfängt und hochzählt, braucht bei 1–1000 im schlimmsten Fall 1000 Versuche. Das ist die lineare Suche und sie ist hier eine ziemlich schlechte Idee.

Die gute Strategie: immer die Mitte raten. Bei 1–100 fängt man mit 50 an. „Zu klein" heißt, die Zahl liegt zwischen 51 und 100 – der halbe Bereich fällt mit einem Versuch weg. Dann rät man 75 und so weiter. Das ist die binäre Suche.

Bereich	n	Versuche höchstens
1–10	10	4
1–20	20	5
1–100	100	7
1–1000	1000	10

b) Die Formel

Schau dir die Zahlen an: der Bereich wird hundertmal so groß (von 10 auf 1000), die Versuche steigen aber nur von 4 auf 10. Das ist das typische Zeichen für einen Logarithmus.

Bei jedem Versuch halbiert sich der Bereich. Nach k Versuchen sind von n Zahlen noch n / 2^k übrig. Man ist fertig, wenn nur noch eine übrig ist:

n / 2^k = 1        | · 2^k
n       = 2^k      | log2
log2(n) = k

Da man keine halben Versuche machen kann, wird aufgerundet:

Anzahl der Versuche (hoechstens) = aufgerundet( log2(n + 1) )

Probe: log2(11) ≈ 3,46 → aufgerundet 4. Stimmt mit der Tabelle überein. log2(1001) ≈ 9,97 → 10. Stimmt auch.

Praktisch kann man das auch ohne Taschenrechner abschätzen: 2¹⁰ ist 1024, also reichen 10 Versuche für alles bis 1000. Die Zweierpotenzen bis 2¹⁰ auswendig zu können hilft im Info-Unterricht ständig.

Warum das so wichtig ist

Der Vergleich mit der linearen Suche ist heftig, und genau deshalb ist die ganze Einheit so aufgebaut:

n	Linear (schlimmster Fall)	Binär (schlimmster Fall)
10	10	4
1 000	1 000	10
1 000 000	1 000 000	20

Eine Million Einträge, und man ist nach 20 Fragen fertig. Der Haken kommt später: das funktioniert nur, wenn die Daten sortiert sind. Beim Zahlenraten sind sie das automatisch, weil Zahlen nun mal eine Reihenfolge haben.