{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Suchen\n", "\n", "Die ersten Algorithmen, mit denen Sie sich auseinandersetzen werden, dienen der Suche nach einem Element in einer Liste.\n", "\n", "---\n", "**Ziele**\n", "\n", "Sie können\n", "* sicher auf Listenelemente zugreifen.\n", "* über Listen *iterieren* (also *darüber loopen*, *Listen mit einer Schleife durchlaufen*).\n", "* die lineare und die binäre Suche mit eigenen Worten beschreiben.\n", "* die lineare Suche implementieren und Ihre Implementation erklären.\n", "* die binäre Suche auf Papier durchgehen und zeigen, dass sie schneller ist als die lineare Suche.\n", "* beurteilen, welcher der beiden Suchalgorithmen sich für eine bestimmte Ausgangslage eignet.\n", "* an einem Beispiel zeigen, dass es sich auch im Falle einfacher Algorithmen lohnen kann, über Optimierungen nachzudenken.\n", "\n", "Ausserdem sollten Sie sehen, dass es sich lohnt, Probleme schrittweise anzugehen. Wenn Sie erst den ganzen Code schreiben, bevor Sie ihn zum ersten Mal ausführen, werden Sie länger nach dem Fehler suchen müssen, falls etwas nicht funktioniert hat, auch wenn Sie die Fehlermeldungen lesen können.\n", "\n", "---\n", "\n", "## Suchspiele\n", "\n", "Um sich mit der Suche von Elementen auseinanderzusetzen, können Sie spielerisch vorgehen. Falls Sie nicht alleine arbeiten, suchen Sie sich eine Partnerin oder einen Partner und probieren Sie die folgenden Spiele aus. Ansonsten überlegen Sie sich kurz, wie Sie vorgehen würden.\n", "\n", "### Schiffe versenken\n", "\n", "Stellen Sie sich eine vereinfachte Form des Spiels \"Schiffe versenken\" in einem Fluss vor. Der Fluss ist in Felder eingeteilt (Sehen Sie die Liste dahinter?) und jedes Schiff hat eine Nummer. Die Nummern sind aber nicht geordnet. Die Schiffe bewegen sich nicht und der Fluss ist in Felder unterteilt (A bis Z). Jede Person hat nun ein Schiff der Länge 1 zur Verfügung. Überlegen Sie sich, wie Sie vorgehen müssen, um das gegnerische Schiff zu finden.\n", "\n", "\n", "| 🚢 83 | 🚢 47 | 🚢 44 | 🚢 72 | 🚢 15 | 🚢 16 | 🚢 12 | 🚢 68 | 🚢 9 | 🚢 58 | 🚢 11 | 🚢 55 | 🚢 78 |\n", "| : | : | : | : | : | : | : | : | : | : | : | : | : |\n", "| A | B | C | D | E | F | G | H | I | J | K | L | M |\n", "\n", "| 🚢 46 | 🚢 93 | 🚢 87 | 🚢 60 | 🚢 35 | 🚢 2 | 🚢 10 | 🚢 4 | 🚢 99 | 🚢 26 | 🚢 70 | 🚢 22 | 🚢 14 |\n", "| : | : | : | : | : | : | : | : | : | : | : | : | : |\n", "| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |\n", "\n", "\n", "\n", "**Variante** \n", "\n", "Nun haben die Schiffe wiederum Nummern. Die Nummern sind aber geordnet. Wie müssten Sie nun vorgehen, um das gegnerische Schiff möglichst schnell zu finden?\n", "\n", "| 🚢 2 | 🚢 4 | 🚢 9 | 🚢 10 | 🚢 11 | 🚢 12 | 🚢 14 | 🚢 15 | 🚢 16 | 🚢 22 | 🚢 26 | 🚢 35 | 🚢 44 |\n", "| : | : | : | : | : | : | : | : | : | : | : | : | : |\n", "| A | B | C | D | E | F | G | H | I | J | K | L | M |\n", "\n", "| 🚢 46 | 🚢 47 | 🚢 55 | 🚢 58 | 🚢 60 | 🚢 68 | 🚢 70 | 🚢 72 | 🚢 78 | 🚢 83 | 🚢 87 | 🚢 93 | 🚢 99 | \n", "| : | : | : | : | : | : | : | : | : | : | : | : | : |\n", "| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |\n", "\n", "\n", "Diese Übung ist inspiriert von [CS Unplugged: Schiffe versenken](https://classic.csunplugged.org/wp-content/uploads/2014/12/CSUnplugged_OS_2015_v3.2.2_AL_Ak-6.pdf) von der Seite zu [Suchalgorithmen](https://classic.csunplugged.org/searching-algorithms/).\n", "\n", "### Wer ist es?\n", "\n", "Wahrscheinlich mögen Sie sich an das Spiel \"Wer ist es\" erinnern, bei dem zwei Spielerinnen oder Spieler je zweimal dieselben Gesichter hatten, einmal als Spielkarten, einmal zum Umklappen. Zu Beginn suchten sich beide Spieler oder Spielerinnen ein Gesicht aus. Die Gesichter hatten Eigenschaften und es galt anhand der Eigenschaften die Auswahl möglichst schnell einzugrenzen, um das Gesicht des Gegners oder der Gegnerin zu finden.\n", "\n", "Je besser die Fragen, desto schneller war die gesuchte Person gefunden. Falls Sie eine Fotoklassenliste haben, lässt sich dieses Spiel schnell realisieren, ansonsten gibt es hier eine Idee aus Emojis, die Sie [herunterladen](./downloads/wer_ist_es.pdf) und ausdrucken können. Viel Spass beim Suchen und Raten.\n", "\n", "\n", "\n", "## Suchalgorithmen\n", "\n", "Die Suchspiele haben gezeigt, dass es verschiedene Strategien gibt, um ein Element in einer Sammlung von Elementen zu finden. Im Spiel \"Wer ist es\" hatten Sie den Blick auf das Ganze und konnten die Gesichter aussortieren, die nicht dem Kriterium entsprachen, das gerade genannt wurde. Dadurch wird die Auswahl immer kleiner. Genauso können Sie auch vorgehen, wenn die Elemente geordnet sind. Das Prinzip, wenn ein Problem immer weiter eingeschränkt wird, nennt man **Teile und Herrsche** (Divide & Conquer). Dieses Prinzip kommt in der Informatik oft zur Anwendung wird Ihnen auch bei den Sortieralgorithmen wieder begegnen.\n", "\n", "Wenn die Elemente nicht geordnet sind oder keine Möglichkeit besteht, das Problem einzugrenzen, wird die Suche mühsamer. Welche Strategie haben Sie bei der ersten Runde Schiffe versenken angewandt? Wahrscheinlich sind Sie die Liste entweder anhand eines Musters durchgegangen (von vorne nach hinten oder umgekehrt oder zuerst von vorne nach hinten jedes zweite Element und dann wieder zurück für die übriggebliebenen Elemente). Vielleicht haben Sie auch zufällig irgendwelche Werte genannt, wobei Sie aufpassen mussten, dass Sie den Überblick behielten und nicht zweimal denselben Wert prüften. Möglicherweise haben Sie mit einer Person gespielt, die Sie sehr gut kennen und haben die Suche dadurch möglicherweise eingegrenzt. Dazu benötigten Sie aber Informationen über die Person. Dies wäre zwar ebenfalls ein Ansatz, um ein Element zu finden, aber einer, der auf künstlicher Intelligenz beruht. So zeigt Ihnen Google beispielsweise die Werbung, die Sie am ehesten interessieren könnte, weil Google Daten zu Ihrem Suchverhalten analysiert hat. Dieser Kurs geht nicht auf diese Art von Algorithmen ein, aber da es immer wieder Schülerinnen und Schüler gibt, die auf diese Weise suchen würden, wird es hier erwähnt.\n", "\n", "Sie sehen also, je nachdem, ob die Daten, die Sie durchsuchen sortiert sind oder nicht, kommen andere Strategien zum Zug. An dieser Ausgangslage lassen sich zwei bekannte Suchalgorithmen zeigen: die lineare Suche und die binäre Suche. Sie werden im Folgenden thematisiert, aber da Sie für beide Suchalgorithmen sicher auf Listenelemente zugreifen und diese mit dem gesuchten Wert vergleichen müssen, machen Sie zuerst eine vorbereitende Übung.\n", "\n", "**Aufgabe 1 – Vorbereitung: Vergleich eines Listenelements mit einem gegebenen Wert** \n", "\n", "Um die Suchalgorithmen zu implementieren, müssen Sie auf Listenelemente zugreifen und deren Inhalte mit dem gesuchten Wert *vergleichen* können.\n", "\n", "Gegeben ist der folgende Code:\n", "\n", "```Python\n", "liste = [2,6,1,8,2,7,0]\n", "gesuchter_wert = 7\n", "```\n", "Sie wollen überprüfen, ob das vierte Element der Liste `liste` gleich dem gesuchten Wert ist. Implementieren Sie dies.\n", "\n", "Hinweis: \n", "Sie müssen den Vergleich nicht verwerten, also keine Verzweigung implementieren. Ihr Vergleich soll lediglich einen Boolean liefern: `True` wenn die beiden Elemente gleich sind gleich sind, `False` wenn sie nicht gleich sind." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "liste = [2,6,1,8,2,7,0]\n", "gesuchter_wert = 7\n", "\n", "# Zugriff aufs vierte Element der Liste liste:\n", "# Ihr Code...\n", "\n", "# Vergleich dieses Elements mit dem gesuchten Wert:\n", "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bei der linearen Suche werden Sie nicht nur irgendein Element der Liste mit dem gesuchten Wert vergleichen wollen, sondern die Liste systematisch durchgehen und jedes Element mit dem gesuchten Wert vergleichen.\n", "\n", "**Aufgabe 2 – Listendurchlauf**\n", "\n", "Gehen Sie die Liste `liste` durch, d.h. machen Sie eine Schleife, welche die Liste durchläuft und den Wert jedes Elements ausgibt: \n", "Index 0 Wert 2 \n", "Index 1 Wert 6\n", "\n", "Es geht hier darum, die Liste durchzugehen und die Elemente der Liste auszugeben." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lineare Suche\n", "\n", "Um ein Element in einer ungeordneten Liste zu finden, muss diese durchlaufen und jedes Element mit dem gesuchten Wert verglichen werden.\n", "\n", "Da dies der erste Algorithmus ist, den Sie implementieren, werden Sie Schritt für Schritt durchgeführt.\n", "\n", "**Aufgabe 3 – Lineare Suche**\n", "\n", "Suchen Sie in einer Liste ein Element.\n", "\n", "a) Erstellen Sie eine Liste `unsortierte_liste`.\n", "* Erstellen Sie zuerst eine Liste, welche die Ganzzahlen von 0 bis 19 enthält." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "b) Mischen Sie nun die Liste mithilfe der Funktion `random.shuffle()` aus dem Modul `random`. \n", "\n", "Vergessen Sie nicht, das Modul `random` zu importieren.\n", "\n", "
\n", " \n", " Hinweis\n", " \n", "\n", "```Python\n", "import random\n", "```\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "c) Grundgerüst der Funktion erstellen.\n", "\n", "Nun bereiten Sie Ihre Funktion für die lineare Suche vor:\n", "\n", "* Erstellen Sie eine Funktion `suche_linear()`. \n", "* Sie nimmt noch keinen Parameter entgegen, wird aber einen Index zurückgeben. \n", "* Jede Funktion braucht einen Funktionskörper. Solange nichts gemacht wird, können Sie einfach nichts zurückgeben:\n", "```Python\n", " return\n", "```\n", "* Rufen Sie Ihre Funktion auf.\n", "\n", "Damit haben Sie das Grundgerüst der Funktion. Sie macht noch nicht viel Gescheites, daru, sehen Sie auch nicht viel." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Wie schnell schleicht sich ein Tippfehler ein oder geht ein Doppelunkt vergessen...* Indem Sie Ihren Code Stück für Stück schreiben und immer wieder ausprobieren ob die einzelnen Teile laufen oder zumindest kompilieren, vermeiden Sie viele Fehler und sind im Endeffekt sicherer.\n", "\n", "d) Erweitern Sie nun Ihre Funktion `suche_linear()`.\n", "\n", "* Wenn das das Element gefunden wird, soll sich die Funktion `suche_linear` den Index in der Variable `index_gefunden` merken. \n", " * Erstellen Sie nun innerhalb Ihrer Funktion diese Variable `index_gefunden` und\n", " * initialisieren Sie sie mit dem Wert `-1`. \n", " Dieser Wert soll zurückgegeben werden, wenn die Suche erfolglos war. \n", " > *Mit dem Wert `-1` codieren Sie das Ergebnis \"nicht gefunden\"*. \n", " > Das ist ein Vorgehen, das beim Programmieren sehr oft zur Anwendung kommt.\n", "* Rufen Sie die Funktion auf, um zu überprüfen, dass sie bereits den Wert `-1` zurückgibt." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "e) Nun wollen Sie die Funktion um den gesuchten Wert einbauen, damit sie für beliebige Suchwerte verwendet werden kann.\n", "\n", "* Erweitern Sie Ihre Funktion `suche_linear` um einen Parameter `wert`, nach dem gesucht werden soll.\n", "* Definieren Sie ausserhalb der Funktion eine Variable `gesuchter_wert`, die den Wert enthält, nach dem gesucht werden soll, zum Beispiel 12.\n", "* Passen Sie den Funktionsaufruf an. Da die Funktion nun den gesuchten Wert als Parameter entgegennimmt, müssen Sie ihn ihr übergeben." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ihre Funktion hat nun den Parameter `wert`, aber sie macht noch nichts damit. Nun können Sie in der Liste `unsortierte_liste` das Element suchen, das den gesuchten Wert aufweist.\n", "\n", "f) Implementieren Sie nun die eigentliche Suche.\n", "\n", "* Die Funktion `suche_linear` soll die ganze Liste `unsortierte_liste` durchgehen und jedes Element mit dem Wert `wert` vergleichen.\n", "\n", "Diesen Schritt haben Sie in Aufgabe 2 und 3 bereits vorbereitet. Versuchen Sie es dennoch selbst, da es hier auch darum geht, den Umgang mit Listen zu üben: wie greifen Sie auf ein Element zu." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "g) Generalisierung\n", "\n", "Nun haben Sie die lineare Suche implementiert. Allerdings muss zwingend eine Liste `unsortierte_liste` definiert sein, sonst greift die Funktion `suche_linear` auf etwas zu, das es nicht gibt. Schöner wäre es, der Funktion auch die Liste `unsortierte_liste` als Parameter zu übergeben.\n", "\n", "Wenn eine Funktion generalisiert ist, nennt man sie auch **generisch**, sie ist dann in verschiedenen Situationen anwendbar.\n", "\n", "* Erweitern Sie Ihre Funktion `unsortierte_liste` um den Parameter `liste`, damit Sie keine Abhängigkeit nach aussen hat. \n", "* Rufen Sie die Funktion `suche_linear(liste, wert)` mit der Liste `unsortierte_liste` und dem wert `gesuchter_wert` auf." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "👍 Sie haben nun die lineare Suche implementiert. 👍\n", "\n", "**Aufgabe 4 – Algorithmus genau beschreiben**\n", "\n", "Um sicherzugehen, dass man einen Algorithmus verstanden hat, lohnt es sich immer, ihn in eigenen Worten zu beschreiben. Beschreiben Sie die lineare Suche deshalb in eigenen Worten so genau wie möglich." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Nutzen Sie diese Zelle für Ihre Antwort." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Optimierung\n", "\n", "Stellen Sie sich vor, in der Liste, in der Sie suchen, kommt der gesuchte Wert mehrmals vor. So wie die Suche nun implementiert ist, gibt die Funktion das letzte Vorkommen des gesuchten Werts aus. Die anderen Indizes werden jeweils überschrieben, wenn ein neues Vorkommen des Wertes gefunden wird. Sie haben nun zwei Möglichkeiten: Entweder Sie merken sich alle Vorkommen oder Sie beenden die Suche nach dem ersten Vorkommen. Oft hat die Suche den Zweck zu schauen, ob ein Wert überhaupt in einer Liste vorkommt.\n", "\n", "Sie können hier davon ausgehen, dass es reicht, das erste Vorkommen zu finden. Sobald ein Element gefunden wird, kann die Suche abgebrochen werden. Da Ihre Funktion einen Wert zurückgibt, reicht es, die Rückgabe gleich zu machen, sobald der Wert gefunden wurde. Damit wird die Funktion verlassen und die weiteren Elemente bis zum Ende der Liste brauchen nicht mehr verglichen zu werden.\n", "\n", "**Aufgabe 5 – Lineare Suche optimiert**\n", "\n", "Implementieren Sie nun diese Optimierung in einer neuen Funktion `suche_linear_optimiert`.\n", "\n", "* Sobald in der Liste ein Element gefunden wurde, das den gesuchen Wert aufweist, soll der Index zurückgegeben werden.\n", "* Überlegen Sie sich, ob Sie die Variable `index_gefunden` noch brauchen und inwiefern Sie den Code ändern müssten, um ohne sie auszukommen." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Challenge – Zeitmessungen mit dem Modul time**\n", "\n", "Mit Hilfe der Funktion `time.time()` des Moduls time lassen sich Zeitstempel abfragen. Sie können sich vorstellen, dass Sie am Anfang des zu messenden Bereichs einen Timer stellen und am Ende schauen, wieviel Zeit vergangen ist. Dazu rufen Sie zweimal (am Anfang und am Ende des zu messenden Bereichs) die Funktion `time.time()` auf und ermitteln die Differenz dieser beiden Werte.\n", "Das Modul time bietet noch andere zeitbezogene Funktionen.\n", "\n", "Beispiel:\n", "\n", "Um die Zeitmessung zu demonstrieren, wird die Funktion `time.sleep(d)` verwendet, wobei `d` der Dauer der *Wartezeit* in Sekunden entspricht.\n", "Der Startwert wird in die Variable startzeitpunkt gespeichert, dann wird in einer Schleife zehnmal eine Sekunde lang gewartet und anschliessend wird der aktuelle Wert in die Variable endzeitpunkt gespeichert. Die Differenz der beiden Werte entspricht der vergangenen Dauer in Sekunden und wird ausgegeben.\n", "Da im Beispiel zehnmal eine Sekunde gewartet wird, liegt die Ausgabe leicht über zehn Sekunden." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import time\n", "\n", "# Startzeitpunkt erfassen:\n", "startzeitpunkt = time.time()\n", "\n", "for i in range(10):\n", " time.sleep(1) \n", " \n", "# Endzeitpunkt erfassen:\n", "endzeitpunkt = time.time()\n", " \n", "print(\"Benötigte Zeit in Sekunden:\", (endzeitpunkt - startzeitpunkt)) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* Erstellen Sie sich nun geeignete Listen (auf- und absteigend sortiert, zufällig), wenden Sie die lineare Suche darauf an und machen Sie Zeitmessungen mit dem Modul time.\n", "* Um einen Effekt zu sehen, müssen Sie eine sehr lange Liste machen (100000 Elemente)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Binäre Suche\n", "\n", "In einer geordneten (sortierten) Liste lässt sich ein Element deutlich schneller finden, da der Suchbereich nach dem Prinzip *Teile und Herrsche* immer mehr **eingegrenzt** werden kann, bis das gesuchte Element gefunden ist.\n", "\n", "Wenn Sie von einer aufsteigend sortierten Liste ausgehen, gibt es für jeden Vergleich drei Möglichkeiten:\n", "* Der Wert des Elements ist **gleich** dem gesuchten Wert: \n", " Sie haben das Element **gefunden** und sind **fertig**.\n", "* Der Wert des Elements ist **kleiner** als der gesuchte Wert: \n", " Sie können das Element und alle Elemente des unteren Teils der Liste ausschliessen und sich auf den oberen Teil konzentrieren.\n", "* Der Wert des Elements ist **grösser** als der gesuchte Wert: \n", " Sie können das Element und alle Elemente oberhalb ausschliessen und sich auf die untere Seite der Liste konzentrieren.\n", "\n", "Überlegen Sie sich kurz, welches Element Sie wählen würden, um jeweils einen möglichst grossen Teil der Liste verwerfen zu können.\n", "\n", "
\n", " \n", " Lösung\n", " \n", "\n", "Wie Sie bestimmt geahnt haben, werden Sie das Element in der Mitte der Liste wählen, um jeweils einen mögichst grossen Teil der Liste verwerfen zu können.\n", "\n", "
\n", "\n", "**Aufgabe 6 – Algorithmus beschreiben**\n", "\n", "Schreiben Sie die binäre Suche in Pseudocode oder erklären Sie in eigenen Worten, wie der Algorithmus funktioniert.\n", "\n", "Schauen Sie sich [die Animation auf der Seite der Universität San Francisco](https://www.cs.usfca.edu/~galles/visualization/Search.html) an, falls Sie Mühe haben, sich vorzustellen, wie die binäre Suche genau funktioniert.\n", "\n", "**Challenge – Binäre Suche**\n", "\n", "Versuchen Sie sich an die Schritte zu halten, die Sie ans Ziel führen. Falls Sie die Challenge in Angriff nehmen möchten, nur zu. Ansonsten können Sie jederzeit hierher zurück kommen.\n", "\n", "* Für diese Liste können Sie eine aufsteigende Liste erstellen oder eine solche wiederverwenden, wenn Sie weiter oben bereits eine gemacht haben.\n", "* Wie bereits im Falle der linearen Suche soll der Wert `-1` ausgegeben werden, wenn kein Element mit dem gesuchten Wert in der Liste enthalten ist.\n", "* kennzeichnen Sie die Ränder des Listenteils, in dem Sie noch suchen mit den Variablen `links` und `rechts`.\n", "* Überprüfen Sie am Anfang, ob der gesuchte Wert in der Liste enthalten ist (dann muss er innerhalb des Bereichs von `links` bis und mit `rechts` sein).\n", "* Nachdem Sie überprüft haben, dass das Element vom Wert her in der Liste enthalten sein kann. können Sie mit der eigentlichen Suche beginnen:\n", " * Um sicherzustellen, dass nicht nur einmal gesucht wird, brauchen Sie eine Schleife, die so lange ausgeführt wird, wie mehr als ein Element in der Teilliste enthalten ist.\n", " * Wenn das Element nicht gefunden wird, können Sie es zum linken oder rechten Rand der übrigbleibenden Suchliste machen." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Optimierung**\n", "\n", "Eine kleine Optimierung können Sie hier noch vornehmen. Da die Liste sortiert ist, können Sie am Anfang prüfen, ob Ihr Wert überhaupt in der Liste sein kann.\n", "\n", "Ergänzen Sie die Funktion `suche_binaer` um die entsprechende Abfrage." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* Zählen Sie nun, wie oft aufgeteilt wurde. \n", " \n", "* **Extra-Challenge**: Sehen Sie hinter der maximalen Anzahl Aufteilungen eine Gesetzmässigkeit? Versuchen Sie die maximale Anzahl Aufteilungen formal auszudrücken." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* **Testen** Sie Ihre Lösung.\n", "\n", "Um in der Softwareentwicklung die Qualität sicherzustellen, wird am Ende der Entwicklung getestet.\n", "\n", "Ihre Lösung sollten Sie testen mit\n", "* einem Wert, der sich in der Liste befindet. \n", " Erwarteter Rückgabewert: der korrekte Index des gesuchten Elements.\n", "* einem Wert, der sich nicht in der Liste befindet. \n", " Erwarteter Rückgabewert: `-1`\n", "* einem Wert, der sich ausserhalb des Wertebereichs der Liste befindet. \n", " Erwarteter Rückgabewert: `-1`\n", "* den Randwerten der Liste (erster und letzter Wert der Liste) \n", " Erwartete Rückgabewerte: `0` und `len(liste)-1`" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Quiz\n", "\n", "Alles klar?\n", "\n", "Sie sollten nun die beiden Suchalgorithmen in eigenen Worten beschreiben und Ihre Implementation der linearen Suche erklären können.\n", "\n", "Testen Sie Ihr Verständnis anhand der Fragen, die erstellt werden, wenn Sie die folgenden Zellen gemäss Ihrer Umgebung ausführen.\n", "\n", "### NUR FALLS SIE AUF GOOGLE COLAB ARBEITEN\n", "\n", "Führen Sie bitte die **beiden** folgenden Zellen aus, um die Bibliothek für das Quiz zu laden." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# NUR falls Sie AUF GOOGLE COLAB arbeiten:\n", "# Führen Sie diese Zelle aus, um das Quiz zu sehen.\n", "\n", "%%writefile quizclone.py\n", "import os\n", "from subprocess import getoutput\n", "getoutput(\"git clone -l -s https://github.com/donze-informatikunterricht/quiz.git cloned-repo\")\n", "os.chdir('cloned-repo')\n", "print('repo cloned successfully')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# NUR falls Sie AUF GOOGLE COLAB arbeiten:\n", "# Führen Sie diese Zelle aus, um das Quiz zu sehen.\n", "\n", "import quizclone" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Quiz erstellen (unabhängig von Ihrer Arbeitsumgebung)\n", "\n", "Nun können Sie das Quiz erstellen. Führen Sie dazu bitte die folgende Zelle aus.\n", "\n", "Teile des Quiz basieren auf dem folgenden Programm:\n", "\n", "```python\n", "import random\n", "\n", "a = [57, 57, 57, 57, 57, 57, 57, 57, 57, 57]\n", "b = [0, 6, 12, 18, 24, 30, 36, 42, 48, 54]\n", "c = [24, 89, 83, 57, 84, 10, 31, 72, 88, 73]\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from IPython.display import display\n", "import quiz\n", "\n", "display(quiz.Q1_suchen)\n", "display(quiz.Q2_suchen)\n", "display(quiz.Q3_suchen)\n", "display(quiz.Q4_suchen)\n", "display(quiz.Q5_suchen)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Abschluss: Suchtänze\n", "\n", "Nun haben Sie sich mit der linearen Suche und der Binären Suche auseinandergesetzt. \n", "\n", "Sehr empfehlenswert für Such- und Sortieralgorithmen ist der [YouTube-Kanal AlgoRythmics](https://www.youtube.com/channel/UCIqiLefbVHsOAXDAxQJH7Xw), der Algorithmen in Form von Tänzen präsentiert.\n", "\n", "Führen Sie die beiden folgenden Zellen aus, um die Tänze zur Linearen und Binären Suche sehen zu können." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Führen Sie diese Zelle aus, um den Videoclip sehen zu können.\n", "\n", "import IPython\n", "\n", "IPython.display.IFrame(src=\"https://www.youtube.com/embed/-PuqKbu9K3U\", width=560, height=315)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "IPython.display.IFrame(src=\"https://www.youtube.com/embed/iP897Z5Nerk\", width=560, height=315)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.8" } }, "nbformat": 4, "nbformat_minor": 4 }