{
"cells": [
{
"cell_type": "markdown",
"id": "88ecc443",
"metadata": {
"id": "88ecc443"
},
"source": [
"# Kapitel 6: Rückgabewerte\n",
"\n",
"[Chapter 6: Return Values](https://colab.research.google.com/github/AllenDowney/ThinkPython/blob/v3/chapters/chap06.ipynb)\n",
"\n",
"In den vorherigen Kapiteln haben wir eingebaute Funktionen -- wie `abs` und `round` -- und Funktionen aus dem Modul `math` -- wie `sqrt` und `pow` -- verwendet.\n",
"Wenn wir eine dieser Funktionen aufrufen, gibt diese einen Wert zurück, den wir einer Variable zuweisen oder als Teil eines Ausdrucks verwenden können.\n",
"\n",
"Die Funktionen, die wir bisher geschrieben haben sind anders.\n",
"Einige verwenden die `print`-Funktion, um Werte darzustellen, andere nutzen `jupyturtle`-Funktionen, um Abbildungen zu zeichnen.\n",
"Aber sie geben keine Werte zurück, die wir einer Variable zuweisen oder in einem Ausdruck nutzen könnten.\n",
"\n",
"In diesem Kapitel werden wir sehen, wie man Funktionen schreibt, die Werte zurückgeben (Englisch: _return_).\n",
"\n",
"\n",
"\n",
"\n",
"([Random Number](https://xkcd.com/221/), Randall Munroe). [Erklärung der Comics](https://www.explainxkcd.com/wiki/index.php/221:_Random_Number) falls Sie mehr erfahren wollen.\n"
]
},
{
"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",
"\n",
"\n",
"\n",
"## Exkurs: Was mir an Python gefällt\n",
"\n",
"Wir wünschen Ihnen ein frohes Fest und einen guten Rutsch ins neue Jahr."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "71c75c42-310b-4238-b343-5aef093e0595",
"metadata": {},
"outputs": [],
"source": [
"\"\"\" \n",
"Quelle: https://teampython.wordpress.com/2015/12/12/print-a-christmas-tree/\n",
"Python 3 version by antiloquax (2015), based on code from datamungeblog.com.\n",
"\"\"\"\n",
" \n",
"from random import choice\n",
"from random import random\n",
" \n",
"# If you change this, use an odd number.\n",
"size = 21\n",
"\n",
"# Probability that a character will be green.\n",
"prob_gr = 0.6\n",
"# Colour codes.\n",
"colours = [31, 33, 34, 35, 36, 37]\n",
"# Characters to use for decorations. Experiment with these.\n",
"# The chr(169) and chr(174) characters may not work in all terminals\n",
"# (extended ASCII, c and r in a circle).\n",
"decs = ['@', '&', '*', chr(169), chr(174)]\n",
"\n",
"# Format string for printing blinking characters.\n",
"blink_col = \"\\033[5;{0}m{1}\\033[0m\"\n",
"# String to print a green octothorpe ('#').\n",
"leaf = \"\\033[32m#\\033[0m\"\n",
"\n",
"# Width of the tree, will grow by 2 each time.\n",
"width = 1\n",
"# Initialise the tree string, with a star at the top.\n",
"tree = \"\\n{}*\\n\".format(' ' * (size))\n",
"\n",
"\"\"\" Main Loop starts now.\"\"\"\n",
" \n",
"\"\"\" We can't use the normal \"format\" centering approach:\n",
" (\"{:^nn}\".format(string) where \"nn\" is the width of the line), \n",
" with these ansi codes. This is because Python sees the strings as being\n",
" more than one character long (15 & 10 for baubles and leaves).\"\"\"\n",
"\n",
"# Loop from (size - 1) down to 0, using the counter as the padding size.\n",
"for pad in range(size - 1, -1, -1):\n",
" # Increase the width of the tree by 2.\n",
" width += 2\n",
" \n",
" # Put the characters for the line in \"temp\".\n",
" temp = \"\"\n",
" for j in range(width):\n",
" # Make some leaves.\n",
" if random() < prob_gr:\n",
" temp += leaf\n",
" # And also some baubles.\n",
" else:\n",
" temp += blink_col.format(choice(colours), choice(decs))\n",
"\n",
" # Add that string to the line, with padding.\n",
" tree += \"{0}{1}\\n\".format(' ' * pad, temp)\n",
"\n",
"# Add a \"trunk\" of 2 lines and return.\n",
"print(tree + \"{0}{1}\\n\".format(' ' * (size - 1), \"000\") * 2)\n",
"print(\"\\x46\\x72\\x6f\\x68\\x65\\x20\\x46\\x65\\x73\\x74\\x74\\x61\\x67\\x65\\x21\")"
]
},
{
"cell_type": "markdown",
"id": "81fe9953-b28c-4ef3-886b-281163c5c257",
"metadata": {},
"source": [
"[Und noch viele weitere schöne Beispiele](https://codegolf.stackexchange.com/questions/15860/) "
]
},
{
"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": "56b1c184",
"metadata": {
"id": "56b1c184",
"tags": []
},
"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": "6cf2cf80",
"metadata": {
"id": "6cf2cf80"
},
"source": [
"## Einige Funktionen haben Rückgabewerte...\n",
"\n",
"Wenn wir eine Funktion wie `math.sqrt` aufrufen, nennt man das Ergebnis einen **Rückgabewert** (Englisch: *return value*).\n",
"Steht der Funktionsaufruf am Ende einer Zelle, so zeigt Jupyter den Rückgabewert sofort an:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e0e1dd91",
"metadata": {
"id": "e0e1dd91"
},
"outputs": [],
"source": [
"import math\n",
"\n",
"math.sqrt(42 / math.pi)"
]
},
{
"cell_type": "markdown",
"id": "4b4885c2",
"metadata": {
"id": "4b4885c2"
},
"source": [
"Wenn wir den Rückgabewert einer Variable zuweisen, wird dieser nicht angezeigt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5aaf62d2",
"metadata": {
"id": "5aaf62d2"
},
"outputs": [],
"source": [
"radius = math.sqrt(42 / math.pi)"
]
},
{
"cell_type": "markdown",
"id": "196c692b",
"metadata": {
"id": "196c692b"
},
"source": [
"Aber wir können ihn später darstellen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "741f7386",
"metadata": {
"id": "741f7386"
},
"outputs": [],
"source": [
"radius"
]
},
{
"cell_type": "markdown",
"id": "257b28d5",
"metadata": {
"id": "257b28d5"
},
"source": [
"Oder wir können den Rückgabewert als Teil eines Ausdrucks verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e56d39c4",
"metadata": {
"id": "e56d39c4"
},
"outputs": [],
"source": [
"radius + math.sqrt(42 / math.pi)"
]
},
{
"cell_type": "markdown",
"id": "23ed47ab",
"metadata": {
"id": "23ed47ab"
},
"source": [
"Hier ist ein Beispiel einer Funktion, die einen Wert zurückkgibt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "50a9a9be",
"metadata": {
"id": "50a9a9be"
},
"outputs": [],
"source": [
"def kreisflaeche(radius):\n",
" flaeche = math.pi * radius**2\n",
" return flaeche"
]
},
{
"cell_type": "markdown",
"id": "273acabc",
"metadata": {
"id": "273acabc"
},
"source": [
"`kreisflaeche` nimmt `radius` als Parameter auf und berechnet die Fläche eines Kreises mit diesem Radius.\n",
"\n",
"Die letzte Zeile ist eine `return`-Anweisung, die den Wert von `flaeche` zurückgibt.\n",
"\n",
"Wenn wir die Funktion so aufrufen, zeigt Jupyter den Rückgabewert an:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d70fd9b5",
"metadata": {
"id": "d70fd9b5"
},
"outputs": [],
"source": [
"kreisflaeche(radius)"
]
},
{
"cell_type": "markdown",
"id": "4f28bfd6",
"metadata": {
"id": "4f28bfd6"
},
"source": [
"Wir können den Rückgabewert einer Variable zuweisen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ef20ba8c",
"metadata": {
"id": "ef20ba8c"
},
"outputs": [],
"source": [
"a = kreisflaeche(radius)"
]
},
{
"cell_type": "markdown",
"id": "3f82fe70",
"metadata": {
"id": "3f82fe70"
},
"source": [
"Oder ihn als Teil eines Ausdrucks verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0a4670f4",
"metadata": {
"id": "0a4670f4"
},
"outputs": [],
"source": [
"kreisflaeche(radius) + 2 * kreisflaeche(radius / 2)"
]
},
{
"cell_type": "markdown",
"id": "15122fd2",
"metadata": {
"id": "15122fd2"
},
"source": [
"Später können wir den Wert der Variable anzeigen, der wir das Ergebnis zugewiesen haben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6e6460b9",
"metadata": {
"id": "6e6460b9"
},
"outputs": [],
"source": [
"a"
]
},
{
"cell_type": "markdown",
"id": "a3f6dcae",
"metadata": {
"id": "a3f6dcae"
},
"source": [
"Aber wir können nicht auf `flaeche` zugreifen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "77613df9",
"metadata": {
"id": "77613df9",
"tags": []
},
"outputs": [],
"source": [
"%%expect NameError\n",
"\n",
"flaeche"
]
},
{
"cell_type": "markdown",
"id": "f8ace9ce",
"metadata": {
"id": "f8ace9ce"
},
"source": [
"`flaeche` ist eine lokale Variable in einer Funktion, daher können wir außerhalb der Funktion nicht auf die Variable zugreifen."
]
},
{
"cell_type": "markdown",
"id": "41a4f03f",
"metadata": {
"id": "41a4f03f"
},
"source": [
"## ...und andere haben keine (\"None\")\n",
"\n",
"Wenn eine Funktion keine `return`-Anweisung hat, gibt sie `None` zurück, was wie `True` und `False` ein besonderer Wert ist.\n",
"Hier ist zum Beispiel die `repeat`-Funktion aus Kapitel 3:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "89c083f8",
"metadata": {
"id": "89c083f8"
},
"outputs": [],
"source": [
"def repeat(word, n):\n",
" print(word * n)"
]
},
{
"cell_type": "markdown",
"id": "6ada19cf",
"metadata": {
"id": "6ada19cf"
},
"source": [
"Wenn wir diese so aufrufen, stellt sie die erste Zeile des Monty Python Songs \"Finland\" dar:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "737b67ca",
"metadata": {
"id": "737b67ca"
},
"outputs": [],
"source": [
"repeat('Finland, ', 3)"
]
},
{
"cell_type": "markdown",
"id": "fe49f5e5",
"metadata": {
"id": "fe49f5e5"
},
"source": [
"Diese Funktion verwendet die `print`-Funktion, um eine Zeichenkette anzuzeigen, aber sie nutzt keine `return`-Anweisung um einen Wert zurückzugeben.\n",
"Wenn wir das Ergebnis einer Variable zuweisen wird die Zeichenkette trotzdem angezeigt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9b4fa14f",
"metadata": {
"id": "9b4fa14f"
},
"outputs": [],
"source": [
"result = repeat('Finland, ', 3)"
]
},
{
"cell_type": "markdown",
"id": "4ecabbdb",
"metadata": {
"id": "4ecabbdb"
},
"source": [
"Und wenn wir den Wert der Variable anzeigen, erhalten wir nichts:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "50f96bcb",
"metadata": {
"id": "50f96bcb"
},
"outputs": [],
"source": [
"result"
]
},
{
"cell_type": "markdown",
"id": "07033959",
"metadata": {
"id": "07033959"
},
"source": [
"`result` hat zwar einen Wert, Jupyter zeigt diesen aber nicht.\n",
"Stattdessen können wir ihn folgendermaßen darstellen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6712f2df",
"metadata": {
"id": "6712f2df"
},
"outputs": [],
"source": [
"print(result)"
]
},
{
"cell_type": "markdown",
"id": "379b98c5",
"metadata": {
"id": "379b98c5"
},
"source": [
"Der Rückgabewert von `repeat` ist `None`.\n",
"\n",
"Hier ist eine Funktion, die `repeat` ähnelt, allerdings einen Rückgabewert hat:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0ec1afd3",
"metadata": {
"id": "0ec1afd3"
},
"outputs": [],
"source": [
"def repeat_string(word, n):\n",
" return word * n"
]
},
{
"cell_type": "markdown",
"id": "db6ad3d4",
"metadata": {
"id": "db6ad3d4"
},
"source": [
"Hier fällt auf, dass wir einen Ausdruck in einer `return`-Anweisung verwenden können, nicht nur eine Variable.\n",
"\n",
"Mit dieser Version können wir das Ergebnis einer Variable zuweisen.\n",
"Wenn die Funktion läuft wird nichts ausgegeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c82334b6",
"metadata": {
"id": "c82334b6"
},
"outputs": [],
"source": [
"line = repeat_string('Spam, ', 4)"
]
},
{
"cell_type": "markdown",
"id": "1232cd8a",
"metadata": {
"id": "1232cd8a"
},
"source": [
"Aber wir können den Wert, der `line` zugewiesen wurde später so anzeigen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "595ec598",
"metadata": {
"id": "595ec598"
},
"outputs": [],
"source": [
"line"
]
},
{
"cell_type": "markdown",
"id": "ae02c7d2",
"metadata": {
"id": "ae02c7d2"
},
"source": [
"Eine solche Funktion wird **reine Funktion** (Englisch: *pure function*) genannt, weil sie nichts anzeigt und auch keine andere Wirkung hat -- außer einen Wert zurückzugeben."
]
},
{
"cell_type": "markdown",
"id": "567ae734",
"metadata": {
"id": "567ae734"
},
"source": [
"## Rückgabewerte und Bedingungen\n",
"\n",
"Würde Python `abs` nicht zur Verfügung stellen, könnten wir es so schreiben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "236c59e6",
"metadata": {
"id": "236c59e6"
},
"outputs": [],
"source": [
"def absolute_value(x):\n",
" if x < 0:\n",
" return -x\n",
" else:\n",
" return x"
]
},
{
"cell_type": "markdown",
"id": "ffd559b8",
"metadata": {
"id": "ffd559b8"
},
"source": [
"Wenn `x` negativ ist, gibt die erste `return`-Anweisung `-x` zurück und die Funktion wird sofort beendet.\n",
"Andernfalls gibt die zweite `return`-Anweisung `x` zurück und die Funktion endet.\n",
"Diese Funktion ist also richtig.\n",
"\n",
"Wenn wir `return`-Anweisungen in einer Bedingung verwenden, müssen wir allerdings aufpassen, dass jeder mögliche Pfad durch das Programm eine `return`-Anweisung beinhaltet.\n",
"Hier ist zum Beispiel eine falsche Version von `absolute_value`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2f60639c",
"metadata": {
"id": "2f60639c"
},
"outputs": [],
"source": [
"def absolute_value_wrong(x):\n",
" if x < 0:\n",
" return -x\n",
" if x > 0:\n",
" return x"
]
},
{
"cell_type": "markdown",
"id": "da3280ae",
"metadata": {
"id": "da3280ae"
},
"source": [
"Folgendes passiert wenn wir diese Funktion mit `0` als Argument aufrufen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c9dae6c8",
"metadata": {
"id": "c9dae6c8"
},
"outputs": [],
"source": [
"absolute_value_wrong(0)"
]
},
{
"cell_type": "markdown",
"id": "5733f239",
"metadata": {
"id": "5733f239"
},
"source": [
"Wir erhalten nichts! Das Problem ist folgendes: wenn `x` `0` ist, ist keine der beiden Bedingungen wahr und die Funktion endet, ohne auf eine `return`-Anweisung zu treffen. Das bedeutet, der Rückgabewert ist `None`und Jupyter zeigt nichts an.\n",
"\n",
"Als ein weiteres Beispiel ist hier eine Version von `absolute_value` mit einer zusätzlichen `return`-Anweisung am Ende:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c8c4edee",
"metadata": {
"id": "c8c4edee"
},
"outputs": [],
"source": [
"def absolute_value_extra_return(x):\n",
" if x < 0:\n",
" return -x\n",
" else:\n",
" return x\n",
"\n",
" return 'This is dead code'"
]
},
{
"cell_type": "markdown",
"id": "cf5486fd",
"metadata": {
"id": "cf5486fd"
},
"source": [
"Wenn `x` negativ ist, läuft die erste `return`-Anweisung und die Funktion endet.\n",
"In allen anderen Fällen läuft die zweite `return`-Anweisung und die Funktion endet.\n",
"So oder so erreichen wir die dritte `return`-Anweisung nicht -- also kann diese nie laufen.\n",
"\n",
"Code, der in keinem Fall laufen kann, wird **toter Code** (Englisch: *dead code*) genannt.\n",
"\n",
"\n",
"\n",
"Allgemein richtet toter Code zwar keinen Schaden an, er ist aber häufig Zeichen für ein Missverständnis und kann bei Personen, die versuchen, ein Programm zu verstehen, zu Verwirrung führen."
]
},
{
"cell_type": "markdown",
"id": "2918c829-e9b2-44f0-9145-d622894fbdda",
"metadata": {},
"source": [
"## Inkrementelle Entwicklung\n",
"\n",
"Wenn wir größere Funktionen schreiben, kann es sein, dass wir mehr Zeit mit der Fehlersuche (Englisch: *Debugging*) verbringen.\n",
"\n",
"Um mit zunehmend komplexeren Programmen klarzukommen, können wir eine Methode verwenden, die sich **inkrementelle Entwicklung** (Englisch: *incremental development*) nennt. Das Ziel bei der inkrementellen Entwicklung ist die Vermeidung langer Fehlersuch-Sitzungen, indem immer nur kleine Codestücke hinzugefügt und getestet werden.\n",
"\n",
"Nehmen wir z.B. an, dass wir die Entfernung zwischen zwei Punkten berechnen wollen, die durch die Koordinaten $(x_1, y_1)$ und $(x_2, y_2)$ gegeben sind. Nach dem [Satz des Pythagoras](https://de.wikipedia.org/wiki/Satz_des_Pythagoras) ist die Entfernung: \n",
"\n",
"$entfernung = \\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$\n",
"\n",
"Im ersten Schritt sollten wir uns überlegen, wie die Funktion `entfernung` in Python aussehen sollte. In anderen Worten: Was sind die Eingaben (Parameter) und was ist das Ergebnis (Rückgabewert)?\n",
"\n",
"In diesem Fall sind die Eingaben zwei Punkte, die wir durch vier Zahlen repräsentieren können. Das Ergebnis ist die Entfernung, repräsentiert als Gleitkommazahl.\n",
"\n",
"Mit dieser Information können wir sofort eine Skizze der Funktion schreiben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6d3ffad2-52cf-43ff-983d-2bbdd64dd8e5",
"metadata": {},
"outputs": [],
"source": [
"def entfernung(x1, y1, x2, y2):\n",
" return 0.0"
]
},
{
"cell_type": "markdown",
"id": "c7477b7a-fb59-4f95-a89d-941fd7341117",
"metadata": {},
"source": [
"Ganz offensichtlich berechnet diese Variante nicht die Entfernung, sie liefert stets Null zurück. Aber sie ist syntaktisch korrekt und sie läuft, das heißt, wir können die Funktion testen, bevor wir sie verkomplizieren.\n",
"\n",
"Rufen Sie die Funktion mit Beispielargumenten auf, um sie zu testen: "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "35eccb91-f033-4152-b59a-d7ceb3e6affc",
"metadata": {},
"outputs": [],
"source": [
"entfernung(1, 2, 4, 6)"
]
},
{
"cell_type": "markdown",
"id": "a9af77d5-4358-4a8a-a7f4-9a85da8f2937",
"metadata": {},
"source": [
"Diese Werte sind so gewählt, dass die horizontale Distanz drei ist und die vertikale Distanz 4 - dadurch ist das Ergebnis 5 - die Hypothenuse eines Dreiecks mit den Seitenlängen 3-4-5. Wenn wir die Funktion testen ist es hilfreich, das richtige Ergebnis zu kennen.\n",
"\n",
" \n",
"\n",
"([Petrus3743](https://commons.wikimedia.org/wiki/File:01-Rechtwinkliges_Dreieck-Pythagoras.svg), Wikimedia Commons)\n",
"\n",
"An dieser Stelle haben wir uns davon überzeugt, dass die Funktion syntaktisch korrekt ist. Wir können also damit beginnen, Code zum Rumpf hinzuzufügen. Ein naheliegender nächster Schritt ist, die Differenzen $x_2-x_1$ und $y_2-y_1$ zu berechnen. Die nächste Version speichert die Werte in **temporären Variablen** (Englisch: *temporary variables*) und gibt sie aus: "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "276dfcf3-25ec-4fa0-b603-d7596e45c4a1",
"metadata": {},
"outputs": [],
"source": [
"def entfernung(x1, y1, x2, y2):\n",
" dx = x2 - x1\n",
" dy = y2 - y1\n",
" print('dx ist', dx)\n",
" print('dy ist', dy)\n",
" return 0.0"
]
},
{
"cell_type": "markdown",
"id": "f8973271-f2b0-4313-b297-cd4ea9d38bc0",
"metadata": {},
"source": [
"Wenn die Funktion richtig funktioniert, sollte `dx ist 3` und `dx ist 4` ausgegeben werden. Wenn dem so ist, wissen wir, dass die Funktion die Argumente richtig erhalten hat und die ersten Berechnungen korrekt durchgeführt wurden. Falls nicht, gibt es nur wenige Zeilen Code, die wir überprüfen müssen.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "548a9fb3-4e1d-49b7-8729-be9a7a691cd9",
"metadata": {},
"outputs": [],
"source": [
"entfernung(1, 2, 4, 6)"
]
},
{
"cell_type": "markdown",
"id": "fa435733-606c-4932-a648-92401848cd71",
"metadata": {},
"source": [
"Als nächstes berechnen wir die Summe der Quadrate von `dx` und `dy`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "23380c0f-db96-4926-80f1-baf4da1c7536",
"metadata": {},
"outputs": [],
"source": [
"def entfernung(x1, y1, x2, y2):\n",
" dx = x2 - x1\n",
" dy = y2 - y1\n",
" dquadrat = dx**2 + dy**2\n",
" print('dquadrat ist: ', dquadrat)\n",
" return 0.0"
]
},
{
"cell_type": "markdown",
"id": "d3cb94bf-476d-4985-bd75-e0ef27715b9a",
"metadata": {},
"source": [
"Wieder rufen wir die Funktion mit bekannten Werten auf und prüfen das Ergebnis (das `25` sein sollte)."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4b16643e-782f-495e-b86f-9decf0e6b85b",
"metadata": {},
"outputs": [],
"source": [
"entfernung(1, 2, 4, 6)"
]
},
{
"cell_type": "markdown",
"id": "d7f4e954-cfa8-4a07-b8d3-745a5c701b75",
"metadata": {},
"source": [
" Abschließend können wir die Funktion `math.sqrt` nutzen um das Ergebnis zu berechnen und zurückzugeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ec306f54-82f8-4af8-b19b-831672e9fddb",
"metadata": {},
"outputs": [],
"source": [
"import math\n",
"def entfernung(x1, y1, x2, y2):\n",
" dx = x2 - x1\n",
" dy = y2 - y1\n",
" dquadrat = dx**2 + dy**2\n",
" ergebnis = math.sqrt(dquadrat)\n",
" print(\"Das Ergebnis ist\", ergebnis)\n",
" return 0.0"
]
},
{
"cell_type": "markdown",
"id": "2307fe03-7b9e-446d-aa5c-0425d2e4f82b",
"metadata": {},
"source": [
"Und dann testen wir die Funktion:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fe0612a0-17a0-451f-a174-afa053569434",
"metadata": {},
"outputs": [],
"source": [
"entfernung(1, 2, 4, 6)"
]
},
{
"cell_type": "markdown",
"id": "0df43737-4ca5-4b9c-b48c-22849719ddb2",
"metadata": {},
"source": [
"Das Ergebnis ist korrekt, aber diese Version der Funktion zeigt das Ergebnis an, anstatt es zurückzugeben. Der Rückgabewert ist weiterhin `0.0`. Wir können das beheben, indem wir die Funktion `print` entfernen und `ergebnis` in die `return`-Anweisung verschieben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f2bc86b6-c977-41e9-b025-6b5d2d8863f5",
"metadata": {},
"outputs": [],
"source": [
"import math\n",
"def entfernung(x1, y1, x2, y2):\n",
" dx = x2 - x1\n",
" dy = y2 - y1\n",
" dquadrat = dx**2 + dy**2\n",
" ergebnis = math.sqrt(dquadrat)\n",
" return ergebnis"
]
},
{
"cell_type": "markdown",
"id": "fa752fdd-23da-49ef-8c71-0cf70e165b77",
"metadata": {},
"source": [
"Diese Version von `distance` ist eine reine Funktion.\n",
"Wenn wir sie auf diese Weise aufrufen, wird nur das Ergebnis angezeigt."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0362a2bb-b3df-4347-af95-b0e7c11ab029",
"metadata": {},
"outputs": [],
"source": [
"entfernung(1, 2, 4, 6)"
]
},
{
"cell_type": "markdown",
"id": "49efe6d6-d8f8-4ebb-ab8a-80a930704283",
"metadata": {},
"source": [
"Und wenn wir das Ergebnis einer Variablen zuweisen, wird nichts angezeigt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9b12a395-d0ba-441c-b749-be6cea4a3c6d",
"metadata": {},
"outputs": [],
"source": [
"d = entfernung(1, 2, 4, 6)"
]
},
{
"cell_type": "markdown",
"id": "fa459813-db78-4ea0-a298-cad555d6d1c7",
"metadata": {},
"source": [
"Die `print`-Anweisungen die wir zwischendurch geschrieben haben sind hilfreich für die Fehlersuche, aber sobald die Funktion funktioniert, sollten wir sie entfernen. Solcher Code wird **Hilfscode** (Englisch: *scaffolding*) genannt, denn er hilft beim Schreiben des Programms aber ist nicht Teil des endgültigen Produkts.\n",
"\n",
"Wenn Sie mit Programmieren beginnen, sollten sie jeweils nur ein bis zwei Zeilen auf einmal hinzufügen. Sobald Sie mehr Erfahrung gesammelt haben, werden Sie merken, dass Sie größere Stücke Code auf einmal schreiben und testen können. In jedem Fall kann Ihnen inkrementelle Entwicklung viel Zeit bei der Fehlersuche ersparen.\n",
"\n",
"Die wichtigsten Punkte dieses Vorgehens sind:\n",
"1. Beginnen Sie mit einem kleinen funktionierenden Programm und führen Sie nur inkrementelle (schrittweise) Änderungen durch. Falls ein Fehler auftritt, sollten Sie zu jeden Zeitpunkt eine Ahnung haben, in welcher Zeile der Fehler sich befindet.\n",
"2. Nutzen Sie Variablen, um Zwischenwerte zu speichern, so dass Sie diese mit `print` ausgeben und überprüfen können.\n",
"3. Sobald das Programm funktioniert, sollten Sie Teile des Hilfscodes entfernen und gegebenenfalls mehrere Anweisungen zu einer Verbundanweisung zusammenfügen, aber nur, wenn sich dadurch die Lesbarkeit des Programms nicht verschlechtert.\n"
]
},
{
"cell_type": "markdown",
"id": "09bfc870-2f36-49f8-b2de-6b5aec76039e",
"metadata": {},
"source": [
"## Boolesche Funktionen\n",
"\n",
"Funktionen können Boolesche Werte zurückliefern. Das ist praktisch, um komplizierte Tests in einer Funktion zu verstecken. Zum Beispiel: "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b157d7d7-a4f2-4fac-ac2d-742beb9ac8e5",
"metadata": {},
"outputs": [],
"source": [
"def ist_teilbar(x, y):\n",
" if x % y == 0:\n",
" return True\n",
" else:\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "b9173688-76e9-4925-95ac-742521a1d0bb",
"metadata": {},
"source": [
"Es ist üblich, Booleschen Funktionen Namen zu geben, die wie Ja-/Nein-Fragen klingen; `ist_teilbar` gibt entweder `True` oder `False` zurück und zeigt damit an, ob `x` durch `y` teilbar ist.\n",
"\n",
"Hier ist ein Beispiel:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9436203b-518e-41cb-a846-ae7c0ca6c055",
"metadata": {},
"outputs": [],
"source": [
"ist_teilbar(6, 4)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0e93dd14-8fc2-4c34-a6db-160d8d8e27f2",
"metadata": {},
"outputs": [],
"source": [
"ist_teilbar(6, 3)"
]
},
{
"cell_type": "markdown",
"id": "6ecff2e9-9e4f-4e36-91ac-de2ec5307c83",
"metadata": {},
"source": [
"Das Ergebnis des `==`-Operators ist ein Boolescher Wert, daher können wir die Funktion kompakter aufschreiben, indem wir den Wert direkt zurückgeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ed8e744a-249e-4f01-aef6-bec70377b834",
"metadata": {},
"outputs": [],
"source": [
"def ist_teilbar(x, y):\n",
" return x % y == 0"
]
},
{
"cell_type": "markdown",
"id": "6959513f-222b-4da0-ac81-82bb4b428828",
"metadata": {},
"source": [
"Boolesche Funktionen werden oft in Verzweigungen genutzt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c5843d62-0236-4514-831a-0681b54458de",
"metadata": {},
"outputs": [],
"source": [
"x = 4\n",
"if ist_teilbar(x, 2):\n",
" print('x ist eine gerade Zahl')"
]
},
{
"cell_type": "markdown",
"id": "cf37e727-4814-4bee-8104-b65532994f5d",
"metadata": {},
"source": [
"Es mag verlockend erscheinen, stattdessen folgendes zu schreiben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c1e87677-ed5d-40a6-ac66-7cc5c24678fa",
"metadata": {},
"outputs": [],
"source": [
"if ist_teilbar(x, 2) == True:\n",
" print('x ist eine gerade Zahl')"
]
},
{
"cell_type": "markdown",
"id": "8a762d7d-afc9-43c4-a123-5509d79c1192",
"metadata": {},
"source": [
"Aber dieser zusätzliche Vergleich ist unnötig.\n",
"\n",
"Schreiben Sie als Übung eine Funktion `ist_zwischen(x, y, z)`, die `True` zurückgibt, wenn $x \\le y \\le z$ gilt und ansonsten `False`."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8054e3fc-1aac-484f-b689-2e05872f5924",
"metadata": {},
"outputs": [],
"source": [
"# implementieren Sie hier"
]
},
{
"cell_type": "markdown",
"id": "a932a966",
"metadata": {
"id": "a932a966"
},
"source": [
"## Noch mehr Rekursion\n",
"\n",
"Wir haben bisher nur eine kleine Teilmenge von Python kennengelernt aber vielleicht interessiert es Sie zu wissen, dass diese Teilmenge eine [*Turing-vollständige*](https://de.wikipedia.org/wiki/Turing-Vollst%C3%A4ndigkeit) Programmiersprache darstellt. Das heißt, alles was berechnet werden kann, können wir mit den bisher erlernten Anweisungen und Funktionen ausdrücken! Jedes jemals geschriebene Programm könnten wir umschreiben, so dass es nur mit den Sprachmerkmalen auskommt, die wir bis jetzt gelernt haben (gut, wir bräuchten noch ein paar Anweisungen, um Geräte wie z.B. die Maus, Festplatten, etc. zu kontrollieren).\n",
"\n",
"\n",
"\n",
"Diese Behauptung zu beweisen, ist eine nicht so ganz einfache Aufgabe, die zuerst von [Alan Turing](https://de.wikipedia.org/wiki/Alan_Turing) gelöst wurde. Er war einer der ersten Informatiker (einige würden argumentieren, dass er ein Mathematiker war, aber viele der ersten Informatiker begannen als Mathematiker). Dementsprechend wird dies oft als [Turing-These](https://de.wikipedia.org/wiki/Church-Turing-These) bezeichnet. \n",
"\n",
"Um einen Idee davon zu bekommen, was wir mit den Werkzeugen, die wir bisher kennengelernt haben, schon erreichen können, wollen wir einige rekursiv definierte mathematische Funktionen implementieren. Eine rekursive Definition ist ähnlich einer [zirkulären Definition](https://en.wikipedia.org/wiki/Circular_definition) (Englisch: *circular definition*) in dem Sinne, dass die Definition eine Referenz auf das, was definiert wird, enthält. Eine richtig zirkuläre Definition ist nicht sehr nützlich:\n",
"\n",
"\n",
"**vorpal:** Ein Adjektiv welches genutzt wird, um etwas zu beschreiben, was vorpal ist.\n",
"\n",
"Wenn Sie so eine Definition in einem Wörterbuch sehen, sind Sie vermutlich verärgert. Andererseits, wenn wir uns die Definition der Fakultätsfunktion heraussuchen (die mit dem Symbol ! bezeichnet wird), finden wir vermutlich etwas in der Art:\n",
"\n",
"\\begin{align}\n",
"0! &= 1\\\\\n",
"n! &= n(n-1)!\n",
"\\end{align}\n",
"\n",
"Diese Definition sagt aus, dass die Fakultät von 0 gleich 1 ist und die Fakultät jedes anderen Wertes $n$ entspricht $n$ multipliziert mit der Fakultät von $n-1$.\n",
"\n",
"Also ist 3! gleich 3 mal 2!, was 2 mal 1! ist, was 1 mal 0! ist. Zusammengenommen ist 3! also gleich 3 mal 2 mal 1 mal 1 - also 6.\n",
"\n",
"Wenn wir etwas rekursiv definieren können, dann können wir auch eine Python-Funktion schreiben, um das ganze auszuwerten. \n",
"\n",
"Wir nutzen hier wieder den Prozess der inkrementellen Entwicklung und beginnen mit einer Funktion, die `n` als Parameter aufnimmt und immer `0` zurückgibt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "23e37c79",
"metadata": {
"id": "23e37c79"
},
"outputs": [],
"source": [
"def fakultaet(n):\n",
" return 0"
]
},
{
"cell_type": "markdown",
"id": "ee1f63b8",
"metadata": {
"id": "ee1f63b8"
},
"source": [
"Nun fügen wir den ersten Teil der Definition hinzu -- wenn das Argument `0` ist, müssen wir einfach `1`zurückgeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5ea57d9f",
"metadata": {
"id": "5ea57d9f"
},
"outputs": [],
"source": [
"def fakultaet(n):\n",
" if n == 0:\n",
" return 1\n",
" else:\n",
" return 0"
]
},
{
"cell_type": "markdown",
"id": "4f2fd7c7",
"metadata": {
"id": "4f2fd7c7"
},
"source": [
"Jetzt befüllen wir den zweiten Teil -- wenn `n` nicht `0` ist, müssen wir einen rekursiven Aufruf machen, um die Fakultät von `n-1` zu finden und dann das Ergebnis mit `n` zu multiplizieren:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b66e670b",
"metadata": {
"id": "b66e670b"
},
"outputs": [],
"source": [
"def fakultaet(n):\n",
" if n == 0:\n",
" return 1\n",
" else:\n",
" rekursion = fakultaet(n-1)\n",
" ergebnis = n * rekursion\n",
" return ergebnis\n",
"\n",
"fakultaet(3)"
]
},
{
"cell_type": "markdown",
"id": "da3d1595",
"metadata": {
"id": "da3d1595"
},
"source": [
"Der Kontrollfluss dieses Programms ist ähnlich dem von `countdown` in [Kapitel 5 - Abschnitt Rekursion](seminar05.ipynb#Rekursion). Wenn wir `fakultaet` mit dem Wert `3` aufrufen, passiert folgendes:\n",
"\n",
"Da `3` ungleich `0` ist, führen wir den zweiten Zweig aus und berechnen die Fakultät von `n-1` ...\n",
"\n",
"> Da `2` ungleich `0` ist, führen wir den zweiten Zweig aus und berechnen die Fakultät von `n-1` ...\n",
">\n",
"> > Da `1` ungleich `0` ist, führen wir den zweiten Zweig aus und berechnen die Fakultät von `n-1` ...\n",
"> >\n",
"> > > Da `0` gleich `0` ist, führen wir den ersten Zweig aus und geben `1` zurück, ohne weitere rekursive Aufrufe zu tätigen.\n",
"> >\n",
"> > Der Rückgabewert, `1`, wird mit `n` multipliziert, was `1` ist, und das Ergebnis zurückgegeben.\n",
">\n",
"> Der Rückgabewert, `1`, wird mit `n` multipliziert, was `2` ist, und das Ergebnis zurückgegeben.\n",
"\n",
"Der Rückgabewert, `2`, wird mit `n` multipliziert, was `3` ist, und das Ergebnis `6` wird zum Rückgabewert des Funktionsaufrufs, der den ganzen Vorgang gestartet hat.\n",
"\n",
"Die folgende Abbildung zeigt wie das Stapeldiagramm für diese Folge von Funktionsaufrufen aussieht:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "455f0457",
"metadata": {
"id": "455f0457",
"tags": []
},
"outputs": [],
"source": [
"from diagram import Frame, Stack, make_binding\n",
"\n",
"main = Frame([], name='__main__', loc='left')\n",
"frames = [main]\n",
"\n",
"ns = 3, 2, 1\n",
"recurses = 2, 1, 1\n",
"results = 6, 2, 1\n",
"\n",
"for n, recurse, result in zip(ns, recurses, results):\n",
" binding1 = make_binding('n', n)\n",
" binding2 = make_binding('recurse', recurse)\n",
" frame = Frame([binding1, binding2],\n",
" name='factorial', value=result,\n",
" loc='left', dx=1.2)\n",
" frames.append(frame)\n",
"\n",
"binding1 = make_binding('n', n)\n",
"frame = Frame([binding1], name='factorial', value=1,\n",
" shim=1.2, loc='left', dx=1.4)\n",
"frames.append(frame)\n",
"\n",
"stack = Stack(frames, dy=-0.45)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a75ccd9b",
"metadata": {
"id": "a75ccd9b",
"tags": []
},
"outputs": [],
"source": [
"from diagram import diagram, adjust\n",
"\n",
"width, height, x, y = [2.74, 2.26, 0.73, 2.05]\n",
"ax = diagram(width, height)\n",
"bbox = stack.draw(ax, x, y)\n",
"# adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "f924c539",
"metadata": {
"id": "f924c539"
},
"source": [
"Das Diagramm zeigt, wie die Rückgabewerte im Stapel weiter nach oben durchgereicht werden. In jedem Block ist der Rückgabewert der Wert von `ergebnis`, was das Produkt von `n` und `rekursion` ist.\n",
"\n",
"Im untersten (letzten) Block existieren die lokalen Variablen `rekursion` und `ergebnis` nicht, denn derjenige Zweig, welcher diese erzeugt, wird nicht ausgeführt.\n",
"\n",
"Nutzen Sie auch [http://pythontutor.com/](http://pythontutor.com/visualize.html#code=def%20fakultaet%28n%29%3A%0A%20%20%20%20if%20n%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20return%201%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20rekursion%20%3D%20fakultaet%28n-1%29%0A%20%20%20%20%20%20%20%20ergebnis%20%3D%20n%20*%20rekursion%0A%20%20%20%20%20%20%20%20return%20ergebnis%0A%0Afakultaet%283%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false), um die einzelnen Schritte nachzuvollziehen!"
]
},
{
"cell_type": "markdown",
"id": "acea9dc1",
"metadata": {
"id": "acea9dc1"
},
"source": [
"## Vertrauensvorschuss\n",
"\n",
"Dem Kontrollfluss zu folgen ist eine Möglichkeit, Programme zu lesen, aber das kann ganz schön aufwendig sein. Eine Alternative ist, dem Code einen **Vertrauensvorschuss** (Englisch: *leap of faith*) zu geben. Wenn wir einen Funktionsaufruf sehen, können wir, statt dem Kontrollfluss zu folgen, einfach *annehmen*, dass die Funktion richtig arbeitet und das korrekte Ergebnis zurückliefert.\n",
"\n",
"Tatsächlich praktizieren wir das bisher schon mit den eingebauten Funktionen. Wenn wir `math.cos` oder `print` aufrufen, schauen wir uns den Rumpf dieser Funktionen nicht an. Wir gehen einfach davon aus, dass sie funktionieren, weil die Leute, die sie geschrieben haben, gute Programmierer$*$innen sind. (Zumindest nehmen wir das vielleicht an ;-) )\n",
"\n",
"Das gleiche gilt, wenn wir eine unserer eigenen Funktionen aufrufen. Beispielsweise haben wir in [Abschnitt 6](#Boolesche-Funktionen) eine Funktion `ist_teilbar` geschrieben, die bestimmt, ob eine Zahl durch eine andere teilbar ist. Sobald wir uns davon überzeugt haben, dass diese Funktion korrekt arbeitet - durch Verstehen des Codes und Testen - können wir die Funktion nutzen, ohne uns den Rumpf noch einmal anzuschauen.\n",
"\n",
"Das gleiche gilt für rekursive Programme. Wenn wir auf einen rekursiven Funktionsaufruf treffen, können wir, anstatt dem Kontrollfluss zu folgen, annehmen, dass der rekursive Aufruf funktioniert (also den richtigen Wert zurückliefert) und uns selbst beispielsweise fragen \"Angenommen, ich kann die Fakultät von $n-1$ berechnen, kann ich dann die Fakultät von $n$ berechnen?\" Das funktioniert offensichtlich - indem wir mit $n$ multiplizieren.\n",
"\n",
"Natürlich ist es etwas seltsam, anzunehmen, dass die Funktion richtig arbeitet, wenn wir sie noch nicht fertig implementiert haben, aber daher wird das ganze ja auch Vertrauensvorschuss genannt. "
]
},
{
"cell_type": "markdown",
"id": "ca2a2d76",
"metadata": {
"id": "ca2a2d76",
"tags": []
},
"source": [
"## Fibonacci\n",
"\n",
"Neben der Fakultät ist ein weiteres übliches Beispiel für eine rekursiv definierte mathematische Funktion die [Fibonacci-Folge](https://de.wikipedia.org/wiki/Fibonacci-Folge):\n",
"\n",
"\\begin{align}\n",
"fibonacci(0) &= 0\\\\\n",
"fibonacci(1) &= 1\\\\\n",
"fibonacci(n) &= fibonacci(n-1) + fibonacci(n-2)\\\\\n",
"\\end{align}\n",
"\n",
"Übersetzt nach Python schaut das so aus:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "cad75752",
"metadata": {
"id": "cad75752"
},
"outputs": [],
"source": [
"def fibonacci(n):\n",
" if n == 0:\n",
" return 0\n",
" elif n == 1:\n",
" return 1\n",
" else:\n",
" return fibonacci(n-1) + fibonacci(n-2)\n",
"\n",
"fibonacci(7)"
]
},
{
"cell_type": "markdown",
"id": "69d56a0b",
"metadata": {
"id": "69d56a0b"
},
"source": [
"Wenn Sie hier versuchen, dem Kontrollfluss zu folgen, wird - selbst für kleine Werte von $n$ - ihr Kopf explodieren. Aber mit Vertrauensvorschuss - wenn wir annehmen dass die zwei rekursiven Aufrufe korrekt funktionieren - wird klar, dass wir das richtige Ergebnis durch Addition der Werte erhalten.\n",
"\n",
"**Übung:** Probieren Sie aus, bis zu welchem Wert von $n$ Sie die Funktion noch aufrufen können, ohne zu lange warten zu müssen. Wenn Sie wollen, können Sie auch `print`-Ausgaben zur Funktion hinzufügen, um den Ablauf nachzuverfolgen (`print(' '*n, n)` erzeugt beispielsweise eine übersichtliche Ausgabe). Rufen Sie die Funktion dann aber besser mit sehr kleinen Werten für `n` auf.\n",
"\n",
"\n",
"\n",
"([Borb](https://commons.wikimedia.org/wiki/File:FibonacciBlocks.svg))"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a5232025-e1cd-431e-84ab-dfa4fb4b993d",
"metadata": {},
"outputs": [],
"source": [
"# implementieren Sie hier "
]
},
{
"cell_type": "markdown",
"id": "26d9706b",
"metadata": {
"id": "26d9706b"
},
"source": [
"## Typen prüfen\n",
"\n",
"Was passiert, wenn wir `fakultaet` mit dem Wert `1.5` als Argument aufrufen?"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5e4b5f1d",
"metadata": {
"id": "5e4b5f1d",
"tags": []
},
"outputs": [],
"source": [
"%%expect RecursionError\n",
"\n",
"fakultaet(1.5)"
]
},
{
"cell_type": "markdown",
"id": "0bec7ba4",
"metadata": {
"id": "0bec7ba4"
},
"source": [
"Das sieht nach einer unendlichen Rekursion aus. Aber wie kann das sein? Die Funktion hat doch einen Basisfall - wenn `n == 0` ist. \n",
"\n",
"\n",
"\n",
"Nun, wenn `n` keine ganze Zahl ist, können wir den Basisfall *verpassen* und eine unendliche Rekursion wird durchgeführt.\n",
"\n",
"Im ersten rekursiven Aufruf ist der Wert von `n` gleich 0.5. Im nächsten ist der Wert `-0.5`. Ab da wird der Wert immer kleiner (immer negativer) aber er wird nie gleich `0` sein. \n",
"\n",
"Wir haben zwei Optionen, dieses Problem zu beheben:\n",
"\n",
"1. Wir können versuchen, die Funktion `fakultaet` zu verallgemeinern, so dass sie auch mit Gleitkommazahlen arbeitet.\n",
"2. Wir können `fakultaet` anpassen, so dass der Typ des übergebenen Arguments geprüft wird.\n",
"\n",
"Die erste Option nennt sich [Gamma-Funktion](https://de.wikipedia.org/wiki/Gammafunktion) und sprengt den Rahmen dieses Kurses. Also schauen wir uns die zweite Option an.\n",
"\n",
"Mit Hilfe der eingebauten Funktion `isinstance` können wir den Typ des Arguments prüfen. Und wenn wir schon einmal dabei sind, können wir auch gleich sicherstellen, dass das Argument positiv ist: "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "73aafac0",
"metadata": {
"id": "73aafac0"
},
"outputs": [],
"source": [
"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)"
]
},
{
"cell_type": "markdown",
"id": "c79d6f40-2212-455b-85a0-b046ddaa53be",
"metadata": {},
"source": [
"Der erste Basisfall behandelt Zahlen die keine ganzen Zahlen sind; der zweite behandelt negative ganze Zahlen. In beiden Fällen gibt die Funktion eine Fehlermeldung aus und gibt `None` zurück, um anzuzeigen, dass etwas schiefgelaufen ist:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c3ebb9bf-2909-4927-8dfb-ac7ad3bad369",
"metadata": {},
"outputs": [],
"source": [
"print(fakultaet(\"fred\"))"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e7681de0-1d2a-4b7a-85e2-3b2ffd16249e",
"metadata": {},
"outputs": [],
"source": [
"print(fakultaet(-2))"
]
},
{
"cell_type": "markdown",
"id": "94fb1130-bfdc-4e60-832a-13d54e1cd075",
"metadata": {},
"source": [
"Wenn wir beide Überprüfungen \"bestehen\", dann wissen wir, dass `n` eine positive ganze Zahl oder Null ist. Damit können wir zeigen, dass die Rekursion terminiert.\n",
"\n",
"Dieses Programm demonstriert ein Entwurfsmuster, welches manchmal **Wächter** (Englisch: *guardian*) genannt wird. Die ersten beiden Verzweigungen agieren als Wächter, die den darauffolgenden Code vor Werten beschützen, die Fehler hervorrufen könnten. Die Wächter ermöglichen uns, die Korrektheit des Codes zu beweisen.\n",
"\n",
"Später werden wir noch eine flexiblere Alternative kennenlernen, um eine Fehlermeldung auszugeben: Ausnahmebehandlung."
]
},
{
"cell_type": "markdown",
"id": "bb47c8a9-56b1-4b47-8ecd-c6a3644ad3fc",
"metadata": {},
"source": [
"## Debugging\n",
"\n",
"Ein großes Programm in kleinere Funktionen zu zerlegen erzeugt ganz natürliche Kontrollpunkte. Wenn eine Funktion nicht funktioniert, gibt es drei Möglichkeiten, die wir in Betracht ziehen sollten:\n",
"\n",
"1. Es stimmt etwas nicht mit den Argumenten der Funktion; eine Vorbedingung ist verletzt.\n",
"2. Es stimmt etwas nicht mit der Funktion; eine Nachbedingung ist verletzt.\n",
"3. Es stimmt etwas nicht mit dem Rückgabewert der Funktion oder der Art und Weise, wie dieser verwendet wird.\n",
"\n",
"Um die erste Möglichkeit auszuschließen, können wir `print`-Anweisungen am Anfang der Funktion einfügen und die Werte der Parameter (und vielleicht deren Typ) ausgeben. Oder wir können Code einfügen, der die Vorbedingungen explizit prüft (wie wir es bei `fakultaet` gerade eben gemacht haben).\n",
"\n",
"Wenn die Parameter gut aussehen, dann können wir eine `print`-Anweisung vor jeder `return`-Anweisung einfügen und den Rückgabewert anzeigen. Falls möglich, prüfen wir den Wert von Hand. Wir können auch in Betracht ziehen, die Funktion mit Werten aufzurufen, die uns das überprüfen des Ergebnisses erleichtern (wie in [Abschnitt 4](#4-Schrittweise-Entwicklung)). \n",
"\n",
"Wenn die Funktion richtig arbeitet (oder es zumindest danach aussieht), sollten wir uns die Stelle anschauen, an der die Funktion aufgerufen wird und sicherstellen, dass der Rückgabewert richtig bzw. überhaupt verwendet wird.\n",
"\n",
"Das Hinzufügen von `print`-Anweisungen am Anfang und Ende einer Funktion kann uns helfen, den Kontrollfluss besser sichtbar zu machen. Hier ist beispielsweise eine Version von `fakultaet` mit `print`-Anweisungen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d39dbf5b-2a55-4500-bcd6-042d4707fd54",
"metadata": {},
"outputs": [],
"source": [
"def fakultaet(n):\n",
" space = ' ' * (4 * n)\n",
" print(space, 'fakultaet', n)\n",
" if n == 0:\n",
" print(space, 'returning 1')\n",
" return 1\n",
" else:\n",
" rekursion = fakultaet(n-1)\n",
" ergebnis = n * rekursion\n",
" print(space, 'returning', ergebnis)\n",
" return ergebnis\n",
" "
]
},
{
"cell_type": "markdown",
"id": "fa612ff7-6a0a-4017-a8fd-0220aaf1ccd2",
"metadata": {},
"source": [
"Dabei ist `space` eine Zeichenkette voller Leerzeichen, die die Einrückung der Ausgabe kontrolliert. Probieren Sie es aus:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c5a55314-45f0-480d-bebf-42b41e5de26e",
"metadata": {},
"outputs": [],
"source": [
"fakultaet(4)"
]
},
{
"cell_type": "markdown",
"id": "c3dbab01-2e13-4deb-9e45-9a77e03e0f83",
"metadata": {},
"source": [
"Wenn Sie der Kontrollfluss verwirrt, dann kann diese Art der Ausgabe hilfreich sein. Es braucht etwas Zeit, guten Hilfscode zu entwickeln, aber etwas Hilfscode kann uns viel Zeit beim Debuggen ersparen.\n",
"\n",
"\n",
"\n",
"([Debugging](https://xkcd.com/1722/), Randall Munroe) [Erklärung des Comics](https://www.explainxkcd.com/wiki/index.php/1722:_Debugging) falls Sie mehr lernen wollen."
]
},
{
"cell_type": "markdown",
"id": "b7c3962f",
"metadata": {
"id": "b7c3962f"
},
"source": [
"## Glossar\n",
"\n",
"Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 6 gelernt haben:\n",
"\n",
"- temporäre Variable:\n",
"- toter Code:\n",
"- inkrementelle Entwicklung:\n",
"- Hilfscode:\n",
"- Wächter: Auch *guardian* genannt, beschützt der \"Wächter\" darauf folgenden Code vor Eingaben, die zu Fehlern führen können.\n",
"- Rückgabewert:\n",
"- reine Funktion:\n",
"\n",
"\n",
"Ergänzen Sie die Liste in eigenen Worten. Das ist eine gute Erinnerungs- und Übungsmöglichkeit."
]
},
{
"cell_type": "markdown",
"id": "ff7b1edf",
"metadata": {
"id": "ff7b1edf"
},
"source": [
"## Übung"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e0f15ca4",
"metadata": {
"id": "e0f15ca4",
"tags": []
},
"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": "0da2daaf",
"metadata": {
"id": "0da2daaf"
},
"source": [
"### Fragen Sie einen virtuellen Assistenten\n",
"\n",
"In diesem Kapitel haben wir eine inkorrekte Funktion gesehen, die enden kann, ohne einen Wert zurückzugeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "90b4979f",
"metadata": {
"id": "90b4979f"
},
"outputs": [],
"source": [
"def absoluter_wert_falsch(x):\n",
" if x < 0:\n",
" return -x\n",
" if x > 0:\n",
" return x"
]
},
{
"cell_type": "markdown",
"id": "69563d4b",
"metadata": {
"id": "69563d4b"
},
"source": [
"Außerdem eine Version der Funktion, die toten Code am Ende beinhaltet:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9217f038",
"metadata": {
"id": "9217f038"
},
"outputs": [],
"source": [
"def absoluter_wert_extracode(x):\n",
" if x < 0:\n",
" return -x\n",
" else:\n",
" return x\n",
"\n",
" return 'This is dead code.'"
]
},
{
"cell_type": "markdown",
"id": "9fe8ae2e",
"metadata": {
"id": "9fe8ae2e"
},
"source": [
"Und wir haben das folgende Beispiel gesehen, das zwar korrekt, aber nicht *idiomatisch* (bedeutet in etwa: so wie Expert$*$innen der Programmiersprache diesen Code verfassen würden) ist:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3168489b",
"metadata": {
"id": "3168489b"
},
"outputs": [],
"source": [
"def ist_teilbar(x, y):\n",
" if x % y == 0:\n",
" return True\n",
" else:\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "14f52688",
"metadata": {
"id": "14f52688"
},
"source": [
"Fragen Sie einen virtuellen Assistenten, was an jeder dieser Funktionen falsch ist und sehen Sie, ob dieser die Fehler bemerkt oder den Stil verbessern kann.\n",
"\n",
"Fragen Sie dann: \"Schreibe eine Funktion, die die Koordinaten zweier Punkte nimmt und die Entfernung zwischen diesen berechnet.\" Prüfen Sie, ob das Ergebnis der Version von `entfernung` ähnelt, die wir in diesem Kapitel geschrieben haben."
]
},
{
"cell_type": "markdown",
"id": "fd23bb60",
"metadata": {
"id": "fd23bb60"
},
"source": [
"### Aufgabe 1\n",
"\n",
"Verwenden Sie inkrementelle Entwicklung, um eine Funktion namens `hypot` zu schreiben, die die Länge der beiden Schenkel eines rechtwinkliges Dreiecks als Argumente aufnimmt und die Länge von dessen Hypotenuse zurückgibt.\n",
"\n",
"Anmerkung: im `math`-Modul gibt es eine Funktion namens `hypot`, die genau dasselbe tut, diese sollen Sie aber nicht für die Übung verwenden!\n",
"\n",
"Selbst wenn Sie die komplette Funktion auf Anhieb richtig schreiben könnten, beginnen Sie mit einer Funktion, die immer `0` zurückgibt. Üben Sie, kleine Veränderungen zu machen und testen Sie denn Code immer wieder.\n",
"Wenn Sie fertig sind, sollte die Funktion nur einen Wert zurückgeben -- es sollte nichts angezeigt werden."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "62267fa3",
"metadata": {
"id": "62267fa3"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5f8fa829",
"metadata": {
"id": "5f8fa829"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3d129b03",
"metadata": {
"id": "3d129b03"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "030179b6",
"metadata": {
"id": "030179b6"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d737b468",
"metadata": {
"id": "d737b468"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "77a74879",
"metadata": {
"id": "77a74879"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0521d267",
"metadata": {
"id": "0521d267"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "468a31e9",
"metadata": {
"id": "468a31e9"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "abbe3ebf",
"metadata": {
"id": "abbe3ebf"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "651295e4",
"metadata": {
"id": "651295e4"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "markdown",
"id": "056c8344-322b-4a14-ac56-4a5b0e9519e5",
"metadata": {},
"source": [
"\n",
"\n",
"([Nina Owens](http://geometry157.blogspot.de/2013/06/types-of-triangles-there-are-several.html))"
]
},
{
"cell_type": "markdown",
"id": "0a66d82a",
"metadata": {
"id": "0a66d82a"
},
"source": [
"### Aufgabe 2\n",
"\n",
"Schreiben Sie eine Boolesche Funktion, `ist_zwischen(x, y, z)`, die `True` zurückgibt wenn $x < y < z$ oder\n",
"$z < y < x$ ist, und in allen anderen Fällen `False`."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0a4ee482",
"metadata": {
"id": "0a4ee482"
},
"outputs": [],
"source": [
"# Hier die Lösung einfügen"
]
},
{
"cell_type": "markdown",
"id": "c12f318d",
"metadata": {
"id": "c12f318d",
"tags": []
},
"source": [
"Sie können diese Beispiele verwenden, um Ihre Funktion zu testen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "956ed6d7",
"metadata": {
"id": "956ed6d7",
"tags": []
},
"outputs": [],
"source": [
"ist_zwischen(1, 2, 3) # sollte True sein"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a994eaa6",
"metadata": {
"id": "a994eaa6",
"tags": []
},
"outputs": [],
"source": [
"ist_zwischen(3, 2, 1) # sollte True sein"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4318028d",
"metadata": {
"id": "4318028d",
"tags": []
},
"outputs": [],
"source": [
"ist_zwischen(1, 3, 2) # sollte False sein"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "05208c8b",
"metadata": {
"id": "05208c8b",
"tags": []
},
"outputs": [],
"source": [
"ist_zwischen(2, 3, 1) # sollte False sein"
]
},
{
"cell_type": "markdown",
"id": "1a6a876f-bae1-4b34-b8e0-e545124b8bcb",
"metadata": {},
"source": [
"### Aufgabe 3\n",
"\n",
"Die [Ackermannfunktion](https://de.wikipedia.org/wiki/Ackermannfunktion), $A(m, n)$ ist folgendermaßen definiert:\n",
"\n",
"\\begin{equation}\n",
"A(m,n) = \n",
"\\begin{cases}\n",
"n+1 & \\ \\ \\text{falls}\\ m=0\\\\\n",
"A(m-1, 1) & \\ \\ \\text{falls}\\ m > 0\\ \\text{und}\\ n = 0\\\\\n",
"A(m-1, A(m, n-1)) & \\ \\ \\text{falls}\\ m > 0\\ \\text{und}\\ n > 0\n",
"\\end{cases}\n",
"\\end{equation}\n",
"\n",
"Schreiben Sie eine Funktion `ack` die die Ackermannfunktion berechnet. Berechnen Sie mit ihrer Funktion `ack(3,4)`, was 125 ergeben sollte. Was passiert für größere Werte von `m` und `n`?\n",
"\n",
"In den folgenden Hinweisen werden wir die Funktion schrittweise entwickeln. Versuchen Sie, die Aufgabe in Partnerarbeit zu lösen und verwenden Sie so wenige Hinweise wie möglich.\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 zuerst den Kopf der Funktion und überlegen Sie sich, wieviele Zweige Ihre Funktion benötigt. Schreiben Sie die entsprechende Anzahl an `if`-Bedingungen (bzw. `elif`-Bedingungen) und `return`-Anweisungen. Keine Sorge, Sie müssen sich an dieser Stelle noch keine Gedanken machen, wie die `if`-Bedingungen aussehen werden.\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",
"Im nächsten Schritt werden wir die korrekten `if`-Bedinungen schreiben. Die geschweifte Klammer in der mathematischen Notation unterscheidet die unterschiedlichen Fälle, die bei bestimmten Bedingungen eintreten. Die Bedingungen stehen hinter dem Schlüsselwort \"falls\". Übersetzen Sie diese Formel in Python. Fügen Sie in jedem Zweig eine `print`-Anweisung ein, die den Zweig eindeutig identifiziert. Wir werden diese Hilfsanweisung später löschen. Testen Sie jetzt, ob Ihre Funktion für verschiedene Eingabewerte den korrekten Zweig ansteuert. Testen Sie auch die Möglichkeiten `m=0` und `n=0`. Im nächsten Hinweis (2.5) finden Sie die verschiedenen `if`-Bedingungen.\n",
" </div> \n",
"</details> \n",
" \n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">2.5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Die `if`-Bedingungen sind: `if m==0:`für den Basisfall, `elif n==0 and m>0:` und `elif m>0 and n>0:`\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",
"Im nächsten Schritt werden wir den korrekten Rückgabewert für den Basisfall eingeben. Anschließend testen Sie Ihre Funktion mit einem Aufruf des Basisfalls. Schauen Sie sich an, wie die Anweisung für die Berechnung des Basisfalls lauten muss. Sie können die korrekte Anweisung in Hinweis 3.5 nachlesen, wenn Sie sich unsicher sind oder Ihr Code nicht korrekt funktioniert.\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">3.5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Die Rückgabe im Basisfall muss `return n+1` lauten. \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",
"Anschließened beschäftigen wir mit der Bedingung `n==0`. Schauen Sie sich auch hier wieder die Formel an und versuchen Sie herauszufinden, welche Werte Sie beim rekursiven Aufruf übergeben müssen. In 4.5 können Sie den korrekten Aufruf nachlesen, wenn Sie dabei Hilfe brauchen. \n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4.5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Die korrekte Anweisung lautet: `return ack (m-1,1)` \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Der letzte Zweig wird aufgerufen, wenn sowohl m als auch n größer als Null sind. Schauen Sie sich genau an, wie die Funktion dabei definiert ist. Dabei fällt auf, dass die Funktion sich selbst im Funktionsaufruf rekursiv aufruft. Schreiben Sie diesen Funktionsaufruf und achten Sie auf die richtige Klammersetzung. Wenn Sie Hilfe brauchen, können Sie sich den korrekten Aufruf in 5.5 anschauen, versuchen Sie es aber zunächst einmal selber und testen Sie, ob bei Ihrem Aufruf das korrekte Ergebnis erscheint. \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5.5 Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Die korrekte `return`-Anweisung lautet: `return ack (m-1, ack(m, n-1))` \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Jetzt funktioniert Ihr Code wie gewünscht. An dieser Stelle ist es sinnvoll, Wächter und einen Doc-String einzubauen. Überlegen Sie dabei, für welche Zahlenbereiche die Funktion definiert ist und stellen Sie sicher, dass ihr Code das zu Beginn überprüft. Schreiben Sie auch einen Doc-String, der beschreibt, welche Eingaben die Funktion akzeptiert und was Sie als Ergebnis ausgibt.\n",
" </div> \n",
"</details>\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bfbe87d0-b7d7-43df-a3bc-34fd3fedc706",
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier die Ackermannfunktion\n",
"\n",
"\n",
"# Testaufruf\n",
"ack(3,4)"
]
},
{
"cell_type": "markdown",
"id": "b4b8be74-d235-418c-9042-059293bdd4f4",
"metadata": {},
"source": [
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n",
"\n",
"Es folgt der Code, der mithilfe der Hinweise entwickelt wurde. Wenn Ihr Code etwas anders aussieht, ist das selbstverständlich okay, solange er das korrekte Ergebnis berechnet.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4e3e345d-f962-4a60-8535-6b955ef82f4d",
"metadata": {},
"outputs": [],
"source": [
"def ack(m,n):\n",
" \n",
" '''Die Funktion erwartet 2 positive ganze Zahlen m und n und berechnet daraus die Ackermannfunktion.\n",
" Werden ungültige Werte eingegeben, ist der Rückgabewert None und ein Fehler wird ausgegeben, andernfalls wird\n",
" das Ergebnis zurückgegeben.'''\n",
" \n",
" if m<0 or n<0:\n",
" print(\"Funktion nicht definiert\")\n",
" return None\n",
" if not isinstance (n, int) or not isinstance (m, int):\n",
" print (\"Funktion nicht definiert\")\n",
" return None\n",
" if m==0:\n",
" return n+1\n",
" if n==0 and m>0:\n",
" return ack (m-1,1)\n",
" if m>0 and n>0:\n",
" return ack (m-1, ack(m, n-1))\n",
" \n",
" \n",
"ack(3,4)"
]
},
{
"cell_type": "markdown",
"id": "e90b601f-fa10-460a-a304-cdd7b903bd8b",
"metadata": {},
"source": [
"### Aufgabe 4\n",
"\n",
"Eine Zahl $a$ ist eine Potenz von $b$, wenn $a$ durch $b$ teilbar ist und $a/b$ eine Potenz von $b$ ist. (Beispielsweise ist 27 eine Potenz von 3, denn 27 ist durch 3 teilbar und 9 ist eine Potenz von 3.) Schreiben Sie eine Funktion `ist_potenz` die Parameter `a` und `b` erwartet und `True` zurückgibt, wenn `a` eine Potenz von `b` ist (ansonsten `False`). \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-info\">Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Überlegen Sie sich, was der Basisfall ist und wie Sie diesen behandeln.\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"Es folgen wie immer Hinweise zum Lösen der Aufgabe. Versuchen Sie zunächst, die Aufgabe in Partnerarbeit zu lösen, so lernen Sie immer am besten. \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 zunächst wie üblich den Kopf der Funktion inklusive der Parameter und schreiben Sie auch bereits die `return`-Anweisungen für die möglichen Ergebnisse der Funktion. Wir kümmern uns anschließend darum, wie diese Werte jeweils erreicht werden.\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",
"Wir müssen uns die beiden Basisfälle überlegen. Diese sind die Fälle, bei denen die Funktion `True` zurückgibt. Die Basisfälle sind `a==b` und `b==1`. Machen Sie sich klar, warum diese Fälle die Basisfälle sind.\n",
" </div> \n",
"</details> \n",
" \n",
" \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Überlegen Sie nun, wie Sie testen können, ob eine Zahl die Potenz einer anderen Zahl ist. Verwenden Sie den `modulo` Operator.\n",
"\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",
"Damit eine Zahl eine Potenz einer anderen Zahl sein kann, muss Sie restlos durch die andere Zahl teilbar sein. Implementieren Sie die Verzweigung und schreiben Sie den Zweig, der `False` zurück gibt. Das ist der Zweig, der ausgeführt wird, wenn alle anderen Bedingungen nicht erfüllt werden.\n",
"\n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Wenn sich $a$ restlos durch $b$ teilen lässt, muss sich in diesem Zweig die Funktion mit einer `return`-Anweisung rekursiv aufrufen. Überlegen Sie sich, welche Werte für $a$ und $b$ übergeben werden müssen.\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",
"Für $a$ müssen Sie $a/b$ übergeben, da Sie ja prüfen müssen, ob $a/b$ auch restlos durch $b$ teilbar ist. Für $b$ müssen Sie daher wieder $b$ übergeben.\n",
"\n",
" </div> \n",
"</details>"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f0d8ab6b-970d-42f2-a905-03387d1d30bb",
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier die Funktion ist_potenz"
]
},
{
"cell_type": "markdown",
"id": "8fd7c716-2bdb-441c-8f73-21b85236be2f",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0e30929e-00ef-457a-ad49-9976205d31d4",
"metadata": {},
"outputs": [],
"source": [
"def ist_potenz(a,b):\n",
" if b==1 or a==b:\n",
" return True\n",
" if a%b==0:\n",
" return ist_potenz (a/b, b) \n",
" else:\n",
" return False\n",
"ist_potenz(12,3)"
]
},
{
"cell_type": "markdown",
"id": "da7b11ee-9b40-4e19-9402-785d6c171497",
"metadata": {},
"source": [
"### Aufgabe 5\n",
"\n",
"Der [größte gemeinsame Teiler](https://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler) (ggT) von $a$ und $b$ ist die größte Zahl die beide Zahlen ($a$ und $b$) ohne Rest teilt.\n",
"\n",
"Eine Möglichkeit den ggT zweier Zahlen zu berechnen, beruht auf der Beobachtung, dass, wenn $r$ der Rest der Division von $a$ durch $b$ ist, $ggT(a,b) = ggT(b,r)$ gilt. Als Basisfall können wir $ggT(a,0)=a$ nutzen.\n",
"\n",
"Schreiben Sie eine Funktion `ggt`, die zwei Parameter `a` und `b` erwartet und den größten gemeinsamen Teiler zurückgibt. Bedenken Sie, dass wir für die Berechnung anders vorgehen als bei der Verwendung des Euklidischen Algorithmus. Nutzen Sie die Hinweise, wenn Sie Hilfe benötigen. \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 zunächst den Kopf der Funktion und die `return`-Anweisung. Lassen Sie die Funktion zuerst einen Platzhalter zurückgeben, wir werden uns in späteren Schritten damit beschäftigen, das korrekte Ergebnis auszugeben.\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 lautet der Basisfall? Schreiben Sie die `if`-Anweisung, die prüft, ob der Basisfall wahr ist. Passen Sie die `return`-Anweisung so an, dass das für den Basisfall passende Ergebnis zurückgegeben wird. Testen Sie, ob dies funktioniert, indem Sie die Funktion mit dem Basisfall aufrufen und sich das Ergebnis anschauen.\n",
"\n",
" </div> \n",
"</details> \n",
" \n",
" \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 wir eine rekursive Funktion implementieren wollen, müssen wir uns überlegen, wie wir den rekursiven Aufruf gestalten können. Schauen Sie sich die Aufgabenstellung an und überlegen Sie, welche Argumente Sie dem Aufruf übergeben. \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",
"\n",
"Wir wollen für $b$ den Rest aus der Divison von $a$ und $b$ übergeben. Berechnen Sie den Wert. Sie können direkt die Berechnung übergeben oder das Ergebnis in einer Variablen speichern und diese Variable übergeben. Für $a$ übergeben wir $b$ aus diesem Funktionsaufruf.\n",
" \n",
" </div> \n",
"</details>"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7d73a256-62c6-4af2-af1d-8dac1bb24648",
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier die Funktion ggt\n"
]
},
{
"cell_type": "markdown",
"id": "10b716ab-23e7-44f9-aa43-1bcfc8384a19",
"metadata": {},
"source": [
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e9e43bec-44fd-46ae-9c89-3bf5b9a09575",
"metadata": {},
"outputs": [],
"source": [
"def ggt (a,b):\n",
" if b==0:\n",
" return a\n",
" r=a%b\n",
" return ggt(b,r)\n",
" \n",
" \n",
"ggt (175,25)"
]
},
{
"cell_type": "markdown",
"id": "1d1446c2-2b3f-4648-a74e-5997c959263c",
"metadata": {},
"source": [
"### Aufgabe 6\n",
"\n",
"Zeichnen Sie (mit Bleistift und Papier) ein Stapeldiagramm für das folgende Programm wenn bei der Ausführung die Zeile `x = x + 1` in der Funktion `a` erreicht wurde. Was gibt das Programm aus?\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5a23df69-e32d-464b-8bda-082cd0764f18",
"metadata": {},
"outputs": [],
"source": [
"def b(z):\n",
" prod = a(z, z)\n",
" print(z, prod)\n",
" return prod\n",
"\n",
"def a(x, y):\n",
" x = x + 1\n",
" return x * y\n",
"\n",
"def c(x, y, z):\n",
" total = x + y + z\n",
" square = b(total)**2\n",
" return square\n",
"\n",
"x = 1\n",
"y = x + 1\n",
"print(c(x, y+3, x+y))"
]
},
{
"cell_type": "markdown",
"id": "01beff4f-ae80-4f82-b401-6eeaa7c73401",
"metadata": {},
"source": [
"### Aufgabe 7\n",
"\n",
"Ein [Palindrom](https://de.wikipedia.org/wiki/Palindrom) ist ein Wort, welches vorwärts und rückwärts gelesen gleich ist. Beispielsweise \"neben\" oder \"hangnah\" (wenn wir Großschreibung ignorieren, gibt es auch Substantive, z.B. \"Reliefpfeiler\" oder \"Anna\"). Rekursiv definiert ist ein Wort ein Palindrom, wenn der erste und letzte Buchstabe identisch sind und der Mittelteil ein Palindrom ist.\n",
"\n",
"Die folgenden Funktionen erwarten eine Zeichenkette als Argument und geben die ersten, letzten und mittleren Buchstaben zurück:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3bbb2923-f744-4174-8414-250dca954c2f",
"metadata": {},
"outputs": [],
"source": [
"def first(word):\n",
" return word[0]\n",
"\n",
"def last(word):\n",
" return word[-1]\n",
"\n",
"def middle(word):\n",
" return word[1:-1]"
]
},
{
"cell_type": "markdown",
"id": "883585fd-71b4-4dfe-a5a5-2edc7b596b49",
"metadata": {},
"source": [
"Wir werden in [Seminar 8](seminar08.ipynb) sehen, wie sie funktionieren.\n",
"\n",
"1. Testen Sie diese Funktionen. Was passiert, wenn Sie `middle` mit einer Zeichenkette mit nur zwei Zeichen aufrufen? Oder mit nur einem Zeichen? Was passiert mit der leeren Zeichenkette, geschrieben `''`, die keine Zeichen enthält?"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "47d7751b-e5ed-40bd-bd1f-558fdfc80a2a",
"metadata": {},
"outputs": [],
"source": [
"# Testen Sie hier die Funktionen first, last und middle "
]
},
{
"cell_type": "markdown",
"id": "433712f6-0b71-40ae-950e-9966678ecc2e",
"metadata": {},
"source": [
"2. Schreiben Sie eine Funktion `ist_palindrom`, die eine Zeichenkette als Argument erwartet und `True` zurückliefert, wenn die Zeichenkette ein Palindrom ist und ansonsten `False`. (Erinnern Sie sich daran, dass Sie mit der eingebauten Funktion `len` die Länge einer Zeichenkette ermitteln können.) \n",
"\n",
"Wie gehabt, folgen jetzt einige Hinweise, versuchen Sie zunächst die Aufgaben in Partnerarbeit zu lösen und verwenden Sie so wenige von den Hinweisen wie möglich, das ist die beste Übung:\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",
"Wir werden uns die Funktionen `first, last` und `middle` zu nutze machen um die Funktion zu schreiben.\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",
"Schreiben Sie zunächst den Kopf der Funktion. Welche Zustände muss die Funktion zurückgeben? Schreiben Sie auch die entsprechenden Rückgabeeingaben, machen Sie sich (noch) keinen Kopf darüber, wie sie entscheiden, welcher Wert zurückgegeben wird. Wenn Sie die Funktion jetzt testen wird immer der erste Rückgabewert, den Sie eingegeben haben zurückgegeben. \n",
" </div> \n",
"</details> \n",
" \n",
" \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 wir automatisch ein Palindrom testen wollen, vergleichen wir immer den ersten mit dem letzen Buchstaben, diese müssen gleich sein. Das bedeutet, dass der hier geschriebene Test bei Palindromen mit unterschiedlich gesetzen Leerzeichen kein Palindrom findet. \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",
" Wir werden die Funktion rekursiv implementieren, wir müssen uns also den Basisfall eines Palindroms überlegen. Wie könnte dieser Basisfall aussehen? \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Der Basisfall für ein Palindrom ist eine Zeichenkette mit nur einem oder keinem Zeichen, diese ist immer ein Palindrom. Für diesen Wert gibt die Funktion den Wert `True` zurück. Verwenden Sie die Funktion `len` um die Länge der Zeichenkette zu testen und schreiben Sie die entsprechende `if`-Bedingung.\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",
"Was muss die Abbruchbedingung sein, wenn die Funktion `False` zurückgeben soll?\n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Verwenden Sie einen Test auf Ungleichheit. Da in einem Palindrom der erste und letzte Buchstabe gleich sein müssen, geben Sie `False` zurück, wenn der Rückgabewert von `first` und `last` nicht gleich ist. \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",
"Abschließend müssen die noch den Rekursiven Funktionsaufruf schreiben. Überlegen Sie, wie Sie die Funktion mit dem zweiten bis vorletzten Buchstaben aufrufen können. \n",
" \n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">9. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Der rekursive Funktionsaufruf muss `ist_palindrom(middle(s))` lauten\n",
" </div> \n",
"</details>\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b264e857-4a65-4735-b51a-423c3fa75cde",
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie die Funktion ist_palindrom"
]
},
{
"cell_type": "markdown",
"id": "d6319d62-0c1c-4bb0-9471-0e362def994d",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d994bc94-3be0-4a44-b419-628e0b2a4701",
"metadata": {},
"outputs": [],
"source": [
"def ist_palindrom(s):\n",
" if len(s)<=1:\n",
" return True\n",
" elif first(s)!=last(s): \n",
" return False\n",
" return ist_palindrom(middle(s))\n",
" \n",
"ist_palindrom(\"gohangasalamiimalasagnahog\")"
]
},
{
"cell_type": "markdown",
"id": "1bb3f503-52cc-47b1-9770-8f3002b0df01",
"metadata": {},
"source": [
" \n",
"\n",
"([Farrar, Straus and Giroux](http://time.com/3771063/mark-saltveit-world-palindrome-championship/))"
]
},
{
"cell_type": "markdown",
"id": "27c0968f-c8b6-4e28-a39a-7580d96e3314",
"metadata": {},
"source": [
" Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). Klicken Sie dazu oben links auf das Disketten-Icon und nutzen Sie beispielsweise einen USB-Stick, E-Mail, Google Drive, Dropbox oder Ihre [HU-Box](https://box.hu-berlin.de/). "
]
},
{
"cell_type": "markdown",
"id": "ba7abb46-fa1f-4bda-a7e9-0e0d2d85ea12",
"metadata": {},
"source": [
"\n",
"\n",
"Herzlichen Glückwunsch! Sie haben das 6. Kapitel geschafft. Weiter geht es in [7: Iteration](seminar07.ipynb)."
]
},
{
"cell_type": "markdown",
"id": "02d2ccdb-c3fa-4db0-b967-602f20b6f080",
"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",
"colab": {
"provenance": []
},
"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
}