Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:suchen_und_sortieren:binaersuche [2026-05-02 12:14] – [Aufgabe B4: Binäre Suche für 079] hof
+++ gf_informatik:suchen_und_sortieren:binaersuche [2026-05-02 12:30] (aktuell) – [Aufgabe B8: Rekursion (optional)] hof
@@ Zeile 184: / Zeile 184: @@
 </template>
 </bottom-exercise>
 #### Aufgabe B5: Zeitmessung mit linearer und binärer Suche
-Vergleiche die lineare Suche mit der binären Suche. Hierzu kannst du von Aufgabe B4 ausgehen (unter neuem Namen speichern):
-  - Behalte nur die Listen und die Definition der Funktion `binary_search()`.
-  - Ergänze die Datei um die Funktion `linear_search(l, v)` (am besten, du schreibst du sie selbst hin, anstatt sie zu kopieren).
-  - Definiere eine neue Funktion `stopwatch(algo, name)`. Sie hat zwei Argumente:
-    - `algo` ist der Name der Suchfunktion (Suchalgorithmus), die verwendet werden soll (also `binary_search` oder `linear_search`, ohne die Klammern des Funktionsaufrufs).
-    - `name` ist der Name, nach dem gesucht werden soll.
-  - Die Funktion soll mit dem gewünschten Algorithmus im Telefonbuch suchen und die Zeit für die Suche messen (`import time`, siehe auch Aufgabe A5). Am Ende soll die Funktion einen Text in folgender Form ausgeben: "Die Telefonnummer von ... lautet .... Die Suche dauerte ... Sekunden."
-  - Rufe nun die Funktion vier mal auf: Für `Annina` und `Lyanna` – jeweils mit der linearen und mit der binären Suche.
-<nodisp 1>
+<bottom-exercise id="b5" timeout="120" zip="https://bottom.ch/ksr/1m/null79.py.zip" showsolution>
-++++Lösung|
+<div slot="prompt">
-<bottom-editor timeout="180" zip="https://bottom.ch/ksr/1m/null79.py.zip">
+Vergleiche die lineare Suche mit der binären Suche. Hierzu kannst du von Aufgabe B4 ausgehen:
+<ul>
+  <li>Behalte nur die Listen und die Definition der Funktion <code>binary_search()</code>.
+  <li>Ergänze die Datei um die Funktion <code>linear_search(l, v)</code> (am besten, du schreibst du sie selbst hin, anstatt sie zu kopieren).
+  <li>Definiere eine neue Funktion <code>stopwatch(algo, name)</code>. Sie hat zwei Argumente:
+  <ul>
+    <li><code>algo</code> ist der Name der Suchfunktion (Suchalgorithmus), die verwendet werden soll (also <code>binary_search</code> oder <code>linear_search</code>, ohne die Klammern des Funktionsaufrufs).
+    <li><code>name</code> ist der Name, nach dem gesucht werden soll.
+    </ul>
+  <li>Die Funktion soll mit dem gewünschten Algorithmus im Telefonbuch suchen und die Zeit für die Suche messen (<code>import time</code>, siehe auch Aufgabe A5). Am Ende soll die Funktion einen Text in folgender Form ausgeben: "Die Telefonnummer von ... lautet .... Die Suche dauerte ... Sekunden."
+  <li>Rufe nun die Funktion vier mal auf: Für <code>Annina</code> und <code>Lyanna</code> – jeweils mit der linearen und mit der binären Suche.
+</ul>
+</div>
+<template data-type="starter">
+from null79 import names, numbers
+def binary_search(l, v):
+    """Gibt den Index des gesuchten Elements in l zurück, None,
+       wenn das Element nicht existiert."""
+    # TODO implementieren
+def linear_search(l, v):
+    """Gibt den Index des gesuchten Elements in l zurück, None,
+       wenn das Element nicht existiert."""
+    # TODO implementieren
+def stopwatch(algo, name):
+    """Ruft die Funktion algo auf und misst die Zeit der Ausführung."""
+stopwatch(binary_search, 'Annina')
+</template>
+<template data-type="solution">
 from null79 import names, numbers
 import time
@@ Zeile 237: / Zeile 259: @@
 stopwatch(linear_search, 'Lyanna')
 stopwatch(binary_search, 'Lyanna')
-</bottom-editor>
+</template>
-++++
+</bottom-exercise>
-</nodisp>
@@ Zeile 293: / Zeile 315: @@
 ++++
 </nodisp>
 #### Aufgabe B8: Rekursion (optional)
+<bottom-exercise id="b8" timeout="5" zip="https://bottom.ch/ksr/1m/null79.py.zip" showsolution>
+<div slot="prompt">
 Bei der binären Suche gehen wir ja wie folgt vor:
-  - Index in der Mitte des Suchintervalls wählen.
+<ul>
-  - Element in der Mitte auslesen.
+  <li>Index in der Mitte des Suchintervalls wählen.
-  - Ist `element == suche` sind wir fertig.
+  <li>Element in der Mitte auslesen.
-  - Andernfalls wiederholen wir die Suche mit einem kleineren Teilintervall (zurück zu Schritt 1):
+  <li>Ist <code>element == suche</code> sind wir fertig.
-    - Ist `suche < element`, so ist das neue Suchintervall die linke Hälfte.
+  <li>Andernfalls wiederholen wir die Suche mit einem kleineren Teilintervall (zurück zu Schritt 1):
-    - Andernfalls ist `element < suche`, das neue Suchintervall ist die rechte Hälfte.
+    <ul>
+      <li>Ist <code>suche &lt; element</code>, so ist das neue Suchintervall die linke Hälfte.
+      <li>Andernfalls ist <code>element &lt; suche</code>, das neue Suchintervall ist die rechte Hälfte.
+    </ul>
+</ul>
-Schreibe eine neue Funktion, `binaere_suche_rekursiv(l, suche, links, rechts)`. Die Funktion codiert die obigen Schritte - statt einer `while`-Schleife soll die Funktion sich im Schritt 4 selber wieder aufrufen. Dieses Verfahren heisst **Rekursion**. Was sind die Startparameter für `links` und `rechts`?
+<p>Schreibe eine neue Funktion, <code>binaere_suche_rekursiv(l, suche, links, rechts)</code>. Die Funktion codiert die obigen Schritte &ndash; statt einer <code>while</code>-Schleife soll die Funktion sich im Schritt 4 selber wieder aufrufen. Dieses Verfahren heisst <strong>Rekursion</strong>. Was sind die Startparameter für <code>links</code> und <code>rechts</code>?
-Rekursion eignet sich für viele Probleme, die sich mit _Divide & Conquer_ (_Teile & Herrsche_) lösen lassen: Probleme, die wir für den trivialen Fall mit einem Element lösen können, und die wir effizient von einem grösseren in ein kleineres Problem überführen können.
+<p>Rekursion eignet sich für viele Probleme, die sich mit <em>Divide &amp; Conquer</em> (<em>Teile &amp; Herrsche</em>) lösen lassen: Probleme, die wir für den trivialen Fall mit einem Element lösen können, und die wir effizient von einem grösseren in ein kleineres Problem überführen können.
+</div>
+<template data-type="starter">
+from null79 import names, numbers
+def binaere_suche_rekursiv(l, suche, links=None, rechts=None):
+    """Gibt den Index des gesuchten Elements in l zurück,
+       None, wenn das Element nicht existiert."""
+</template>
+<template data-type="test">
+assert binaere_suche_rekursiv(names, 'Lyanna', links=0, rechts=len(names)) >= 0
+assert binaere_suche_rekursiv(names, 'Lyanna') >= 0, "Aufruf ohne links / rechts sollte auch funktionieren"
+</template>
+<template data-type="solution">
+from null79 import names, numbers
-<nodisp 1>
-++++Lösung|
-<bottom-editor timeout="180" zip="https://bottom.ch/ksr/1m/null79.py.zip">
 def binaere_suche_rekursiv(l, suche, links=None, rechts=None):
     """Gibt den Index des gesuchten Elements in l zurück,
@@ Zeile 339: / Zeile 378: @@
 from null79 import names, numbers
 print(f'Die Telefonummer von Lyanna ist {numbers[binaere_suche_rekursiv(names, "Lyanna")]}.')
-</bottom-editor>
+</template>
-++++
+</bottom-exercise>
-</nodisp>