{
"cells": [
{
"cell_type": "markdown",
"id": "a81d9ad2-9a47-4872-bf65-5a8dfb09c32f",
"metadata": {
"tags": [
"chapter_search"
]
},
"source": [
"# Kapitel 7: Iteration und Suche\n",
"[Chapter 7: Iteration and Search](https://colab.research.google.com/github/AllenDowney/ThinkPython/blob/v3/chapters/chap07.ipynb)\n",
"\n",
"Im Jahr 1939 veröffentlichte Ernest Vincent Wright einen Roman mit 50.000 Wörtern namens *Gadsby*, in dem der Buchstabe \"e\" kein einziges Mal vorkommt. Da \"e\" der am häufigsten verwendete Buchstabe der englischen Sprache ist, ist es schwierig auch nur ein paar wenige Worte zu schreiben, ohne ihn zu verwenden.\n",
"Um ein Gefühl dafür zu bekommen, wie schwierig es wäre, werden wir in diesem Kapitel den Anteil an englischen Wörtern berechnen, die mindestens ein \"e\" enthalten.\n",
"\n",
"Dafür werden wir `for`-Anweisungen verwenden, um die Buchstaben in einer Zeichenkette und Wörter aus einer Datei in einer Schleife durchzugehen. Wir werden zudem Variablen in einer Schleife aktualisieren, um die Anzahl der Wörter, die ein \"e\" enthalten zu ermitteln.\n",
"Wir werden den `in`-Operator verwenden, um zu überprüfen, ob ein Buchstabe in einem Wort vorkommt und ein Programmiermuster namens **lineare Suche** (Englisch: *linear search*) kennenlernen.\n",
"\n",
"Als Übung werden Sie mithilfe dieser Werkzeuge ein Worträtsel namens \"Spelling Bee\" lösen."
]
},
{
"cell_type": "markdown",
"id": "2cb6856d-271f-4e44-9eed-c635facb29e9",
"metadata": {},
"source": [
"## Ihre Lernziele\n",
"Sie können eine Übersicht der Inhalte dieses Notebooks einblenden mit *Strg + Shift + k*. \n",
"\n",
"Beschreiben Sie in 2-3 Stichpunkten kurz was Sie im Seminar heute lernen wollen. Klicken Sie dazu doppelt auf diesen Text und bearbeiten Sie dann den Text:\n",
"\n",
"- \n",
"- \n",
"- \n"
]
},
{
"cell_type": "markdown",
"id": "2595a027-7ad2-431f-b59d-9285a6b912a4",
"metadata": {},
"source": [
"## Exkurs: Was mir an Python gefällt\n",
"\n",
"In dieser Rubrik, die immer am Anfang eines Kapitels steht, möchte ich Ihnen zeigen, wofür ich Python nutze und warum ich es mag. Sie werden vielleicht noch nicht verstehen, was ich genau mache, aber Sie sehen damit schon einmal die Möglichkeiten von Python und können später darauf zurückgreifen. Da dies auch ein Exkurs ist, können Sie diese Rubrik gerne auch erst einmal überspringen.\n",
"\n",
"Mit den Operatoren aus diesem Kapitel können wir ganz leicht das Verfahren zur Umwandlung einer Dezimalzahl in ihre Binärdarstellung implementieren:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f3a8a7bf-351e-4f37-a9d1-237fa492de7a",
"metadata": {},
"outputs": [],
"source": [
"# Umwandlung einer positiven, ganzen Dezimalzahl in Binärdarstellung (als Zeichenkette)\n",
"def dez_zu_bin(n):\n",
" ergebnis = \"\"\n",
" while n > 0:\n",
" ergebnis = str(n % 2) + ergebnis\n",
" n = n // 2\n",
" return ergebnis\n",
"\n",
"print(dez_zu_bin(42))\n",
"\n",
"# Und weil wir heute beim Thema Rekursion sind ...\n",
"def dez_zu_bin_rekursiv(n):\n",
" if n == 0:\n",
" return \"\"\n",
" return dez_zu_bin_rekursiv(n // 2) + str(n % 2)\n",
"\n",
"print(dez_zu_bin_rekursiv(42))\n",
"\n",
"# Warum eigentlich auf ein Zahlensystem festlegen?\n",
"def dez_zu_allem(n, s):\n",
" if n == 0:\n",
" return \"\"\n",
" return dez_zu_allem(n // len(s), s) + s[n % len(s)]\n",
"\n",
"print(dez_zu_allem(42, \"01\"))\n",
"print(dez_zu_allem(42, \"0123456789\"))\n",
"print(dez_zu_allem(42, \"01234567\"))\n",
"print(dez_zu_allem(42, \"0123456789ABCDEF\"))\n",
"print(dez_zu_allem(42, \"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\"))"
]
},
{
"cell_type": "markdown",
"id": "dd4b77e1-9c25-4b41-aadc-aa5662fc6c9e",
"metadata": {},
"source": [
"## Herunterladen des unterstützenden Codes\n",
"Die folgende Zelle lädt eine Datei herunter und führt einen Code aus, der speziell für dieses Notebook verwendet wird. Sie müssen diesen Code nicht verstehen, aber Sie sollten die Zelle vor allen weiteren Zellen in diesem Notebook ausführen."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f0c8eb18",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"from os.path import basename, exists\n",
"\n",
"def download(url):\n",
" filename = basename(url)\n",
" if not exists(filename):\n",
" from urllib.request import urlretrieve\n",
"\n",
" local, _ = urlretrieve(url, filename)\n",
" print(\"Downloaded \" + str(local))\n",
" return filename\n",
"\n",
"download('https://github.com/AllenDowney/ThinkPython/raw/v3/thinkpython.py');\n",
"download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');\n",
"\n",
"import thinkpython"
]
},
{
"cell_type": "markdown",
"id": "389f5162-0a8c-4cc7-99f1-a261e0b39006",
"metadata": {},
"source": [
"## Schleifen und Zeichenketten\n",
"\n",
"In Kapitel 3 haben wir eine `for`-Schleife gesehen, die die `range`-Funktion verwendet, um eine Abfolge von Zahlen anzuzeigen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6b8569b8-1576-45d2-99f6-c7a2c7e100c4",
"metadata": {},
"outputs": [],
"source": [
"for i in range(3):\n",
" print(i, end=' ')"
]
},
{
"cell_type": "markdown",
"id": "937a0af9-5486-4195-8e59-6f819db1cf3f",
"metadata": {},
"source": [
"Diese Version nutzt das Schlüsselwort-Argument `end`, damit die `print`-Funktion ein Leerzeichen nach jede Zahl setzt, statt (mit dem `newline`-Zeichen) eine neue Zeile zu beginnen.\n",
"\n",
"Wir können eine `for`-Schleife auch verwenden, um die Buchstaben einer Zeichenkette darzustellen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6cb5b573-601c-42f5-a940-f1a4d244f990",
"metadata": {},
"outputs": [],
"source": [
"for letter in 'Gadsby':\n",
" print(letter, end=' ')"
]
},
{
"cell_type": "markdown",
"id": "72044436-ed85-407b-8821-9696648ec29c",
"metadata": {},
"source": [
"Beachten Sie hier, dass ich den Namen der Variable von `i` zu `letter` abgeändert habe, um auf diese Weise zusätzliche Informationen über den Wert, auf den die Variable verweist zu übermitteln.\n",
"Die in einer `for`-Schleife definierte Variable wird **Schleifen-Variable** (Englisch: *loop variable*) genannt.\n",
"\n",
"Jetzt wo wir uns in einer Schleife durch die einzelnen Buchstaben eines Wortes arbeiten können, können wir auch überprüfen, ob es den Buchstaben \"e\" enthält."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7040a890-6619-4ad2-b0bf-b094a5a0e43d",
"metadata": {},
"outputs": [],
"source": [
"for letter in \"Gadsby\":\n",
" if letter == 'E' or letter == 'e':\n",
" print('This word has an \"e\"')"
]
},
{
"cell_type": "markdown",
"id": "644b7df2-4528-48d9-a003-2d21fbefbaab",
"metadata": {},
"source": [
"Bevor wir weitermachen, sollten wir diese Schleife in eine Funktion verkapseln:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "40fd553c-693c-4ffc-8e49-1d7de3c4d4a7",
"metadata": {},
"outputs": [],
"source": [
"def has_e():\n",
" for letter in \"Gadsby\":\n",
" if letter == 'E' or letter == 'e':\n",
" print('This word has an \"e\"')"
]
},
{
"cell_type": "markdown",
"id": "31cfacd9-5721-457a-be40-80cf002723b2",
"metadata": {},
"source": [
"Außerdem wollen wir sie zu einer reinen Funktion (Englisch: *pure function*) machen, die `True`zurückgibt, wenn das Wort ein \"e\" enthält, sowie `False` in allen anderen Fällen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8a34174b-5a77-482a-8480-14cfdff16339",
"metadata": {},
"outputs": [],
"source": [
"def has_e():\n",
" for letter in \"Gadsby\":\n",
" if letter == 'E' or letter == 'e':\n",
" return True\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "8f45502e-6db3-4fcc-802c-c97398787dbd",
"metadata": {},
"source": [
"Wir können die Funktion verallgemeinern, sodass sie das Wort als Parameter aufnimmt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0909121d-5218-49ca-b03e-258206f00e40",
"metadata": {},
"outputs": [],
"source": [
"def has_e(word):\n",
" for letter in word:\n",
" if letter == 'E' or letter == 'e':\n",
" return True\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "590f4399-16d3-4f1c-93bc-b1fe7ce46633",
"metadata": {},
"source": [
"Jetzt können wir sie so testen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3c4d8138-ddf6-46fe-a940-a7042617ceb1",
"metadata": {},
"outputs": [],
"source": [
"has_e('Gadsby')"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5c463051-b737-49ab-a1d7-4be66fd8331f",
"metadata": {},
"outputs": [],
"source": [
"has_e('Emma')"
]
},
{
"cell_type": "markdown",
"id": "8adf1e92-435e-4b54-837a-bad603ebcafd",
"metadata": {},
"source": [
"## Die Wortliste lesen\n",
"\n",
"Um zu sehen, wie viele Wörter ein \"e\" enthalten, brauchen wir eine Wortliste.\n",
"Die Liste, die wir verwenden werden besteht aus etwa 114.000 offiziellen Kreuzwörtern, also Wörtern, die für Kreuzworträtsel und andere Spiele mit Wörtern als gültig angesehen werden."
]
},
{
"cell_type": "markdown",
"id": "0e3d1c79-5436-42ac-9e29-82fc59936263",
"metadata": {
"tags": [
"remove-cell"
]
},
"source": [
"Die folgende Zelle lädt die Wortliste herunter, diese ist eine modifizierte Variante einer Liste, die von Grady Ward als Teil des *Moby lexicon project* zusammengestellt und der Öffentlichkeit zu Verfügung gestellt wurde (siehe <http://wikipedia.org/wiki/Moby_Project>):"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a7b7ac52-64a6-4dd9-98f5-b772a5e0f161",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');"
]
},
{
"cell_type": "markdown",
"id": "5b383a3c-d173-4a66-bf86-23b329032004",
"metadata": {},
"source": [
"Die Wortliste befindet sich in einer Datei namens `words.txt`, die im Notebook für dieses Kapitel heruntergeladen wird.\n",
"Um sie zu lesen werden wir die eingebaute Funktion `open` verwenden, die die Namen der Dateien als Parameter aufnimmt und ein **Dateiobjekt** (Englisch: *file object*) zurückgibt, das wir zum Lesen der Datei verwenden können:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1ad13ce7-99be-4412-8e0b-978fe6de25f2",
"metadata": {},
"outputs": [],
"source": [
"file_object = open('words.txt')"
]
},
{
"cell_type": "markdown",
"id": "4414d9b1-cb8e-472e-818c-0555e29b1ad5",
"metadata": {},
"source": [
"Das Dateiobjekt stellt eine Funktion namens `readline` zur Verfügung, die die Zeichen aus der Datei liest, bis sie ein `newline`-Zeichen erreicht und gibt anschließend das Ergebnis als Zeichenkette zurück:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "dc2054e6-d8e8-4a06-a1ea-5cfcf4ccf1e0",
"metadata": {},
"outputs": [],
"source": [
"file_object.readline()"
]
},
{
"cell_type": "markdown",
"id": "d74e9fe9-117e-436a-ade3-3d08dfda2a00",
"metadata": {},
"source": [
"Ihnen fällt sicher auf, dass die Syntax für den Aufruf von `readline` anders ist, als für andere Funktionen, die wir bisher gesehen haben. Das liegt daran, dass es eine **Methode** (Englisch: *method*) ist, also eine Funktion, die mit einem Objekt assoziiert ist.\n",
"In diesem Fall ist `readline` mit dem Dateiobjekt assoziiert, wir rufen es also auf, indem wir den *Namen des Objekts*, den *`Punkt`-Operator* (Englisch: *dot operator*) und den *Namen der Methode* verwenden.\n",
"\n",
"Das erste Wort in der List ist \"aa\", was das englische Wort für eine Art von Lava ist.\n",
"Die Zeichenfolge `\\n` repräsentiert das `newline`-Zeichen, das dieses Wort vom nächsten trennt.\n",
"\n",
"Das Dateiobjekt merkt sich, wo es sich in der Datei befindet, wenn wir `readline` erneut aufrufen, erhalten wir also das nächste Wort:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "eaea1520-0fb3-4ef3-be6e-9e1cdcccf39f",
"metadata": {},
"outputs": [],
"source": [
"line = file_object.readline()\n",
"line"
]
},
{
"cell_type": "markdown",
"id": "cd466fdb-38ce-4e5b-92c7-05dc23922005",
"metadata": {},
"source": [
"Um das `newline`-Zeichen vom Ende des Wortes zu entfernen, können wir `strip`verwenden, eine Methode, die mit Zeichenketten assoziiert wird und so aufgerufen werden kann:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f602bfb6-7a93-4fb8-ade6-6784155a6f1a",
"metadata": {},
"outputs": [],
"source": [
"word = line.strip()\n",
"word"
]
},
{
"cell_type": "markdown",
"id": "c56d0dfb-4c0a-4fd2-9664-ea599193011c",
"metadata": {},
"source": [
"`strip` entfernt Whitespace-Zeichen, also Zeichen wie Leerzeichen, Einrückungszeichen und `newline`-Zeichen, die sich am Anfang oder Ende einer Zeichenkette befinden.\n",
"\n",
"Wir können ein Dateiobjekt auch als Teil einer `for`-Schleife verwenden.\n",
"Dieses Programm liest `words.txt` und gibt jedes einzelne Wort mit `print`aus, eines pro Zeile:\n",
"\n",
"**Hinweis: Wenn die Ausgabe erfolgt ist, können Sie die Ausgabe-Box verkleinern indem Sie links neben die Wörter klicken.**"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "cf3b8b7e-5fc7-4bb1-b628-09277bdc5a0d",
"metadata": {
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"for line in open('words.txt'):\n",
" word = line.strip()\n",
" print(word)"
]
},
{
"cell_type": "markdown",
"id": "93e320a5-4827-487e-a8ce-216392f398a8",
"metadata": {},
"source": [
"Jetzt wo wir die Wortliste lesen können, ist der nächste Schritt, sie zu zählen.\n",
"Hierfür brauchen wir die Fähigkeit, **Variablen zu aktualisieren** (Englisch: *to update variables*)."
]
},
{
"cell_type": "markdown",
"id": "b63a6877",
"metadata": {},
"source": [
"## Variablen aktualisieren\n",
"\n",
"Wie Sie vielleicht schon herausgefunden haben, ist es erlaubt, mehr als nur eine Zuweisung an die selbe Variable durchzuführen. Durch eine neue Zuweisung verweist eine existierende Variable auf einen neuen Wert (und nicht mehr auf den alten Wert).\n",
"\n",
"Hier ist zum Beispiel eine Erstzuweisung, die eine Variable erschafft:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6bf8a104",
"metadata": {},
"outputs": [],
"source": [
"x = 5\n",
"x"
]
},
{
"cell_type": "markdown",
"id": "c9735982",
"metadata": {},
"source": [
"Und hier ist eine Zuweisung, die den Wert einer Variable ändert:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0fe7ae60",
"metadata": {},
"outputs": [],
"source": [
"x = 7\n",
"x"
]
},
{
"cell_type": "markdown",
"id": "fbcd1092-ce06-47fc-9204-fce1c9a100a5",
"metadata": {},
"source": [
"Die folgende Abbildung zeigt, wie diese Zuweisungen in einem Zustandsdiagramm (Englisch: *state diagram*) aussehen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8a09bc24",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"from diagram import make_rebind, draw_bindings\n",
"\n",
"bindings = make_rebind('x', [5, 7])"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "36a45674-7f41-4850-98f1-2548574ce958",
"metadata": {
"tags": [
"remove-input"
]
},
"outputs": [],
"source": [
"from diagram import diagram, adjust\n",
"\n",
"width, height, x, y = [0.54, 0.61, 0.07, 0.45]\n",
"ax = diagram(width, height)\n",
"bbox = draw_bindings(bindings, ax, x, y)\n",
"# adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "cd963fbd-923f-405b-964d-00dd93c6fb80",
"metadata": {},
"source": [
"Der gepunktete Pfeil zeigt, dass `x` nicht mehr auf `5` verweist.\n",
"Der durchgezogene Pfeil gibt an, dass es jetzt auf `7` verweist."
]
},
{
"cell_type": "markdown",
"id": "54763b7c-c0f1-4b7e-bbbf-c0f8676c6a9c",
"metadata": {},
"source": [
"An dieser Stelle wollen wir auf eine häufige Ursache für Verwechslungen hinweisen: Da Python das Gleichheitszeichen (`=`) für die Zuweisung verwendet, ist es verlockend, eine Anweisung wie `a = b` wie eine mathematische Aussage der Gleichheit zu interpretieren, das heißt, die Behauptung, dass `a` und `b` gleich seien. Aber diese Interpretation ist falsch! \n",
"\n",
"Zum Einen ist Gleichheit im Gegensatz zur Zuweisung eine symmetrische Beziehung. Beispielsweise gilt in der Mathematik: wenn $a=7$, dann ist auch $7=a$. Aber in Python ist die Anweisung `a = 7` erlaubt, `7 = a` ist es nicht. \n",
"\n",
"Zum Anderen ist in der Mathematik eine Aussage über die Gleichheit entweder wahr oder falsch und gilt durchgängig. Wenn $a = b$ jetzt gilt, dann wird $a$ stets gleich $b$ sein. In Python kann eine Zuweisung zwei Variablen gleich machen, sie müssen aber nicht durchgängig gleich bleiben:\n"
]
},
{
"cell_type": "markdown",
"id": "10e10039-5292-4acb-aa55-ff2881386b92",
"metadata": {},
"source": [
"Eine übliche Art der Neuzuweisung ist eine **Aktualisierung** (Englisch: *update*), bei der der neue Wert vom alten Wert abhängt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ba2ab90b",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"x = 7"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "88496dc4",
"metadata": {},
"outputs": [],
"source": [
"x = x + 1\n",
"x"
]
},
{
"cell_type": "markdown",
"id": "d3025706",
"metadata": {},
"source": [
"Das bedeutet \"nimm den aktuellen Wert von `x`, füge `1` hinzu und aktualisiere dann `x` mit dem neuen Wert\".\n",
"\n",
"Wenn wir versuchen eine Variable zu aktualisieren, die nicht existiert, erhalten wir einen Fehler, denn Python evaluiert die rechte Seite der Zuweisung bevor es den Wert der Variablen auf der linken Seite zuweist:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4a0c46b9",
"metadata": {
"tags": [
"raises-exception"
]
},
"outputs": [],
"source": [
"%%expect NameError\n",
"\n",
"z = z + 1"
]
},
{
"cell_type": "markdown",
"id": "1b8b7f14-d0aa-496f-8f8d-97e975caeb0c",
"metadata": {},
"source": [
"Bevor wir eine Variable aktualisieren können, müssen wir sie **initialisieren**, (Englisch: *initialize*) typischerweise mittels einer Zuweisung:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2220d826",
"metadata": {},
"outputs": [],
"source": [
"z = 0\n",
"z = z + 1\n",
"z"
]
},
{
"cell_type": "markdown",
"id": "374fb3d5",
"metadata": {},
"source": [
"Das Aktualisieren einer Variable mittels Addition der Zahl `1` wird **inkrementieren** (Englisch: *increment*) genannt, das Subtrahieren einer `1` **dekrementieren** (Englisch: *decrement*).\n",
"\n",
"Weil diese Operationen so häufig verwendet werden, stellt Python dafür **erweiterte Zuweisungs-Operatoren** (Englisch: *augmented assignment operators*) zur Verfügung, die eine Variable auf präzisere Weise aktualisieren\n",
"Der `+=`-Operator inkrementiert eine Variable zum Beispiel um den angegebenen Betrag:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d8e1ac5a",
"metadata": {},
"outputs": [],
"source": [
"z += 2\n",
"z"
]
},
{
"cell_type": "markdown",
"id": "3f4eedf1",
"metadata": {},
"source": [
"Es gibt erweiterte Zuweisungs-Operatoren für weitere arithmetische Operatoren, unter anderem `-=` und `*=`."
]
},
{
"cell_type": "markdown",
"id": "6f481809-c5b7-4dd7-bb1f-edfa151808af",
"metadata": {},
"source": [
"\n",
"\n",
"([Footnote Labyrinths](https://xkcd.com/1208/), Randall Munroe) [Erklärung des Comics](https://www.explainxkcd.com/wiki/index.php/1208:_Footnote_Labyrinths) falls Sie mehr wissen möchten."
]
},
{
"cell_type": "markdown",
"id": "70eeef60-6a34-403a-96bb-aa5c4574a5fe",
"metadata": {},
"source": [
"## Schleifen und Zählen\n",
"\n",
"Das folgende Programm zählt die Menge an Worten in der Wortliste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0afd8f88",
"metadata": {},
"outputs": [],
"source": [
"total = 0\n",
"\n",
"for line in open('words.txt'):\n",
" word = line.strip()\n",
" total += 1"
]
},
{
"cell_type": "markdown",
"id": "9bd83ddd",
"metadata": {},
"source": [
"Es beginnt damit, `total` mit `0` zu initialisieren.\n",
"Bei jedem Schleifendurchlauf wird `total` um `1` inkrementiert.\n",
"Wenn die Schleife verlassen wird, bezieht sich `total` also auf die Gesamtzahl an Wörtern:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8686b2eb-c610-4d29-a942-2ef8f53e5e36",
"metadata": {},
"outputs": [],
"source": [
"total"
]
},
{
"cell_type": "markdown",
"id": "54904394",
"metadata": {},
"source": [
"Eine Variable wie diese, die verwendet wird um zu zählen wie oft etwas passiert, nennt man **Zähler** (Englisch: *counter*).\n",
"\n",
"Wir können dem Programm einen zweiten Zähler hinzufügen, um die Anzahl an Wörtern zu erfassen, die ein \"e\" enthalten:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "89a05280",
"metadata": {},
"outputs": [],
"source": [
"total = 0\n",
"count = 0\n",
"\n",
"for line in open('words.txt'):\n",
" word = line.strip()\n",
" total = total + 1\n",
" if has_e(word):\n",
" count += 1"
]
},
{
"cell_type": "markdown",
"id": "ab73c1e3",
"metadata": {},
"source": [
"Lasst uns überprüfen, wie viele Wörter ein \"e\" enthalten:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9d29b5e9",
"metadata": {},
"outputs": [],
"source": [
"count"
]
},
{
"cell_type": "markdown",
"id": "d2262e64",
"metadata": {},
"source": [
"Der Anteil aller Wörter, die ein \"e\" enthalten beträgt im Verhältnis zur Gesamtmenge an Wörtern `total` etwa zwei Drittel:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "304dfd86",
"metadata": {},
"outputs": [],
"source": [
"count / total * 100"
]
},
{
"cell_type": "markdown",
"id": "fe002dde",
"metadata": {},
"source": [
"Jetzt sollten Sie in der Lage sein zu verstehen, warum es so schwierig ist, ein Buch ohne diese Wörter zu verfassen."
]
},
{
"cell_type": "markdown",
"id": "632a992f",
"metadata": {},
"source": [
"## Der `in`-Operator\n",
"\n",
"Die Version von `has_e`, die wir in diesem Kapitel geschrieben haben ist unnötig kompliziert.\n",
"Python bietet einen Operator, `in`, der überprüft, ob ein Zeichen in einer Zeichenkette vorkommt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fe6431b7",
"metadata": {},
"outputs": [],
"source": [
"word = 'Gadsby'\n",
"'e' in word"
]
},
{
"cell_type": "markdown",
"id": "ede36fe9",
"metadata": {},
"source": [
"Also können wir `has_e` so umschreiben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "85d3fba6",
"metadata": {},
"outputs": [],
"source": [
"def has_e(word):\n",
" if 'E' in word or 'e' in word:\n",
" return True\n",
" else:\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "f86f6fc7",
"metadata": {},
"source": [
"Und da die Bedingung der `if`-Anweisung einen Booleschen Wert hat, können wir die `if`-Anweisung weglassen und den Booleschen Wert direkt zurückgeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2d653847",
"metadata": {},
"outputs": [],
"source": [
"def has_e(word):\n",
" return 'E' in word or 'e' in word"
]
},
{
"cell_type": "markdown",
"id": "f2a05319",
"metadata": {},
"source": [
"Wir können diese Funktion sogar noch weiter vereinfachen, indem wir die Methode `lower` verwenden, die die Buchstaben in einer Zeichenkette in Kleinbuchstaben umwandelt.\n",
"Hier ist ein Beispiel:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a92a81bc",
"metadata": {},
"outputs": [],
"source": [
"word.lower()"
]
},
{
"cell_type": "markdown",
"id": "57aa625a",
"metadata": {},
"source": [
"`lower` erstellt eine neue Zeichenkette -- die bestehende Zeichenkette wird nicht verändert -- so dass der Wert von `word` unverändert bleibt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d15f83a4",
"metadata": {},
"outputs": [],
"source": [
"word"
]
},
{
"cell_type": "markdown",
"id": "9f0bd075",
"metadata": {},
"source": [
"So können wir `lower` in `has_e` verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e7958af4",
"metadata": {},
"outputs": [],
"source": [
"def has_e(word):\n",
" return 'e' in word.lower()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "020a57a7",
"metadata": {},
"outputs": [],
"source": [
"has_e('Gadsby')"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0b979b20",
"metadata": {},
"outputs": [],
"source": [
"has_e('Emma')"
]
},
{
"cell_type": "markdown",
"id": "1c39cb6b",
"metadata": {},
"source": [
"## Suche\n",
"\n",
"Basierend auf dieser einfacheren Version von `has_e` schreiben wir nun eine allgemeinere Funktion namens `has_any`, die als einen zweiten Parameter eine Zeichenkette aus Buchstaben aufnimmt.\n",
"Wenn das Wort irgendeinen der Buchstaben enthält gibt sie `True`zurück, wenn nicht `False`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bd29ff63",
"metadata": {},
"outputs": [],
"source": [
"def uses_any(word, letters):\n",
" for letter in word.lower():\n",
" if letter in letters.lower():\n",
" return True\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "dc2d6290",
"metadata": {},
"source": [
"Hier ist ein Beispiel mit dem Ergebnis `True`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9369fb05",
"metadata": {},
"outputs": [],
"source": [
"uses_any('banana', 'aeiou')"
]
},
{
"cell_type": "markdown",
"id": "2c3c1553",
"metadata": {},
"source": [
"Und hier eines mit dem Ergebnis `False`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "eb32713a",
"metadata": {},
"outputs": [],
"source": [
"uses_any('apple', 'xyz')"
]
},
{
"cell_type": "markdown",
"id": "b2acc611",
"metadata": {},
"source": [
"`uses_any` wandelt `word` und `letters` in Kleinbuchstaben um, daher funktioniert die Funktion mit jeder Kombination von Groß- und Kleinbuchstaben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7e65a9fb",
"metadata": {},
"outputs": [],
"source": [
"uses_any('Banana', 'AEIOU')"
]
},
{
"cell_type": "markdown",
"id": "673786a5",
"metadata": {},
"source": [
"Die Struktur von `uses_any` ist ähnlich wie die von `has_e`.\n",
"Die Funktion läuft in einer Schleife durch die Buchstaben von `word` und prüft sie einzeln nacheinander.\n",
"Wenn sie einen findet, der in `letters` vorkommt, gibt sie sofort `True` zurück.\n",
"Wenn sie die Schleife ganz durchläuft, ohne einen zu finden, gibt sie `False` zurück.\n",
"\n",
"Dieses Muster nennt man **lineare Suche** (Englisch: *linear search*).\n",
"In den Übungen am Ende dieses Kapitels werden Sie weitere Funktionen schreiben, die diesem Muster folgen."
]
},
{
"cell_type": "markdown",
"id": "62cdb3fc",
"metadata": {},
"source": [
"## Doctest\n",
"\n",
"In [Chapter 4](section_docstring) haben wir einen Docstring verwendet, um eine Funktion zu dokumentieren -- also um zu erklären, was sie tut.\n",
"Es ist aber auch möglich, einen Docstring zu verwenden, um eine Funktion zu *testen*.\n",
"Hier ist eine Version von `uses_any` mit einem Docstring, die Tests beinhaltet:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3982e7d3",
"metadata": {},
"outputs": [],
"source": [
"def uses_any(word, letters):\n",
" \"\"\"Überprüft, ob ein Wort einen der Buchstaben einer Liste beinhaltet.\n",
" \n",
" >>> uses_any('banana', 'aeiou')\n",
" True\n",
" >>> uses_any('apple', 'xyz')\n",
" False\n",
" \"\"\"\n",
" for letter in word.lower():\n",
" if letter in letters.lower():\n",
" return True\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "2871d018",
"metadata": {},
"source": [
"Jeder Test beginnt mit `>>>>`, was in manchen Python-Umgebungen als Eingabeaufforderung verwendet wird, um anzuzeigen, wo der/die Benutzer$*$in Code eingeben kann.\n",
"In einem Doctest folgt auf die Eingabeaufforderung ein Ausdruck, normalerweise ein Funktionsaufruf.\n",
"Die darauffolgende Zeile gibt den Wert an, den der Ausdruck haben sollte, wenn die Funktion korrekt funktioniert.\n",
"\n",
"Im ersten Beispiel beinhaltet `banana` den Buchstaben `a`, also sollte das Ergebnis `True` sein.\n",
"Im zweiten Beispiel, `apple`, kommt keiner der Buchstaben `'xyz'` vor, also sollte das Ergebnis `False` sein.\n",
"\n",
"Um diese Tests durchführen zu können müssen wir das `Doctest`-Modul importieren und eine Funktion namens `run_docstring_examples` laufen lassen.\n",
"Um die Verwendung dieser Funktion einfacher zu machen, habe ich folgende Funktion geschrieben, die ein Funktionsobjekt als Argument aufnimmt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "40ef00d3",
"metadata": {},
"outputs": [],
"source": [
"from doctest import run_docstring_examples\n",
"\n",
"def run_doctests(func):\n",
" run_docstring_examples(func, globals(), name=func.__name__)"
]
},
{
"cell_type": "markdown",
"id": "79e3de21",
"metadata": {},
"source": [
"Über `globals` und `__name__` haben wir noch nichts gelernt - Sie können diese daher ignorieren.\n",
"Jetzt können wir `uses_any` wie folgt testen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f37cfd36",
"metadata": {},
"outputs": [],
"source": [
"run_doctests(uses_any)"
]
},
{
"cell_type": "markdown",
"id": "432d8c31",
"metadata": {},
"source": [
"`run_doctests` findet die Ausdrücke im Docstring und evaluiert diese.\n",
"Wenn das Ergebnis der erwartete Wert ist, gilt der Test als **bestanden** (Englisch: *pass*)\n",
"Andernfalls ist er **fehlgeschlagen** (Englisch: *fail*).\n",
"\n",
"Wenn alle Tests bestanden werden, zeigt `run_doctests` keinen Output an -- in diesem Fall sind keine Nachrichten gute Nachrichten.\n",
"Um zu sehen was passiert, wenn ein Test fehlschlägt, ist hier eine inkorrekte Version von `uses_any`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "58c916cc",
"metadata": {},
"outputs": [],
"source": [
"def uses_any_incorrect(word, letters):\n",
" \"\"\"Überprüft, ob ein Wort einen der Buchstaben einer Liste beinhaltet.\n",
" \n",
" >>> uses_any_incorrect('banana', 'aeiou')\n",
" True\n",
" >>> uses_any_incorrect('apple', 'xyz')\n",
" False\n",
" \"\"\"\n",
" for letter in word.lower():\n",
" if letter in letters.lower():\n",
" return True\n",
" else:\n",
" return False # INCORRECT!"
]
},
{
"cell_type": "markdown",
"id": "34b78be4",
"metadata": {},
"source": [
"Und hier ist was passiert, wenn wir diese testen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7a325745",
"metadata": {},
"outputs": [],
"source": [
"run_doctests(uses_any_incorrect)"
]
},
{
"cell_type": "markdown",
"id": "473aa6ec",
"metadata": {},
"source": [
"Der Output enthält das fehlgeschlagene Beispiel, den Wert, den die Funktion eigentlich erwartungsgemäß produzieren sollte und den Wert, der tatsächlich herausgekommen ist.\n",
"\n",
"Wenn Sie sich nicht sicher sind, warum dieser Test fehlgeschlagen ist, können sie ihn als Übung debuggen."
]
},
{
"cell_type": "markdown",
"id": "382c134e",
"metadata": {},
"source": [
"## Glossar\n",
"\n",
"Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 7 gelernt haben:\n",
"\n",
"- Schleifen-Variable:\n",
"- Dateiobjekt:\n",
"- Methode:\n",
"- aktualisieren:\n",
"- initialisieren:\n",
"- inkrementieren:\n",
"- dekrementieren:\n",
"- erweiterte Zuweisungs-Operatoren:\n",
"- Zähler:\n",
"- lineare Suche:\n"
]
},
{
"cell_type": "markdown",
"id": "0a2b3510-e8d3-439b-a771-a4a58db6ac59",
"metadata": {},
"source": [
"## Übung"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bc58db59",
"metadata": {
"tags": [
"remove-print"
]
},
"outputs": [],
"source": [
"# Diese Zelle weist Jupyter an, detallierte Debugging-Informationen auszugeben, wenn ein Laufzeitfehler\n",
"# passiert. Lassen Sie sie daher laufen, bevor Sie beginnen an den Aufgaben zu arbeiten.\n",
"\n",
"%xmode Verbose"
]
},
{
"cell_type": "markdown",
"id": "8e8606b8-9a48-4cbd-a0b0-ea848666c77d",
"metadata": {},
"source": [
"### Fragen Sie einen virtuellen Assistenten\n",
"\n",
"In `uses_any` ist Ihnen vielleicht aufgefallen, dass die erste `return`-Anweisung sich in der Schleife und die zweite sich außerhalb der Schleife befindet:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6b3cdf6a-0e90-4a98-b0f1-ab95dd195ca7",
"metadata": {},
"outputs": [],
"source": [
"def uses_any(word, letters):\n",
" for letter in word.lower():\n",
" if letter in letters.lower():\n",
" return True\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "e1920737-b485-4823-ac20-c1e35aa93e7f",
"metadata": {},
"source": [
"Es ist ein üblicher Fehler, beim ersten Schreiben solcher Funktionen beide `return`-Anweisungen in die Schleife zu setzen, wie in diesem Beispiel:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7cbb72b1",
"metadata": {},
"outputs": [],
"source": [
"def uses_any_incorrect(word, letters):\n",
" for letter in word.lower():\n",
" if letter in letters.lower():\n",
" return True\n",
" else:\n",
" return False # INCORRECT!"
]
},
{
"cell_type": "markdown",
"id": "d9b46591-6c80-4ff8-9378-e9318ce5e429",
"metadata": {},
"source": [
"Fragen Sie einen virtuellen Assistenten, was mit dieser Version falsch ist."
]
},
{
"cell_type": "markdown",
"id": "99eff99e",
"metadata": {},
"source": [
"### Aufgabe 1\n",
"\n",
"Schreiben Sie eine Funktion namens `uses_none`, die ein Wort und eine Zeichenkette mit verbotenen Buchstaben aufnimmt und `True` zurückgibt, wenn das Wort keinen der verbotenen Buchstaben verwendet.\n",
"\n",
"Hier ist ein Entwurf der Funktion, der zwei Doctests enthält.\n",
"Befüllen Sie die Funktion so, dass sie diese beiden Tests besteht und fügen Sie noch mindestens einen weiteren Doctest hinzu."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6c825b80",
"metadata": {},
"outputs": [],
"source": [
"def uses_none(word, forbidden):\n",
" \"\"\"Checks whether a word avoid forbidden letters.\n",
" \n",
" >>> uses_none('banana', 'xyz')\n",
" True\n",
" >>> uses_none('apple', 'efg')\n",
" False\n",
" \"\"\"\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "86a6c2c8",
"metadata": {},
"outputs": [],
"source": [
"# implementieren Sie hier"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2bed91e7",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"run_doctests(uses_none)"
]
},
{
"cell_type": "markdown",
"id": "9465b09f-0c62-49f6-bbe2-365ecf1717ef",
"metadata": {},
"source": [
"### Aufgabe 2\n",
"\n",
"Schreiben Sie eine Funktion namens `uses_only`, die ein Wort und eine Zeichenkette aufnimmt und `True` zurückgibt, wenn das Wort nur Buchstaben aus der Zeichenkette enthält.\n",
"\n",
"Hier ist ein Entwurf der Funktion, der zwei Doctests enthält.\n",
"Befüllen Sie die Funktion so, dass sie diese beiden Tests besteht und fügen Sie noch mindestens einen weiteren Doctest hinzu."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d0d8c6d6",
"metadata": {},
"outputs": [],
"source": [
"def uses_only(word, available):\n",
" \"\"\"Checks whether a word uses only the available letters.\n",
" \n",
" >>> uses_only('banana', 'ban')\n",
" True\n",
" >>> uses_only('apple', 'apl')\n",
" False\n",
" \"\"\"\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "31de091e",
"metadata": {},
"outputs": [],
"source": [
"# implementieren Sie hier"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8c5133d4",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"run_doctests(uses_only)"
]
},
{
"cell_type": "markdown",
"id": "74259f36",
"metadata": {},
"source": [
"### Aufgabe 3\n",
"\n",
"Schreiben Sie eine Funktion namens `uses_all`, die ein Wort und eine Zeichenkette aufnimmt und `True` zurückgibt, wenn das Wort alle Buchstaben der Zeichenkette mindestens einmal enthält.\n",
"\n",
"Hier ist ein Entwurf der Funktion, der zwei Doctests enthält.\n",
"Befüllen Sie die Funktion so, dass sie diese beiden Tests besteht und fügen Sie noch mindestens einen weiteren Doctest hinzu."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "18b73bc0",
"metadata": {},
"outputs": [],
"source": [
"def uses_all(word, required):\n",
" \"\"\"Checks whether a word uses all required letters.\n",
" \n",
" >>> uses_all('banana', 'ban')\n",
" True\n",
" >>> uses_all('apple', 'api')\n",
" False\n",
" \"\"\"\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5c8be876",
"metadata": {},
"outputs": [],
"source": [
"# implementieren Sie hier"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ad1fd6b9",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"run_doctests(uses_all)"
]
},
{
"cell_type": "markdown",
"id": "7210adfa",
"metadata": {},
"source": [
"### Aufgabe 4\n",
"\n",
"*The New York Times* veröffentlicht jeden Tag ein Rätsel namens \"Spelling Bee\", das Leser$*$innen herausfordert, so viele englische Wörter wie möglich aus nur sieben vorgegebenen Buchstaben zusammenzusetzen, wobei ein bestimmter Buchstaben zwingend vorkommen muss.\n",
"Die Wörter müssen mindestens vier Buchstaben haben.\n",
"\n",
"An dem Tag, an dem ich das hier geschrieben habe waren die Buchstaben zum Beispiel `ACDLORT`, mit dem `R` als verpflichtendem Buchstaben.\n",
"Also ist hier \"color\" ein zulässiges Wort, \"told\" aber nicht, weil kein `R` darin vorkommt und \"rat\" ebenfalls nicht, weil es nur drei Buchstaben hat.\n",
"Buchstaben können wiederholt werden, \"ratatat\" ist also zulässig.\n",
"\n",
"Schreiben Sie eine Funktion namens `check_word`, die überprüft, ob ein Wort zulässig ist.\n",
"Sie sollte als Parameter das zu kontrollierende Wort, eine Zeichenkette von sieben verfügbaren Buchstaben und eine Zeichenkette mit dem einzelnen verpflichtenden Buchstaben aufnehmen.\n",
"Sie können hierfür die Funktionen verwenden, die Sie für die vorherigen Übungen geschrieben haben.\n",
"\n",
"Hier ist ein Entwurf der Funktion, der Doctests enthält. Befüllen Sie die Funktion und überprüfen sie dann, ob alle Tests bestanden werden."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "576ee509",
"metadata": {},
"outputs": [],
"source": [
"def check_word(word, available, required):\n",
" \"\"\"Check whether a word is acceptable.\n",
" \n",
" >>> check_word('color', 'ACDLORT', 'R')\n",
" True\n",
" >>> check_word('ratatat', 'ACDLORT', 'R')\n",
" True\n",
" >>> check_word('rat', 'ACDLORT', 'R')\n",
" False\n",
" >>> check_word('told', 'ACDLORT', 'R')\n",
" False\n",
" >>> check_word('bee', 'ACDLORT', 'R')\n",
" False\n",
" \"\"\"\n",
" return False"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a4d623b7",
"metadata": {},
"outputs": [],
"source": [
"# implementieren Sie hier"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "23ed7f79",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"run_doctests(check_word)"
]
},
{
"cell_type": "markdown",
"id": "0b9589fc",
"metadata": {},
"source": [
"Nach den \"Spelling Bee\"-Regeln...\n",
"\n",
"* ...sind Wörter mit vier Buchstaben je einen Punkt wert.\n",
"\n",
"* ...verdient man für längere Wörter je einen Punkt pro Buchstabe.\n",
"\n",
"* ...enthält jedes Rätsel mindestens ein \"Pangramm\", das jeden der Buchstaben enthält. Diese sind sieben Extrapunkte wert!\n",
"\n",
"Schreiben Sie eine Funktion namens `score_word`, die ein Wort und eine Zeichenkette mit verfügbaren Buchstaben aufnimmt und eine Punktzahl zurückgibt. Gehen sie davon aus, dass das Wort erlaubt ist.\n",
"\n",
"Hier ist wieder ein Entwurf der Funktion mit Doctests:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "11b69de0",
"metadata": {},
"outputs": [],
"source": [
"def word_score(word, available):\n",
" \"\"\"Berechnen Sie die Punktzahl für ein zulässiges Wort.\n",
" \n",
" >>> word_score('card', 'ACDLORT')\n",
" 1\n",
" >>> word_score('color', 'ACDLORT')\n",
" 5\n",
" >>> word_score('cartload', 'ACDLORT')\n",
" 15\n",
" \"\"\"\n",
" return 0"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "eff4ac37",
"metadata": {},
"outputs": [],
"source": [
"# implementieren Sie hier"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "eb8e8745",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"run_doctests(word_score)"
]
},
{
"cell_type": "markdown",
"id": "82e5283b",
"metadata": {
"tags": [
"remove-cell"
]
},
"source": [
"Wenn alle Ihre Funktionen die Tests bestehen, verwenden Sie folgende Schleife, um die Wortliste nach zulässigen Wörtern zu durchsuchen und deren Punktzahl zu berechnen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6965f673",
"metadata": {
"tags": [
"remove-output",
"remove-cell"
]
},
"outputs": [],
"source": [
"available = 'ACDLORT'\n",
"required = 'R'\n",
"total = 0\n",
"\n",
"file_object = open('words.txt')\n",
"for line in file_object:\n",
" word = line.strip() \n",
" if check_word(word, available, required):\n",
" score = word_score(word, available)\n",
" total = total + score\n",
" print(word, score)\n",
" \n",
"print(\"Total score\", total)"
]
},
{
"cell_type": "markdown",
"id": "dcc7d983",
"metadata": {
"tags": [
"remove-cell"
]
},
"source": [
"Besuchen Sie die \"Spelling Bee\" Website unter <https://www.nytimes.com/puzzles/spelling-bee> und geben Sie die Buchstaben des Tages ein. Der Buchstabe in der Mitte ist der verpflichtende Buchstabe.\n",
"\n",
"Ich habe einen Satz an Buchstaben gefunden, mit dem man Wörter mit einer Gesamtpunktzahl von 5820 bilden kann. Können Sie das übertreffen? Den besten Buchstabensatz zu finden, könnte zu schwer sein - wir müssen realistisch bleiben."
]
},
{
"cell_type": "markdown",
"id": "9ae466ed",
"metadata": {},
"source": [
"### Aufgabe 5\n",
"\n",
"Vielleicht ist Ihnen aufgefallen, dass die Funktionen, die Sie in den vorherigen Aufgaben geschrieben haben einiges gemeinsam hatten.\n",
"Tatsächlich sind sie sich so ähnlich, dass Sie oft eine der Funktionen verwenden können, um eine andere zu schreiben.\n",
"\n",
"Wenn zum Beispiel ein Wort keinen der verbotenen Buchstaben benutzt, ist das das Gegenteil der Funktion `uses_any`. Also können wir eine solche Version von `uses_none` schreiben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d3aac2dd",
"metadata": {},
"outputs": [],
"source": [
"def uses_none(word, forbidden):\n",
" \"\"\"Checks whether a word avoids forbidden letters.\n",
" \n",
" >>> uses_none('banana', 'xyz')\n",
" True\n",
" >>> uses_none('apple', 'efg')\n",
" False\n",
" >>> uses_none('', 'abc')\n",
" True\n",
" \"\"\"\n",
" return not uses_any(word, forbidden)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9a10674a-5694-4bd6-9b26-844468100738",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "307c07e6",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"run_doctests(uses_none)"
]
},
{
"cell_type": "markdown",
"id": "32aa2c09",
"metadata": {},
"source": [
"Es gibt außerdem eine Gemeinsamkeit zwischen `uses_only` und `uses_all`, die wir uns zu Nutzen machen können. Wenn Sie eine funktionierende Version von `uses_only`haben, versuchen Sie eine Version von `uses_all` zu schreiben, die `uses_only` aufruft:"
]
},
{
"cell_type": "markdown",
"id": "fa758462",
"metadata": {},
"source": [
"### Aufgabe 6\n",
"\n",
"Wenn Sie bei einer der vorherigen Aufgaben hängen geblieben sind, versuchen Sie einen virtuellen Assistenten zu fragen: \"Gegeben sei eine Funktion `uses_only`, die zwei Zeichenketten aufnimmt und überprüft, dass die erste nur die Zeichen der zweiten Zeichenkette nutzt, verwende diese um eine Funktion `uses_all` zu schreiben, die zwei Zeichenketten aufnimmt und überprüft, ob die erste alle Buchstaben aus der zweiten verwendet, wobei Wiederholungen erlaubt sind.\"\n",
"\n",
"Verwenden Sie `run_doctests` um die Antwort zu überprüfen."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "83c9d33c",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "ab66c777",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"run_doctests(uses_all)"
]
},
{
"cell_type": "markdown",
"id": "18f407b3",
"metadata": {},
"source": [
"### Aufgabe 7\n",
"\n",
"Lasst uns nun versuchen, `uses_all` auf Basis von `uses_any` zu schreiben.\n",
"\n",
"Fragen Sie einen virtuellen Assistenten: \"Gegeben sei eine Funktion `uses_any`, die zwei Zeichenketten aufnimmt und überprüft, ob die erste mindestens einen der Buchstaben aus der zweiten verwendet, kannst du diese verwenden um ` uses_all` zu schreiben, eine Funktion, die zwei Zeichenketten aufnimmt und überprüft, ob die erste alle Buchstaben aus der zweiten verwendet, wobei Wiederholungen erlaubt sind.\"\n",
"\n",
"Wenn das der Fall ist, sollten Sie das Ergebnis unbedingt testen!"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bfd6070c",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "6980de57",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "60865505-7ccf-48d8-92b0-6082c4905f3c",
"metadata": {},
"source": [
"## Aufgabe 8\n",
"Die eingebaute Funktion `eval` erwartet eine Zeichenkette und führt sie dann mit dem Python-Interpreter aus. Beispielsweise:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ce8180ae-876c-4c31-a85e-ff8cf6ca1642",
"metadata": {},
"outputs": [],
"source": [
"eval('1 + 2 * 3')"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "169d3d66-c338-4066-aeaf-3c58e64cbfb5",
"metadata": {},
"outputs": [],
"source": [
"import math\n",
"eval('math.sqrt(5)')"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "52a7622e-df98-473d-9afb-53e1c0049ff5",
"metadata": {},
"outputs": [],
"source": [
"eval('type(math.pi)')"
]
},
{
"cell_type": "markdown",
"id": "347bbfcf-3051-4cb4-a3e9-d056c620a5ed",
"metadata": {},
"source": [
"Schreiben Sie eine Funktion `eval_loop`, die den Nutzer iterativ bittet etwas einzugeben, die eingegebene Zeichenkette mittels `eval` ausführt und schließlich das Ergebnis ausgibt. \n",
"\n",
"Die Funktion sollte so lange laufen, bis der Nutzer `fertig` eingibt und dann sollte der Rückgabewert des letzten ausgeführten Ausdrucks ausgegeben werden.\n",
"\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Schreiben Sie den Funktionskopf.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Richten Sie die Nutzereingabe ein und weisen Sie diese einer Variablen zu, damit wir den Input weiter verwenden können.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Da der Nutzer mehrfach eine Eingabe machen soll, muss diese Zuweisung innerhalb einer Schleife stattfinden. \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Überlegen Sie, welche Schleife Sie verwenden müssen, was ist hier die Abbruchbedingung? Ist Sie positiv oder negativ?\n",
" \n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Wenn `fertig` eingegeben wird, soll der letzte berechnete Wert zurückgegeben werden, daher muss dieser in einer Variablen temporär gespeichert werden.\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Wenn nicht `fertig` eingegeben wird, wird der neue Ausdruck evaluiert und die temporären Variable wird mit dem neuen Ergebnis überschrieben.\n",
" \n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Vergessen Sie nicht, dass die temporäre Variable initialisiert werden muss, bevor wir sie zum Speichern von Werten verwenden können.\n",
" \n",
" </div> \n",
"</details>"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b9742510-2a86-4e2d-8f8a-21064a8889bc",
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier die Funktion eval_loop"
]
},
{
"cell_type": "markdown",
"id": "a6ab8bc6-2920-43a3-b789-0e9c552cdb86",
"metadata": {},
"source": [
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe) [Erklärung des Comics](https://www.explainxkcd.com/wiki/index.php/109:_Spoiler_Alert) falls Sie mehr erfahren wollen."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "cc5d1843-bd8b-421c-b5cc-4698557bad2e",
"metadata": {},
"outputs": [],
"source": [
"def eval_loop():\n",
" Eval=0\n",
" while True:\n",
" line = input('> ')\n",
" if line == 'fertig':\n",
" return(Eval)\n",
" break\n",
" Eval=eval(line)\n",
" print(Eval)\n",
" print('Fertig!')\n",
" \n",
"eval_loop()"
]
},
{
"cell_type": "markdown",
"id": "3f86c91d-b764-4f55-ac81-f8c0610792fc",
"metadata": {},
"source": [
"# Bonusaufgabe 1\n",
"\n",
"\n",
"\n",
"Der Mathematiker [Srinivasa Ramanujan](https://de.wikipedia.org/wiki/S._Ramanujan) hat eine unendliche Folge gefunden die genutzt werden kann, um eine numerische Näherung für 1/$\\pi$ zu berechnen:\n",
"\n",
"\\begin{equation}\n",
"\\frac{1}{\\pi} = \\frac{2\\sqrt{2}}{9801} \\cdot \\sum_{k=0}^{\\infty} \\frac{(4\\cdot k)! \\cdot (1103+26390 \\cdot k)}{(k!)^4 \\cdot 396^{4\\cdot k}}\n",
"\\end{equation}\n",
"\n",
"(Eventuell ist die Formel [in der Original-Aufgabenstellung](http://greenteapress.com/thinkpython2/html/thinkpython2008.html#hevea_default541) besser zu lesen.)\n",
"\n",
"Schreiben Sie eine Funktion `estimate_pi` die diese Formel nutzt, um einen Näherungswert für $\\pi$ zu berechnen und zurückzugeben. Sie sollten eine `while`-Schleife nutzen, um die Terme der Summe zu solange berechnen, bis der letzte Term kleiner ist als `1e-15` (was die Python-Notation für $10^{-15}$ ist). Sie können Ihr Ergebnis prüfen, indem Sie es mit `math.pi` vergleichen.\n",
"\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" Auf den ersten Blick sieht diese Formel sehr überwältigend aus. Machen Sie sich keine Sorgen, wir können die Formel in ihre einzelnen Bestandteile aufteilen und diese einzeln berechnen.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Wie Sie sehen können wird in der Formel zweimal eine Fakultät berechnet. Dafür können Sie die Funktion, die Sie in Seminar 6 geschrieben haben, verwenden.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Berechnen Sie zuerst die Konstante vor dem Summenzeichen und speichern Sie den Wert in einer Variablen. In unserer Lösung wird diese Variable `faktor` genannt.\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Die while-Schleife ersetzt das Summenzeichen. Überlegen Sie sich wie Sie die Bedingung formulieren müssen. Die Abbruchbedingung lautet $abs(term)<1e-15$\n",
" \n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Das Summenzeichen berechnet und addiert Werte von `k=0` bis unendlich. `k` muss also in jedem Schleifendurchlauf um 1 erhöht werden. \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Alles was hinter dem Summenzeichen steht, wird in der Schleife berechnet.\n",
" \n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"In jedem Durchgang der Schleife werden Zähler (hier `num`) und Nenner (hier `den`) einzeln berechnet und je einer Variablen zugewiesen.\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">8. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Anschließend wird der Wert des Terms im aktuellen Schleifendurchlauf berechnet, indem die Konstante vor dem Summenzeichen mit dem Bruch hinter dem Summenzeichen multipliziert wird.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">9. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Dieser Wert wird in jedem Schleifendurchlauf auf das Gesamtergebnis hinzuaddiert.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">10. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Danach wird geprüft, ob die Abbruchbedingung erfüllt ist.\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">11. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Da diese Formel 1/$\\pi$ berechnet, muss 1/ergebnis gerechnet werden um $\\pi$ zu erhalten. \n",
" \n",
" </div> \n",
"</details>"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fdcf5448-3e08-46e6-9868-7b52516fb0a2",
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier die Funktion estimate_pi"
]
},
{
"cell_type": "markdown",
"id": "22029d24-134d-4539-8b44-c36daea61717",
"metadata": {},
"source": [
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe) [Erklärung des Comics](https://www.explainxkcd.com/wiki/index.php/109:_Spoiler_Alert) falls Sie mehr erfahren wollen."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2be81de8-f673-4ff1-b125-83297d5008e6",
"metadata": {},
"outputs": [],
"source": [
"import math\n",
"\n",
"def fakultaet(n):\n",
" if not isinstance(n, int):\n",
" print('Die Fakultät ist nur für ganze Zahlen definiert.')\n",
" return None\n",
" elif n < 0:\n",
" print('Die Fakultät für negative ganze Zahlen ist nicht definiert.')\n",
" return None\n",
" elif n == 0:\n",
" return 1\n",
" else:\n",
" return n * fakultaet(n-1)\n",
"\n",
"def estimate_pi():\n",
" faktor = 2 * math.sqrt(2) / 9801 \n",
" ergebnis = 0\n",
" k = 0\n",
" while True:\n",
" num = fakultaet(4*k) * (1103 + 26390*k)\n",
" den = fakultaet(k)**4 * 396**(4*k)\n",
" term = faktor * num / den\n",
" ergebnis= ergebnis + term\n",
" if abs(term) < 1e-15:\n",
" break\n",
" k =k + 1\n",
" \n",
" fast_pi= 1/ ergebnis\n",
" return fast_pi\n",
"\n",
"print(estimate_pi())"
]
},
{
"cell_type": "markdown",
"id": "1933f6b8-0c4d-4ef3-a7cd-879cca648192",
"metadata": {},
"source": [
"# Bonusaufgabe 2\n",
"## Quadratwurzeln\n",
"\n",
"\n",
"\n",
"([Estimation](https://xkcd.com/612/), Randall Munroe) [Erklärung des Comics](explainxkcd.com/wiki/index.php/612:_Estimation) falls Sie mehr wissen möchten.\n",
"\n",
"Schleifen werden häufig in Programmen genutzt, die numerische Werte berechnen, indem sie mit einem Näherungswert beginnen und diesen iterativ verbessern. \n",
"\n",
"Beispielsweise kann die Quadratwurzel einer Zahl mit dem [Newton-Verfahren](https://de.wikipedia.org/wiki/Newton-Verfahren) berechnet werden. Angenommen, wir wollen die Quadratwurzel von $a$ berechnen. Wenn wir mit einem (fast beliebigen) Näherungswert $x$ beginnen, können wir einen besseren Näherungswert $y$ mit der folgenden Formel berechnen:\n",
"\n",
"\\begin{equation}\n",
"y = \\frac{x + a/x}{2}\n",
"\\end{equation}\n",
"\n",
"Wenn beispielsweise $a$ gleich 4 ist und $x$ gleich 3:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "003354ad-857e-449e-8ece-98895166b31e",
"metadata": {},
"outputs": [],
"source": [
"a = 4\n",
"x = 3\n",
"y = (x + a/x) / 2\n",
"y"
]
},
{
"cell_type": "markdown",
"id": "2c2cd67b-0da2-4f04-864e-57b58454465c",
"metadata": {},
"source": [
"Das Ergebnis ist näher an der richtigen Antwort ($\\sqrt{4} = 2$). Wenn wir den Vorgang mit dem neuen Näherungswert wiederholen, kommen wir noch näher heran:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c9848b49-c724-4736-8bb3-edec3aa3199c",
"metadata": {},
"outputs": [],
"source": [
"x = y\n",
"y = (x + a/x) / 2\n",
"y "
]
},
{
"cell_type": "markdown",
"id": "d89eea35-b499-42a2-a12f-fd8d4ae117ef",
"metadata": {},
"source": [
"Nach ein paar mehr Aktualisierungen ist die Näherung fast exakt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ee92d90e-9ffd-4e46-b2f6-66d858d9f256",
"metadata": {},
"outputs": [],
"source": [
"x = y\n",
"y = (x + a/x) / 2\n",
"y"
]
},
{
"cell_type": "markdown",
"id": "ad314ff7-63a4-45a7-a3bb-cb7969bd7f6c",
"metadata": {},
"source": [
"Im Allgemeinen wissen wir anfangs nicht, wie viele Schritte nötig sind, um die richtige Antwort zu erhalten, aber wir wissen es, wenn sich der Näherungswert nicht mehr verändert:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9c8e69f5-24a7-43a2-bd00-0cddcb4bbe02",
"metadata": {},
"outputs": [],
"source": [
"x = y\n",
"y = (x + a/x) / 2\n",
"y \n"
]
},
{
"cell_type": "markdown",
"id": "5ef03533-73c0-481e-906a-f7671ac802ad",
"metadata": {},
"source": [
"Sobald `x == y` gilt, können wir abbrechen. Im Folgenden eine Schleife, die mit einem Näherungswert `x` beginnt und diesen verbessert, bis er sich nicht mehr ändert:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d7fdde6b-ae8c-42e3-8e84-6cb1c5afd329",
"metadata": {},
"outputs": [],
"source": [
"a = 4\n",
"x = 3\n",
"\n",
"while True:\n",
" print(x)\n",
" y = (x + a/x) / 2\n",
" if y == x:\n",
" break\n",
" x = y\n"
]
},
{
"cell_type": "markdown",
"id": "482447ff-aca8-4db6-a128-af63985f1975",
"metadata": {},
"source": [
"Für die meisten Werte von `a` funktioniert das sehr gut aber im Allgemeinen ist es gefährlich, die Gleichheit von Gleitkommazahlen zu testen. Gleitkommazahlen sind nur ungefähr exakt: die meisten rationalen Zahlen wie z.B. 1/3 und irrationale Zahlen wie z.B. $\\sqrt{2}$ können nicht exakt als Gleitkommazahl repräsentiert werden. \n",
"\n",
"Statt zu prüfen ob `x` und `y` exakt gleich sind ist es sicherer, die eingebaute Funktion `abs` zu nutzen, um den Absolutbetrag des Unterschieds zwischen den beiden Zahlen zu berechnen:\n",
"\n",
"```python\n",
"if abs(y-x) < epsilon:\n",
" break\n",
"```\n",
"\n",
"Wobei wir für `epsilon` einen sehr kleinen Wert wie z.B. `0.0000001` wählen sollten, der bestimmt, welche Näherung gut genug für uns ist. "
]
},
{
"cell_type": "markdown",
"id": "9aa286b3-e99f-4149-9e9a-04b14b601d20",
"metadata": {},
"source": [
"## Übung\n",
"\n",
"Kopieren Sie die Schleife aus [Abschnitt 7.8](#7.8-Quadratwurzeln) und verkapseln Sie sie in eine Funktion `mysqrt` die einen Parameter `a` erwartet, einen sinnvollen Wert für `x` wählt und eine Näherung für die Quadratwurzel von `a` zurückliefert.\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Schreiben Sie den Kopf der Funktion, überlegen Sie welche Argumente der Funktion übergeben müssen.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Kopieren Sie, wie oben bereits erwähnt die Funktion. \n",
" \n",
" </div> \n",
"</details> \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Wenn Sie das Notebook aufmerksam gelesen haben, werden Sie sich an einige Verbesserungen erinnern, die wir vornehmen müssen.\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Die bedeutet, dass Sie den Betrag der Differenz zwischen `x` und `y` berechnen müssen. Anschließend vergleichen Sie, ob dieser Wert kleiner als `epsilon` ist. Nutzen Sie dazu die Betragsfunktion `abs()`. Lösung: $abs(x-y)<epsilon$ wobei Sie einen passenden Wert für `epsilon` wählen müssen (z.B. 0.001). Fügen Sie diese Änderungen in Ihren Code ein. \n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Wählen Sie einen geeigneten Wert für `x` in Abhängigkeit von `a`. Dies können Sie durch Ausprobieren ermitteln. Stellen Sie sicher, dass `x` ungleich null ist. \n",
"\n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Vergessen Sie nicht Ihre Funktion mit Werten zu testen, die Sie überprüfen können.\n",
" \n",
" </div> \n",
"</details>\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "18413a90-e3e6-4468-b000-d3656b6c507d",
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier die Funktion mysqrt\n",
"\n",
"\n",
"# Testen Sie hier die Funktion\n",
"print(\"Die Wurzel von 2 ist ungefähr \", mysqrt(2))\n",
"print(\"Die Wurzel von 23 ist ungefähr \", mysqrt(23))"
]
},
{
"cell_type": "markdown",
"id": "8eada683-0cc3-48a9-a724-186d17004286",
"metadata": {},
"source": [
"Testen Sie die Funktion, indem Sie eine Funktion `test_square_root` schreiben, die eine Tabelle der folgenden Art ausgibt:\n",
"\n",
"```\n",
"a mysqrt(a) math.sqrt(a) diff\n",
"- --------- ------------ ----\n",
"1.0 1.0 1.0 0.0\n",
"2.0 1.41421356237 1.41421356237 2.22044604925e-16\n",
"3.0 1.73205080757 1.73205080757 0.0\n",
"4.0 2.0 2.0 0.0\n",
"5.0 2.2360679775 2.2360679775 0.0\n",
"6.0 2.44948974278 2.44948974278 0.0\n",
"7.0 2.64575131106 2.64575131106 0.0\n",
"8.0 2.82842712475 2.82842712475 4.4408920985e-16\n",
"9.0 3.0 3.0 0.0\n",
"```\n",
"\n",
"Dabei ist die erste Spalte eine Zahl, `a`; die zweite Spalte ist die Quadratwurzel von `a` die mit `mysqrt` berechnet wurde; die dritte Spalte ist die Quadratwurzel, die mittels `math.sqrt` berechnet wurde; und die vierte Spalte ist der Absolutbetrag des Unterschieds zwischen den beiden Werten. \n",
"\n",
"Wenn ihre Funktion funktiniert, können Sie anfange, die Tabelle zu implementieren. Dazu können Sie folgendermaßen anfangen:\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Der Kopf der Funktion ist bereits gegeben, aber Sie können bereits den Tabellenkopf schreiben. Dafür schreiben Sie eine `print`-Anweisung für jede Zeile des Tabellenkopfs.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Als nächstes müssen Sie entscheiden ob Sie die Tabelle von oben ausgeben wollen, dann muss `a` die Werte 1 bis 9 annehmen - Sie brauchen eine Schleife - oder ob Sie die Tabelle für ein beliebiges `a` berechnen wollen, dann müssen Sie User-Input einrichten.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Wir planen für die Schleife, für diesen Fall können Sie eine `While` oder eine `For` Schleife verwenden. \n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Prüfen Sie zunächst, ob beide Funktionen (`mysqrt()` und `math.sqrt()` Werte zurückgeben. Trifft dies auf Ihre Funktion zu? Wenn nicht, nutzen Sie die return-Anweisung an der richtigen Stelle in `mysqrt()`. \n",
" \n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Die Ergebnisse der Funktionen müssen in Variablen gespeichert werden.\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Berechnen Sie die Differenz zwischen `mysqrt()` und `math.sqrt()` und speichern Sie diese in einer neuen Variablen.\n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"\n",
"Fügen Sie die `print`-Anweisung hinzu, die die einzelnen Tabellenzeilen ausgibt.\n",
"\n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">8. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Vergessen Sie nicht den Wert für `a` bei jedem Schleifendurchlauf zu erhöhen. \n",
" </div> \n",
"</details>"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1bb32eda-baaa-4ace-b63e-5f4e5ed84c73",
"metadata": {},
"outputs": [],
"source": [
"def test_square_root():\n",
" # Implementieren Sie hier die Funktion test_square_root\n",
"\n",
"\n",
"# Rufen Sie hier die Funktion test_square_root auf\n",
"test_square_root()"
]
},
{
"cell_type": "markdown",
"id": "4f069856-e152-4952-889d-4b4ce054613a",
"metadata": {},
"source": [
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe) [Erklärung des Comics](https://www.explainxkcd.com/wiki/index.php/109:_Spoiler_Alert) falls Sie mehr erfahren wollen.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "653095fc-e92d-49fb-8ee5-e75981fc7494",
"metadata": {},
"outputs": [],
"source": [
"def mysqrt(a):\n",
" if a==1:\n",
" x=a\n",
" else:\n",
" x=a-1\n",
" \n",
" epsilon=0.00000000001\n",
" while True:\n",
" y=(x+a/x)/2\n",
" if abs(y-x) < epsilon:\n",
" break\n",
" x=y\n",
" return x\n",
" \n",
" \n",
"mysqrt(25)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6bc324ed-fedb-4be7-a4c0-de396b780888",
"metadata": {},
"outputs": [],
"source": [
"import math\n",
"def test_square_root():\n",
" a=1.0\n",
" print('a mysqrt(a) math.sqrt(a) diff')\n",
" print('- --------- ------------ ----')\n",
" while a<10:\n",
" E= mysqrt(a)\n",
" M= math.sqrt(a)\n",
" if E<M:\n",
" diff=M-E\n",
" else:\n",
" diff=E-M\n",
" E=str(E)\n",
" M=str(M)\n",
" print(a,E,(18-len(E))*' ',M,(18-len(M))*' ',diff)\n",
" a=a+1\n",
"\n",
" \n",
"test_square_root()"
]
},
{
"cell_type": "markdown",
"id": "aadee942-b8dd-4679-a331-e6023b569ad6",
"metadata": {},
"source": [
" Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). Rufen Sie dazu im Menü *File* den Punkt *Download as* → *Notebook* auf und nutzen Sie beispielsweise einen USB-Stick, E-Mail, Google Drive, Dropbox oder Ihre [HU-Box](https://box.hu-berlin.de/). \n"
]
},
{
"cell_type": "markdown",
"id": "3f98530e-bfe6-4319-9898-50940c840ba4",
"metadata": {},
"source": [
"\n",
"\n",
"Herzlichen Glückwunsch! Sie haben das 7. Kapitel geschafft!"
]
},
{
"cell_type": "markdown",
"id": "5cf853f4-5575-408c-8446-bc993452dc66",
"metadata": {},
"source": [
"<img src=\"https://scm.cms.hu-berlin.de/ibi/python/-/raw/master/img/by-nc-sa.png\" alt=\"CC BY-NC-SA\" style=\"width: 150px;\"/>\n",
"\n",
"Der Text dieses Notebooks ist als freies Werk unter der Lizenz [CC BY-NC-SA 4.0 ](https://creativecommons.org/licenses/by-nc-sa/4.0/) verfügbar.\n",
"Der Code dieses Notebooks ist als freies Werk unter der Lizenz [MIT License](https://mit-license.org/) verfügbar.\n",
"\n",
"Es handelt sich um übersetzte und leicht veränderte Notebooks von [Allen B. Downey](https://allendowney.com) aus [Think Python: 3rd Edition](https://allendowney.github.io/ThinkPython/index.html).\n"
]
}
],
"metadata": {
"celltoolbar": "Tags",
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.12.2"
}
},
"nbformat": 4,
"nbformat_minor": 5
}