Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:algorithmen:binaere_suche:zahlenraten:start [26.06.2020 15:50] – [Ein besseres Verfahren] sbel
+++ faecher:informatik:oberstufe:algorithmen:binaere_suche:zahlenraten:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== Zahlenraten ======
-Wir schauen und das "Zahlenraten" Beispiel genauer an:
-|{{:faecher:informatik:oberstufe:algorithmen:binaere_suche:numbers.jpg?400|}} | **Zahlenraten**: Deine Freundin denkt sich eine zahl zwischen 1 und 100, du musst die Zahl mit möglichst wenigen Versuchen erraten. Die Freundin sage dir jeweils, ob die geratene Zahl zu groß, zu klein oder richtig ist.|
-| ((Photo by  https://unsplash.com/@drew_beamer))||
-===== Der Reihe nach raten =====
-Ziel ist natürlich, die Zahl mit möglichst wenigen Versuchen zu erraten. Wenn du einfach bei ''1'' beginnst und "hochzählst", ist das allerdings unter Umständen schlecht: Wenn deine Freundin sich die Zahl 100 gedacht hast, rätst du 99 mal falsch. Der **"Worst Case"** für dieses Verfahren (//"Der Reihe nach raten"//) benötigt also 100 Versuche, um die Zahl sicher zu finden.
-Es kann auch mal weniger Versuche benötigen, aber im ungünstigsten Fall - 100 Versuche. Wenn ihr die Spielregeln nun ändert, und die gedachte Zahl zwischen 1 und 10.000 liegen darf, benötigst du mit //"Der Reihe nach raten"// um schlechtesten Fall sogar 10.000 Versuche!
-<WRAP center round tip 75%>
-**Der "schlechteste Fall" wird also mit der Länge der Zahlenlisten immer schlechter.** Das wird uns noch beschäftigen...
-</WRAP>
-{{ .:raten_o_n.png |}}
-===== Ein besseres Verfahren =====
-Zurück zum Beispiel - Zahlen von 1 bis 100. Geschickter wäre es, wenn man als erste Zahl **50** wählen würde, denn damit hat man mit einmal raten **die Hälfte aller Möglichkeiten eliminiert** - erinnert euch daran, dass die Antwortmöglichkeiten der Freundin "zu klein", "zu groß" oder "Treffer" sind. Wenn die gedachte Zahl **89** ist, erhält man die Information "zu klein" und kann alle Zahlen kleiner als 50 ebenfalls als Möglichkeiten ausschließen.
-Im nächsten Schrittt wählt man nun die Mitte der verbleibenden Möglichkeiten, als des Bereichs zwischen 51 und 100 -- 75, und erhält wieder die Rückmeldung "zu klein". Nun weiß man, dass die gesuchte Zahl zwischen 76 und 100 liegt. Und so weiter - das sieht dann so aus:
-{{ :faecher:informatik:oberstufe:algorithmen:binaere_suche:zahlenraten:zraten.png |}}
-**Nach 5 mal Raten weiß man das Ergebnis.**
-----
-[[..:start|Einführung <<<<]] -- **Zahlenraten** -- [[ .:next:start|>>>> NEXT]]