Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:binaere_suche:zahlenraten:start [26.06.2020 13:50] – [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 |}}
@@ Zeile 29: / Zeile 29: @@
 {{ :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** -- [[ .:next:start|>>>> NEXT]]
+[[..:start|Einführung <<<<]] -- **Zahlenraten** -- [[ ..:binsuchprogramm:start|>>>> Ein Programm]]