Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:binaere_suche:zahlenraten:start [26.06.2020 12:58] – [Ein besseres Verfahren] sbel
+++ faecher:informatik:oberstufe:algorithmen:binaere_suche:zahlenraten:start [30.01.2025 06:45] (aktuell) – [Einfache Suche: Der Reihe nach raten] Frank Schiebel
@@ Zeile 6: / Zeile 6: @@
 | ((Photo by  https://unsplash.com/@drew_beamer))||
-===== Der Reihe nach raten =====
+===== Einfache Suche: Der Reihe nach raten =====
@@ Zeile 18: / Zeile 18: @@
-{{ .:raten_o_n.png |}}
+{{ .:raten_o_n.drawio.png |}}
 ===== Ein besseres Verfahren =====
-Zurück zum Beispiel - Zahlen von 1 bis 100.
+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.**
+Wäre die gedachte Zahl 87 gewesen, hätte man das Ergebnis schon nach 3 Schritten gehabt (man kann auch immer mal Glück haben) - aber wie lange hätte es höchstens gedauert? Hier hilft es, sich klarzumachen, wieviele Zahlen nach jedem Rateversuch bei diesem Verfahren noch als Kandidaten im Rennen sind, ohne an eine spezielle Zahl zu denken:
+{{ :faecher:informatik:oberstufe:algorithmen:binaere_suche:zahlenraten:maxtries.png |}}
+<WRAP center round todo 75%>
+Beim Erraten einer Zahl zwischen 1 und 100 benötigt man also allerhöchstens 7 Versuche, wenn man nach dem beschriebenen Verfahren -- **der binären Suche** -- vorgeht!
+</WRAP>
+===== Aufgaben =====
+  * **(1)** Nach wievielen Rateversuchen ist man im schlechtesten Fall erfolgreich, wenn man eine Zahl zwischen 1 und 10.000 mit der binären Suche erraten möchte. Schätze zuerst, überlege dann.
+  * **(2)** Du suchst in einem Wörterbuch mit 320.000 Wörtern nach einem zufälligen Begriff. Wieviele Schritte benötigst du im ungünstigsten Fall mit der **einfachen Suche** (der Reihe nach) und der **binären Suche**?
+  * **(3)** Wie viele Versuche benötigt man bei der binären Suche in einer sortierten Liste mit ''n'' Elementen allgemein im schlechtesten Fall, um das gesuchte Element zu finden?
+  * **(4)** Erkläre, warum die binäre Suche in unsortierten Listen nicht funktionieren kann.
 ----
-[[..:start|Einführung <-]] -- [[.:zahlenraten:start|Zahlenraten]] -- [[ .:next:start|-> NEXT]]
+[[..:start|Einführung <<<<]] -- **Zahlenraten** -- [[ ..:binsuchprogramm:start|>>>> Ein Programm]]