{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 10 Listen\n",
"[Chapter 10: Lists](http://greenteapress.com/thinkpython2/html/thinkpython2011.html)\n",
"\n",
"\n",
"In diesem Kapitel lernen wir einen der nützlichsten eingebauten Datentypen von Python kennen: Listen. Wir lernen auch mehr über Objekte und was passieren kann, wenn es mehr als einen Namen für das gleiche Objekt gibt.\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<h1>Inhaltsverzeichnis<span class=\"tocSkip\"></span></h1>\n",
"<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Exkurs:-Was-mir-an-Python-gefällt\" data-toc-modified-id=\"Exkurs:-Was-mir-an-Python-gefällt-1\"><span class=\"toc-item-num\">1 </span>Exkurs: Was mir an Python gefällt</a></span></li><li><span><a href=\"#Eine-Liste-ist-eine-Folge\" data-toc-modified-id=\"Eine-Liste-ist-eine-Folge-2\"><span class=\"toc-item-num\">2 </span>Eine Liste ist eine Folge</a></span></li><li><span><a href=\"#Listen-sind-veränderbar\" data-toc-modified-id=\"Listen-sind-veränderbar-3\"><span class=\"toc-item-num\">3 </span>Listen sind veränderbar</a></span></li><li><span><a href=\"#Eine-Liste-durchlaufen\" data-toc-modified-id=\"Eine-Liste-durchlaufen-4\"><span class=\"toc-item-num\">4 </span>Eine Liste durchlaufen</a></span></li><li><span><a href=\"#Listenoperatoren\" data-toc-modified-id=\"Listenoperatoren-5\"><span class=\"toc-item-num\">5 </span>Listenoperatoren</a></span></li><li><span><a href=\"#Listensegmente\" data-toc-modified-id=\"Listensegmente-6\"><span class=\"toc-item-num\">6 </span>Listensegmente</a></span></li><li><span><a href=\"#Listenmethoden\" data-toc-modified-id=\"Listenmethoden-7\"><span class=\"toc-item-num\">7 </span>Listenmethoden</a></span></li><li><span><a href=\"#Map,-filter-und-reduce\" data-toc-modified-id=\"Map,-filter-und-reduce-8\"><span class=\"toc-item-num\">8 </span>Map, filter und reduce</a></span></li><li><span><a href=\"#Elemente-löschen\" data-toc-modified-id=\"Elemente-löschen-9\"><span class=\"toc-item-num\">9 </span>Elemente löschen</a></span></li><li><span><a href=\"#Listen-und-Zeichenketten\" data-toc-modified-id=\"Listen-und-Zeichenketten-10\"><span class=\"toc-item-num\">10 </span>Listen und Zeichenketten</a></span></li><li><span><a href=\"#Objekte-und-Werte\" data-toc-modified-id=\"Objekte-und-Werte-11\"><span class=\"toc-item-num\">11 </span>Objekte und Werte</a></span></li><li><span><a href=\"#Aliasing\" data-toc-modified-id=\"Aliasing-12\"><span class=\"toc-item-num\">12 </span>Aliasing</a></span></li><li><span><a href=\"#Listen-als-Argumente\" data-toc-modified-id=\"Listen-als-Argumente-13\"><span class=\"toc-item-num\">13 </span>Listen als Argumente</a></span></li><li><span><a href=\"#Debugging\" data-toc-modified-id=\"Debugging-14\"><span class=\"toc-item-num\">14 </span>Debugging</a></span><ul class=\"toc-item\"><li><span><a href=\"#Die-meisten-Listenmethoden-verändern-das-Argument-und-geben-None-zurück.\" data-toc-modified-id=\"Die-meisten-Listenmethoden-verändern-das-Argument-und-geben-None-zurück.-14.1\"><span class=\"toc-item-num\">14.1 </span>Die meisten Listenmethoden verändern das Argument und geben <code>None</code> zurück.</a></span></li><li><span><a href=\"#Sich-für-ein-Idiom-entscheiden-und-dann-dabei-bleiben.\" data-toc-modified-id=\"Sich-für-ein-Idiom-entscheiden-und-dann-dabei-bleiben.-14.2\"><span class=\"toc-item-num\">14.2 </span>Sich für ein Idiom entscheiden und dann dabei bleiben.</a></span></li><li><span><a href=\"#Kopien-erzeugen,-um-Aliasing-zu-vermeiden.\" data-toc-modified-id=\"Kopien-erzeugen,-um-Aliasing-zu-vermeiden.-14.3\"><span class=\"toc-item-num\">14.3 </span>Kopien erzeugen, um Aliasing zu vermeiden.</a></span></li></ul></li><li><span><a href=\"#Glossar\" data-toc-modified-id=\"Glossar-15\"><span class=\"toc-item-num\">15 </span>Glossar</a></span></li><li><span><a href=\"#Übung\" data-toc-modified-id=\"Übung-16\"><span class=\"toc-item-num\">16 </span>Übung</a></span><ul class=\"toc-item\"><li><span><a href=\"#Aufgabe-1\" data-toc-modified-id=\"Aufgabe-1-16.1\"><span class=\"toc-item-num\">16.1 </span>Aufgabe 1</a></span></li><li><span><a href=\"#Aufgabe-2\" data-toc-modified-id=\"Aufgabe-2-16.2\"><span class=\"toc-item-num\">16.2 </span>Aufgabe 2</a></span></li><li><span><a href=\"#Aufgabe-3\" data-toc-modified-id=\"Aufgabe-3-16.3\"><span class=\"toc-item-num\">16.3 </span>Aufgabe 3</a></span></li><li><span><a href=\"#Aufgabe-4\" data-toc-modified-id=\"Aufgabe-4-16.4\"><span class=\"toc-item-num\">16.4 </span>Aufgabe 4</a></span></li><li><span><a href=\"#Aufgabe-5\" data-toc-modified-id=\"Aufgabe-5-16.5\"><span class=\"toc-item-num\">16.5 </span>Aufgabe 5</a></span></li><li><span><a href=\"#Aufgabe-6\" data-toc-modified-id=\"Aufgabe-6-16.6\"><span class=\"toc-item-num\">16.6 </span>Aufgabe 6</a></span></li><li><span><a href=\"#Aufgabe-7\" data-toc-modified-id=\"Aufgabe-7-16.7\"><span class=\"toc-item-num\">16.7 </span>Aufgabe 7</a></span></li><li><span><a href=\"#Aufgabe-8\" data-toc-modified-id=\"Aufgabe-8-16.8\"><span class=\"toc-item-num\">16.8 </span>Aufgabe 8</a></span></li><li><span><a href=\"#Aufgabe-9\" data-toc-modified-id=\"Aufgabe-9-16.9\"><span class=\"toc-item-num\">16.9 </span>Aufgabe 9</a></span></li><li><span><a href=\"#Aufgabe-10\" data-toc-modified-id=\"Aufgabe-10-16.10\"><span class=\"toc-item-num\">16.10 </span>Aufgabe 10</a></span></li><li><span><a href=\"#Aufgabe-11\" data-toc-modified-id=\"Aufgabe-11-16.11\"><span class=\"toc-item-num\">16.11 </span>Aufgabe 11</a></span></li><li><span><a href=\"#Aufgabe-12\" data-toc-modified-id=\"Aufgabe-12-16.12\"><span class=\"toc-item-num\">16.12 </span>Aufgabe 12</a></span></li></ul></li></ul></div>"
]
},
{
"cell_type": "markdown",
"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 Hilfe von pydotplus ist es möglich, Graphen zu visualisieren, die auch direkt im Jupyter Notebook angezeigt werden können. Als Beispiel wird hier ein [Trie](https://de.wikipedia.org/wiki/Trie) erzeugt, der schnellen Zugriff auf die Präfixe einer Liste von Wörtern bildet (so etwas ermöglicht z.B. eine schnelle Wortvervollständigung bei der Eingabe von Wörtern auf der Handy-Tastatur ([siehe](https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1))."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from IPython.display import Image \n",
"import pydotplus\n",
"\n",
"# Der Quellcode für die Klasse `TrieNode` und die Funktion `add` stammt von der Webseite:\n",
"#https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1\n",
"class TrieNode(object):\n",
" def __init__(self, char: str):\n",
" self.char = char\n",
" self.children = []\n",
" self.word = None\n",
" self.counter = 1\n",
"\n",
"def add(root, word):\n",
" node = root\n",
" for char in word:\n",
" found_in_child = False\n",
" # Search for the character in the children of the present `node`\n",
" for child in node.children:\n",
" if child.char == char:\n",
" # We found it, increase the counter by 1 to keep track that another\n",
" # word has it as well\n",
" child.counter += 1\n",
" # And point the node to the child that contains this char\n",
" node = child\n",
" found_in_child = True\n",
" break\n",
" # We did not find it so add a new chlid\n",
" if not found_in_child:\n",
" new_node = TrieNode(char)\n",
" node.children.append(new_node)\n",
" # And then point node to the new child\n",
" node = new_node\n",
" # Everything finished. Mark it as the end of a word.\n",
" node.word = word\n",
"\n",
"# fügt eine Liste von Wörtern hinzu\n",
"def add_words(root, words):\n",
" for word in words:\n",
" add(root, word)\n",
"\n",
"# wandelt den Baum in einen Graphen, also eine Menge von Knoten (vertices) und Kanten (edges) um\n",
"# Eingaben:\n",
"# - root: Wurzelknoten des Baums\n",
"# - vertices: (leere) Liste mit Knoten (jeder Knoten ist vom Typ TrieNode)\n",
"# - edges: (leere) Liste mit Kanten (jede Kante ist ein Tupel von ganzen Zahlen, die die Knoten-IDs repräsentieren)\n",
"def tree_to_graph(root, vertices, edges):\n",
" # Hinzufügen des Wurzelknotens\n",
" if len(vertices) == 0:\n",
" vertices.append(root)\n",
" # wir nummerieren die Knoten durch:\n",
" # jeder Knoten erhält als ID seine Position in der Liste (ab 1 zählend)\n",
" rootid = len(vertices)\n",
" # Hinzufügen der Kindknoten\n",
" for child in root.children:\n",
" vertices.append(child)\n",
" childid = len(vertices)\n",
" \n",
" # Kante zum Kindknoten hinzufügen\n",
" edges.append((rootid, childid))\n",
"\n",
" # Rekursion, falls Kindknoten vorhanden\n",
" if child.children:\n",
" tree_to_graph(child, vertices, edges)\n",
"\n",
"# erzeugt eine Zeichenkette in der Syntax for GraphViz (http://graphviz.org/)\n",
"def build_graph_string(vertices, edges):\n",
" # Konfiguration für Graph, Knoten und Kanten \n",
" s = \"\"\"\n",
"digraph G {\n",
" graph [rankdir=\"LR\"];\n",
" node [sep=\"+0.01,+0.01\", height=\"0\", width=\"0\", shape=\"box\", margin=\"0.05, 0.05\"];\n",
" edge [];\n",
" \"\"\"\n",
" # Hinzufügen der Knoten\n",
" for i, vertice in enumerate(vertices):\n",
" label = vertice.char\n",
" # Knoten, die ein Wort repräsentieren, sollen dieses zusätzlich enthalten\n",
" if vertice.word:\n",
" label += \" (\" + vertice.word + \")\"\n",
" s += ' ' + str(i + 1) + ' [label=\"' + label + '\"];\\n'\n",
" # Hinzufügen der Kanten\n",
" for v1, v2 in edges:\n",
" s += ' ' + str(v1) + ' -> ' + str(v2) + ';\\n'\n",
" s += \"}\"\n",
" return s\n",
" \n",
"\n",
"# Beispielwörter zum Visualisieren - ergänzen Sie die Liste oder probieren Sie andere Wörter\n",
"words = [\"Braten\", \"Brauerei\", \"Brause\", \"Brot\", \"Brett\", \n",
" \"Brei\", \"Brief\", \"Breite\", \"Brille\", \"Brand\", \"Bruder\", \n",
" \"Bruch\", \"Brust\", \"Bronze\", \"Brache\", \"Branche\", \n",
" \"Brandung\", \"Braten\", \"Bratsche\", \"Bremse\", \"Brenner\", \n",
" \"Brezel\", \"Brikett\", \"Brise\", \"Brocken\", \"Bronze\", \n",
" \"Brosche\", \"Brunnen\", \"Brut\"]\n",
"# Alternative: aus einer Datei einlesen\n",
"# words = []\n",
"# fin = open('top10000de.txt', encoding=\"latin1\")\n",
"# for line in fin:\n",
"# if line.startswith(\"Bra\"):\n",
"# words.append(line.strip())\n",
"\n",
"# Wörter zum Trie hinzufügen (in sortierter Reihenfolge, das liest sich leichter)\n",
"root = TrieNode('*')\n",
"add_words(root, sorted(words))\n",
"\n",
"# aus dem Trie einen Graph erzeugen\n",
"vertices = []\n",
"edges = []\n",
"tree_to_graph(root, vertices, edges)\n",
"\n",
"# die Zeichenkette für GraphViz erzeugen\n",
"graphdata = build_graph_string(vertices, edges)\n",
"\n",
"# den Graph zeichnen und anzeigen\n",
"graph = pydotplus.graph_from_dot_data(graphdata) \n",
"Image(graph.create_png())\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Eine Liste ist eine Folge\n",
"\n",
"Wie eine Zeichenkette, ist eine **Liste** eine Folge (*sequence*) von Werten. In einer Zeichenkette sind die Werte Zeichen; in einer Listen können sie von jedem Typ sein. Die Werte in einer Liste heißen **Elemente**, im Englischen manchmal auch *items*.\n",
"\n",
"Es gibt mehrere Möglichkeiten, eine neue Liste zu erzeugen. Die einfachste ist es, Elemente in eckigen Klammern einzuschließen (`[` und `]`):"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[10, 20, 30, 40]\n",
"l = ['crunchy frog', 'ram bladder', 'lark vomit']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das erste Beispiel ist eine Liste mit vier ganzen Zahlen. Das zweite Beispiel ist eine Liste mit drei Zeichenketten. Die Elemente einer Liste müssen nicht vom gleichen Typ sein. Die folgende Liste enthält eine Zeichenkette, eine Gleitkommazahl, eine ganze Zahl und (ja!) eine andere Liste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"['spam', 2.0, 5, [10, 20]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Eine Liste innerhalb einer anderen Liste ist **verschachtelt** (*nested*).\n",
"\n",
"Eine Liste, die keine Elemente enthält wird **leere Liste** genannt. Wir können Sie mit Hilfe von leeren Klammern erzeugen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wir Sie vielleicht schon vermutet haben, können wir Listen Variablen zuweisen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cheeses = ['Cheddar', 'Edam', 'Gouda']\n",
"numbers = [42, 123]\n",
"empty = []\n",
"print(cheeses, numbers, empty)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Listen sind veränderbar\n",
"\n",
"Die Syntax, um auf Elemente einer Liste zuzugreifen, ist die gleiche wie die zum Zugriff auf die Zeichen einer Zeichenkette: der Klammer-Operator. Der Ausdruck innerhalb der Klammern gibt den Index an. Denken Sie daran, dass die Zählung der Indizes mit 0 beginnt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cheeses[0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Anders als Zeichenketten sind Listen veränderbar. Wenn der Klammer-Operator auf der linken Seite einer Zuweisung auftaucht, identifiziert er das Element der Liste, dessen Wert geändert wird."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"numbers = [42, 123]\n",
"numbers[1] = 5\n",
"numbers"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das zweite Element von `numbers`, welches 123 war, ist jetzt 5.\n",
"\n",
"Die folgende Abbildung zeigt das Zustandsdiagramm für `cheeses`, `numbers` and `empty`:\n",
"\n",
"\n",
"\n",
"In diesen Diagrammen sind Listen als Boxen mit dem Wort \"Liste\" oberhalb und den Elementen der Liste innerhalb repräsentiert. Dabei zeigt `cheeses` auf eine Liste mit drei Elementen, die mit 0, 1 und 2 indiziert sind. `numbers` enthält zwei Elemente; das Diagramm zeigt, dass der Wert des zweiten Elements von 123 zu 5 geändert wurde. `empty` verweist auf eine Liste ohne Elemente.\n",
"\n",
"Listenindizes funktionieren genauso wie Indizes bei Zeichenketten:\n",
"- Jeder Ausdruck, der eine ganze Zahl ergibt, kann als Index verwendet werden.\n",
"- Wenn wir versuchen, ein Element zu lesen oder zu schreiben, welches nicht existiert, erhalten wir einen `IndexError`.\n",
"- Wenn ein Index einen negativen Wert hat, zählt er rückwärts vom Ende der Liste.\n",
"\n",
"Der `in`-Operator funktioniert auch für Listen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cheeses = ['Cheddar', 'Edam', 'Gouda']\n",
"'Edam' in cheeses"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"'Brie' in cheeses"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Eine Liste durchlaufen\n",
"\n",
"Üblicherweise durchläuft man die Elemente einer Liste mit einer `for`-Schleife. Die Syntax ist die gleiche wie für Zeichenketten:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for cheese in cheeses:\n",
" print(cheese)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das funktioniert gut wenn wir die Elemente einer Liste lediglich *lesen* wollen. Wenn wir die Elemente aber schreiben oder verändern wollen, benötigen wir die Indizes. Eine übliche Variante das zu tun ist, die eingebauten Funktionen `range` und `len` zu kombinieren: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in range(len(numbers)):\n",
" numbers[i] = numbers[i] * 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Diese Schleife durchläuft die Liste und aktualisiert jedes Element. Dabei gibt `len` die Anzahl der Elemente in der Liste zurück und `range` gibt eine Liste von Indizes zurück, die mit 0 bis $n-1$ nummeriert sind - wobei $n$ die Länge der Liste ist. Bei jedem Schleifendurchlauf erhält `i` den Index des nächsten Elements. Die Zuweisung im Rumpf verwendet `i`, um den alten Wert des Elementes zu lesen den neuen Wert zuzuweisen. \n",
"\n",
"Eine `for`-Schleife über eine leere Liste durchläuft niemals den Schleifenrumpf:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for x in []:\n",
" print(\"This never happens.\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Obwohl eine Liste eine andere Liste enthalten kann, zählt die verschachtelte Liste als ein einzelnes Element. Die Länge der folgenden Liste ist vier: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"allerhand = ['spam', 1, ['Brie', 'Roquefort', 'Pol le Veq'], [1, 2, 3]]\n",
"len(allerhand)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Listenoperatoren\n",
"\n",
"Der `+`-Operator verknüpft Listen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = [1,2,3]\n",
"b = [4,5,6]\n",
"c = a + b\n",
"c"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Der `*`-Operator wiederholt eine Liste so oft wie angegeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[0] * 4"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[1,2,3] * 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das erste Beispiel wiederholt `[0]` viermal. Das zweite Beispiel wiederholt die Liste `[1,2,3]` dreimal.\n",
"\n",
"## Listensegmente\n",
"\n",
"Der Segmentoperator (*slice operator*) funktioniert auch auf Listen: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c', 'd', 'e', 'f']\n",
"t[1:3]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t[:4]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t[3:]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wenn wir den ersten Index weglassen, dann beginnt das Segment mit dem Anfang. Wenn wir den zweiten Index weglassen, dann geht das Segment bis zum Ende. Wenn wir also beide weglassen, dann ist das Segment eine Kopie der gesamten Liste. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t[:]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Da Listen veränderbar sind, ist es oft nützlich, eine Kopie der Liste zu erstellen, bevor man Operationen anwendet, die die Liste verändern.\n",
"\n",
"Wenn wir den Segmentoperator auf der linken Seite einer Zuweisung verwenden, können wir mehrere Listenelemente verändern: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c', 'd', 'e', 'f']\n",
"t[1:3] = ['x', 'y']\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Listenmethoden\n",
"\n",
"Python stellt Methoden bereit, die auf Listen operieren. Zum Beispiel fügt `append` neue Elemente am Ende einer Liste hinzu:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"t.append('d')\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`extend` erwartet eine Liste als Argument und fügt alle Elemente der Liste am Ende hinzu:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t1 = ['a', 'b', 'c']\n",
"t2 = ['d', 'e']\n",
"t1.extend(t2)\n",
"t1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In diesem Beispiel wird `t2` nicht verändert.\n",
"\n",
"Mit `sort` können wir die Elemente einer Liste sortieren - vom kleinsten zum größten:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['d', 'c', 'e', 'b', 'a']\n",
"t.sort()\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Die meisten Listenmethoden sind leer - sie verändern die Liste und geben `None` zurück. Wenn wir fälschlicherweise `t = t.sort()` schreiben, werden wir vom Ergebnis enttäuscht sein.\n",
"\n",
"## Map, filter und reduce\n",
"\n",
"Um die Elemente einer Liste aufzuaddieren, können wir eine Schleife wie die folgende nutzen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def add_all(t):\n",
" total = 0\n",
" for x in t:\n",
" total += x\n",
" return total"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`total` wird mit 0 initialisiert. Bei jedem Durchlauf der Schleife enthält `x` ein Element der Liste. Der `+=`-Operator ist eine Kurzschreibweise zum Verändern einer Variable. Diese **erweiterte Zuweisung** (*augmented assignment statement*),\n",
"\n",
"```python\n",
"total += x\n",
"```\n",
"\n",
"ist äquivalent zu \n",
"\n",
"```python\n",
"total = total + x\n",
"```\n",
"\n",
"Während die Schleife läuft, akkumuliert `total` die Summe der Elemente. Eine Variable die so verwendet wird, wird manchmal **Akkumulator** genannt.\n",
"\n",
"Die Elemente einer Liste aufzuaddieren ist eine so übliche Operation, dass Python dafür die eingebaute Funktion `sum` bereitstellt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = [1, 2, 3]\n",
"sum(t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Eine Operation wie diese, die eine Folge von Elementen in einen einzelnen Wert kombiniert, wird manchmal **Reducer** genannt. \n",
"\n",
"Manchmal wollen wir eine Liste durchlaufen während wir eine andere aufbauen. Beispielsweise erwartet die folgende Funktion eine Liste von Zeichenketten und gibt eine neue Liste zurück, die großgeschriebene Zeichenketten enthält:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def capitalize_all(t):\n",
" res = []\n",
" for s in t:\n",
" res.append(s.capitalize())\n",
" return res"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`res` wird mit der leeren Liste initialisiert. Bei jedem Schleifendurchlauf fügen wir das nächste Element hinzu. Also ist `res` eine andere Art von Akkumulator.\n",
"\n",
"Eine Operation wie `capitalize_all` wird manchmal **Mapper** genannt, da sie eine Funktion auf alle Elemente einer Folge anwendet (*maps*). \n",
"\n",
"Eine andere übliche Operation ist es, einige Elemente einer Liste auszuwählen und dann eine Teilliste zurückzugeben. Beispielsweise erwartet die folgende Funktion eine Liste von Zeichenketten und gibt eine Liste zurück, die nur die Zeichenketten enthält, die ausschließlich aus Großbuchstaben bestehen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def only_upper(t):\n",
" res = []\n",
" for s in t:\n",
" if s.isupper():\n",
" res.append(s)\n",
" return res"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`isupper` ist eine Zeichenketten-Methode, die `True` zurückgibt, wenn die Zeichenkette nur aus Großbuchstaben besteht.\n",
"\n",
"Eine operation wie `only_upper` wird **Filter** genannt, denn sie wählt einige der Elemente aus und filtert andere heraus.\n",
"\n",
"Die meisten üblichen Listenoperatoren können als eine Kombination aus Mapper, Filter und Reducer ausgedrückt werden."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Elemente löschen\n",
"\n",
"Es gibt mehrere Möglichkeiten, um Elemente aus einer Liste zu entfernen. Wenn wir den Index des Elementes kennen, dann können wir es mittels `pop` entfernen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"x = t.pop(1)\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`pop` verändert die Liste und gibt das Element zurück, welches entfernt wurde. Wenn wir keinen Index angeben, dann wird das letzte Element entfernt und zurückgegeben.\n",
"\n",
"Wenn wir den gelöschten Wert nicht benötigen, können wir den `del`-Operator verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"del t[1]\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wenn wir das Element kennen, welches wir entfernen wollen (aber nicht seinen Index), können wir `remove` verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"t.remove('b')\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Der Rückgabewert von `remove` ist `None`.\n",
"\n",
"Um mehr als ein Element zu löschen, können wir `del` mit einem einem Segment-Index nutzen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c', 'd', 'e', 'f']\n",
"del t[1:5]\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wie sonst auch, beinhaltet das Segment alle Elemente bis zum zweiten Index."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Listen und Zeichenketten\n",
"\n",
"Eine Zeichenkette ist eine Folge von Zeichen und eine Liste ist eine Folge von Werten, aber eine Liste von Zeichen ist nicht das gleiche wie eine Zeichenkette. Um eine Zeichenkette in eine Liste von Zeichen zu konvertieren, können wir die Funktion `list` verwenden:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s = 'spam'\n",
"t = list(s)\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Da `list` der Name einer eingebauten Funktion ist, sollten wir diesen nicht als Variablennamen verwenden. Da `l` der `1` sehr ähnlich sieht, sollten wir `l` als Name für Listen vielleicht auch nicht verwenden. Daher verwenden wir hier `t`.\n",
"\n",
"Die `list`-Funktion teilt eine Zeichenkette in die individuellen Zeichen auf. Wenn wir eine Zeichenkette in die enthaltenen Wörter aufteilen wollen, können wir die `split`-Methode verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s = 'pining for the fjords'\n",
"t = s.split()\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ein optionales Argument, genannt **Trennzeichen** (*delimiter*) gibt an, welche Zeichen als Wortgrenzen verwendet werden sollen. Im folgenden Beispiel wird ein Bindestrich als Trennzeichen verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s = 'spam-spam-spam'\n",
"delimiter = '-'\n",
"t = s.split(delimiter)\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das Gegenstück zu `split` ist `join`. Die Methode erwartet eine Liste von Zeichenketten und verkettet die einzelnen Elemente. `join` ist eine Zeichenketten-Methode, daher müssen wir sie auf ein Trennzeichen anwenden und die Liste als Parameter übergeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['pining', 'for', 'the', 'fjords']\n",
"delimiter = ' '\n",
"s = delimiter.join(t)\n",
"s"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In diesem Fall ist das Trennzeichen das Leerzeichen, so dass `join` ein Leerzeichen zwischen die Wörter setzt. Um die Zeichenketten ohne Trennzeichen miteinander zu verketten, können wir die leere Zeichenkette `''` als Trennzeichen verwenden."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Objekte und Werte\n",
"\n",
"Wenn wir diese beiden Zuweisungen ausführen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = 'banana'\n",
"b = 'banana'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"wissen wir, dass sowohl `a` als auch `b` auf eine Zeichenkette verweisen, aber wir wissen nicht, ob sie auf *die selbe* Zeichenkette verweisen. Es gibt zwei mögliche Zustände:\n",
"\n",
"\n",
"\n",
"Im ersten Fall verweisen `a` und `b` auf zwei unterschiedliche Objekte, die den gleichen Wert haben. Im zweiten Fall verweisen sie auf das selbe Objekt.\n",
"\n",
"Um zu prüfen, ob zwei Variablen auf das selbe Objekt verweisen, können wir den `is`-Operator verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = 'banana'\n",
"b = 'banana'\n",
"a is b"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In diesem Beispiel erzeugt Python nur ein Zeichenketten-Objekt und sowohl `a` als auch `b` verwiesen darauf. Wenn wir jedoch zwei Listen erzeugen, erhalten wir zwei Objekte:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = [1, 2, 3]\n",
"b = [1, 2, 3]\n",
"a is b"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das Zustandsdiagramm sieht in diesem Fall so aus:\n",
"\n",
"\n",
"\n",
"In diesem Fall würden wir sagen, dass die beiden Listen **äquivalent** sind, denn sie enthalten die gleichen Elemente, aber sie sind nicht **identisch**, denn sie sind nicht das selbe Objekt. Wenn zwei Objekte identisch sind, sind sie auch äquivalent; aber wenn sie äquivalent sind, sind sie nicht notwendig auch identisch.\n",
"\n",
"Bis jetzt haben wir die Begriffe \"Objekt\" und \"Wert\" synonym verwendet, aber es ist eigentlich präziser, zu sagen, dass ein Objekt einen Wert hat. Wenn wir `[1,2,3]` evaluieren, dann erhalten wir ein Listenobjekt, dessen Werte eine Folge von ganzen Zahlen darstellen. Wenn ein anderes Listenobjekt die gleichen Elemente enthält sagen wir, dass es den gleichen Wert hat, aber es ist nicht das selbe Objekt."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Aliasing\n",
"\n",
"Wenn `a` auf ein Objekt verweist und wir die Zuweisung `b = a` ausführen, dann verweisen beide Variablen auf das selbe Objekt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = [1, 2, 3]\n",
"b = a\n",
"b is a"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das Zustandsdiagramm schaut dann folgendermaßen aus:\n",
"\n",
"\n",
"\n",
"Die Verbindung (*association*) einer Variable mit einem Objekt wird **Referenz** (*reference*) genannt. In diesem Beispiel gibt es zwei Referenzen auf das selbe Objekt.\n",
"\n",
"Ein Objekt mit mehr als einer Referenz hat mehr als einen Namen, daher sagen wir, dass dieses Objekt einen **Alias** besitzt. \n",
"\n",
"Falls das Objekt mit Alias veränderbar ist, dann betreffen Veränderungen, die an einem Alias vorgenommen werden auch den anderen:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"b[0] = 42\n",
"a"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Obwohl dieses Verhalten nützlich sein kann, ist es auch fehleranfällig. Im allgemeinen ist es sicherer, Aliasing zu vermeiden wenn wir mit veränderbaren Objekten arbeiten.\n",
"\n",
"Bei unveränderbaren Objekte wie z.B. Zeichenketten ist Aliasing kein großes Problem. Im Beispiel\n",
"```python\n",
"a = 'banana'\n",
"b = 'banana'\n",
"```\n",
"macht es so gut wie nie einen Unterschied, ob `a` und `b` auf die gleiche Zeichenkette verweisen oder nicht."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Listen als Argumente\n",
"\n",
"Wenn wir eine Liste an eine Funktion als Argument übergeben, erhält die Funktion eine Referenz auf die Liste. Wenn die Funktion die Liste verändert, verändert sich auch die Liste an der aufrufenden Stelle (denn es ist die selbe Liste). Beispielsweise entfernt die Funktion `delete_head` das erste Element einer Liste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def delete_head(t):\n",
" del t[0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Hier sehen wir, wie die Funktion verwendet werden kann und wie sie wirkt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"letters = ['a', 'b', 'c']\n",
"delete_head(letters)\n",
"letters"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Der Parameter `t` und die Variable `letters` sind Aliase für das selbe Objekt. Das Stapeldiagramm beim Aufruf von `delete_head` sieht folgendermaßen aus:\n",
"\n",
"\n",
"\n",
"Die zwei Blöcke `__main__` und `delete_head` teilen sich die Liste, daher zeigen zwei Pfeile auf sie.\n",
"\n",
"Es ist wichtig, dass wir zwischen Operationen unterscheiden, die Listen *verändern* und jenen, die neue Listen *erzeugen*. Beispielsweise verändert die Methode `append` eine Liste, aber der Operator `+` erzeugt eine neue Liste.\n",
"\n",
"Nachfolgend ein Beispiel zu `append`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t1 = [1, 2]\n",
"t2 = t1.append(3)\n",
"print(t1)\n",
"print(t2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Der Rückgabewert von `append` ist `None`.\n",
"\n",
"Nachfolgend ein Beispiel für den Operator `+`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t3 = t1 + [4]\n",
"print(t1)\n",
"print(t3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das Ergebnis des Operators ist eine neue Liste; die Ursprungsliste ist unverändert.\n",
"\n",
"Dieser Unterschied ist wichtig, wenn wir Funktionen schreiben die Listen verändern. Beispielsweise entfernt die folgende Funktion *nicht* das erste Element einer Liste: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def bad_delete_head(t):\n",
" t = t[1:] # FALSCH!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Der Segmentoperator erzeugt eine neue Liste und die Zuweisung sorgt dafür, dass `t` auf die neue Liste verweist, aber das verändert nicht die Ursprungsliste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t4 = [1, 2, 3]\n",
"bad_delete_head(t4)\n",
"t4"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Am Anfang von `bad_delete_head` verweisen `t` und `t4` auf die gleiche Liste. Am Ende verweist `t` auf eine neue Liste, aber `t4` verweist immer noch auf die ursprüngliche, unveränderte Liste.\n",
"\n",
"Eine Alternative ist, eine Funktion zu schreiben, die eine neue Liste erzeugt und zurückgibt. Beispielsweise gibt `tail` alle bis auf das erste Element einer Liste zurück:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def tail(t):\n",
" return t[1:]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Diese Funktion verändert die Ursprungsliste nicht! Folgendermaßen kann die Funktion verwendet werden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"letters = ['a', 'b', 'c']\n",
"rest = tail(letters)\n",
"rest"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Debugging\n",
"\n",
"Unvorsichtige Verwendung von Listen (und anderen veränderbaren Objekten) kann langwieriges Debuggen verursachen. Einige übliche Fehler und Wege, sie zu vermeiden:\n",
"\n",
"### Die meisten Listenmethoden verändern das Argument und geben `None` zurück.\n",
"\n",
"Das ist das Gegenteil zum Verhalten der Methoden für Zeichenketten, die eine neue Zeichenkette zurückgeben und die ursprüngliche Zeichenkette unverändert lassen.\n",
"\n",
"Wenn Sie gewohnt sind, Code für Zeichenketten so zu schreiben:\n",
" \n",
"```python\n",
"word = word.strip()\n",
"```\n",
" \n",
"Dann ist es verlockend, folgenden Code für Listen zu schreiben:\n",
" \n",
"```python\n",
"t = t.sort() # FALSCH!\n",
"```\n",
" \n",
"Weil `sort` keinen Wert (also `None`) zurückliefert, wird die nächste Operation, die wir mit `t` durchführen würden wahrscheinlich fehlschlagen. \n",
" \n",
"Bevor wir Methoden und Operatoren für Listen verwenden, sollten wir aufmerksam die Dokumentation lesen und mit etwas Beispielcode testen.\n",
" \n",
"### Sich für ein Idiom entscheiden und dann dabei bleiben.\n",
"\n",
"Ein Teil des Problems mit Listen ist, dass es zu viele Möglichkeiten gibt, mit Ihnen umzugehen. Beispielsweise können wir zum Entfernen eines Elements `pop`, `remove`, `del` oder sogar den Segmentoperator verwenden. \n",
" \n",
"Um ein Element hinzuzufügen, können wir die Methode `append` oder den Operator `+` verwenden. Angenommen, `t` ist eine Liste und `x` ist ein Listenelement, dann sind die folgenden Varianten korrekt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"x = 'n'\n",
"\n",
"t.append(x)\n",
"print(t)\n",
"\n",
"t = t + [x]\n",
"print(t)\n",
"\n",
"t += [x]\n",
"print(t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"und die folgenden sind falsch:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t.append([x]) # FALSCH!\n",
"print(t)\n",
"\n",
"t = t.append(x) # FALSCH!\n",
"print(t)\n",
"\n",
"t + [x] # FALSCH!\n",
"print(t)\n",
"\n",
"t = t + x # FLASCH!\n",
"print(t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Probieren Sie diese Beispiele (einzeln!) aus und stellen Sie sicher, dass Sie wirklich verstanden haben, was sie tun. Beachten Sie, dass nur das letzte Beispiel einen Laufzeitfehler (*runtime error*) verursacht. Die anderen drei Varianten sind erlaubt, aber sie tun das Falsche.\n",
" \n",
"### Kopien erzeugen, um Aliasing zu vermeiden.\n",
"\n",
"Wenn Sie eine Methode wie z.B. `sort` verwenden wollen, die das Argument verändert, aber Sie benötigen auch die Ursprungsliste, dann können Sie eine Kopie erzeugen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = [3, 1, 2]\n",
"t2 = t[:]\n",
"t2.sort()\n",
"print(t)\n",
"print(t2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In diesem Beispiel könnten Sie auch die eingebaute Funktion `sorted` verwenden, die eine neue, sortierte Liste zurückgibt, ohne die Ursprungsliste zu verändern: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t2 = sorted(t)\n",
"print(t)\n",
"print(t2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Glossar\n",
"\n",
"Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 10 gelernt haben:\n",
"\n",
"- Liste: eine Folge von Werten\n",
"- Element:\n",
"- verschachtelte Liste: \n",
"- Akkumulator:\n",
"- erweiterte Zuweisung\n",
"- Reducer:\n",
"- Mapper:\n",
"- Filter:\n",
"- Objekt:\n",
"- äquivalent:\n",
"- identisch:\n",
"- Referenz:\n",
"- Aliasing:\n",
"- Trennzeichen:\n",
"\n",
"Ergänzen Sie die Liste in eigenen Worten. Das ist eine gute Erinnerungs- und Übungsmöglichkeit."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Übung\n",
"\n",
"Sie finden die Lösungen für die Aufgaben hier: http://thinkpython2.com/code/list_exercises.py\n",
"\n",
"### Aufgabe 1\n",
"Schreiben Sie eine Funktion `nested_sum`, die eine Liste von Listen von ganzen Zahlen erwartet und die Werte der einzelnen Elemente aufaddiert und das Ergebnis zurückgibt. Beispielsweise sollte die Funktion für die Liste `t = [[1, 2], [3], [4, 5, 6]]` den Wert `21` zurückgeben.\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",
"Wie immer schreiben wir zuerst den Kopf der Funktion mit den nötigen Parametern und eine `return`-Anweisung mit einem Platzhalter.\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",
"In diesem Notebook wird eine Funktion vorgestellt, mit der Sie die Summe einer einzelnen Liste berechnen können. Schauen Sie nach, wie diese Funktion heißt und überlegen Sie, wie Sie diese Funktion hier verwenden können.\n",
"\n",
" </div> \n",
"</details> \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",
"Um die Funktion nutzen zu können, die die Summe einer einzelnen Liste berechnet, müssen Sie auf die einzelnen Elemente der Liste von Listen zugreifen. Dafür verwenden Sie eine `for`- Schleife.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Sie brauchen eine Variable, in der Sie die Summen der untergeordneten Listen zusammenaddieren und speichern können.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
" \n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Sie müssen die Variable ausserhalb der `for`-Schleife implementieren. Setzen Sie innerhalb der `for``-Schleife diese Variable immer gleich des aktuellen Wertes plus der Summe der aktuellen Subliste. Am Ende geben Sie diese Zahl aus. \n",
" \n",
" </div> \n",
"</details> "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\n",
"def nested_sum(t):\n",
" # Implementieren Sie hier die Funktion\n",
" "
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"def nested_sum(t):\n",
" total=0\n",
" for element in t:\n",
" total = total+ sum(element)\n",
" return total\n",
" \n",
" \n",
"t = [[1, 2], [3], [4, 5, 6]]\n",
"nested_sum(t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 2 \n",
"\n",
"Schreiben Sie eine Funktion `cumsum`, die eine Liste von Zahlen erwartet und die kumulative Summe zurückgibt, d.h. eine neue Liste, in der das *i*-te Element die Summe der ersten *i + 1* Elemente der Original-Liste enthält. Beispielsweise sollte die Funktion für die Liste `t = [1, 2, 3]` die Liste `[1, 3, 6]` zurückgeben.\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",
"Wie immer schreiben wir zuerst den Kopf der Funktion mit den nötigen Parametern und eine `return`-Anweisung mit einem Platzhalter.\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",
"Da wir eine neue Liste ausgeben wollen, müssen wir eine neue (zunächst leere) Liste erstellen. Ebenso brauchen wir eine Variable, die die aktuelle Summe speichern kann. \n",
" \n",
" </div> \n",
"</details> \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",
"Wir müssen die alte Liste in einer 'for'-Schleife durchlaufen. Was sind die zwei Schritte, die innerhalb der Schleife vorgenommen werden müssen?\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
" \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Zunächst muss die neue Summe berechnet werden. Anschließend muss dieses Ergebnis an die (neue) Ergebnisliste angehängt werden.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
" \n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Denken Sie daran, dass die 'return'-Anweisung am Ende die neue Liste zurückgeben muss.\n",
" \n",
" </div> \n",
"</details> "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def cumsum(t):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Testen Sie die Funktion mit verschiedenen Listen als Eingabe.\n",
"\n",
"Welche Liste müssten Sie der Funktion `cumsum` übergeben, um als Ergebnis die Liste `[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]` der ersten zehn Fibonacci-Zahlen zu erhalten?\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-success\">Lösung für die Liste</summary>\n",
" <div class=\"alert alert-success\" role=\"alert\">\n",
" Die korrekte Liste ist: [1,0,1,1,2,3,5,8, 13, 21]\n",
" </div> \n",
"</details> "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#Testen Sie hier verschiedene Listen, bis Sie das korrekte Ergebnis erhalten."
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"def cumsum(t):\n",
" total = 0\n",
" result = []\n",
" for element in t:\n",
" total += element\n",
" result.append(total)\n",
" return result\n",
"\n",
"t = [1, 2, 3] \n",
"cumsum(t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 3\n",
"Schreiben Sie eine Funktion `middle`, die eine Liste als Argument erwartet und eine neue Liste zurückgibt, die alle Elemente bis auf das erste und letzte der Ausgangsliste enthält. Beispielsweise sollte die Funktion für die Liste `t = [1,2,3,4]` die Liste `[2,3]` zurückgeben:\n",
"\n",
"```python\n",
"t = [1,2,3,4]\n",
"middle(t)\n",
"```\n",
"sollte `[2,3]` ergeben. \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",
"Wie immer schreiben wir zuerst den Kopf der Funktion mit den nötigen Parametern und eine `return`-Anweisung mit einem Platzhalter.\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 wollen den 'Segment' Operator verwenden, um die Teilliste auszuwählen. Schauen Sie sich nochmal an, wie dieser verwendet wird.\n",
" \n",
" </div> \n",
"</details> \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",
"Zunächst wollen wir dafür sorgen, dass die Liste ab dem zweiten Element zurückgegeben wird. Welchen Index hat das erste Element der Liste, welchen das zweite? Testen Sie ob Ihre Funktion korrekt die Liste ab dem 2. Element zurückgibt.\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",
"In Notebook 8 haben Sie gelernt, wie Sie von hinten auf Zeichenketten zugreifen können, ohne ihre Länge zu kennen. Das funktioniert analog für Listen. Schauen Sie nochmal in Notebook 8 nach, wenn Sie sich nicht mehr sicher sind (nutzen Sie gegebenenfalls `str`+`f`und suchen Sie nach `rückwärts` um die entsprechende Stelle zu finden). Achten Sie dabei darauf, wie die Segmente ausgegeben werden. Probieren Sie verschiedene Indices bis es richtig funktioniert.\n",
" \n",
" </div> \n",
"</details> "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def middle(t):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"def middle(t):\n",
" return t[1:-1]\n",
" \n",
"t=[1,2,3,4]\n",
"middle(t)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 4\n",
"Schreiben Sie eine Funktion `chop`, die eine Liste als Argument erwartet, das erste und letzte Element entfernt und `None` zurückgibt. Beispielsweise sollte\n",
"\n",
"```python\n",
"t = [1,2,3,4]\n",
"chop(t)\n",
"t\n",
"```\n",
"`[2,3]` ergeben.\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",
"Zunächst mag es scheinen, als sei diese Funktion dasselbe wie `middle`, aber wenn Sie ihre ursprüngliche Liste ausgeben lassen, nachdem Sie `middle` angewendet haben, dann ist die Liste unverändert. Im Gegensatz dazu verändern wir mit `chop` die ursprüngliche Liste.\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",
"Schauen Sie in diesem Notebook nach, wie Sie Elemente anhand ihres Indexes löschen können. \n",
" </div> \n",
"</details> \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",
"Wir benötigen 2 Zeilen, eine für jeden Index, den wir entfernen wollen. Testen Sie ob Sie den richtigen Index entfernt haben indem Sie die Funktion testen und verändern Sie gegebenenfalls den Index bis Sie das richtige Ergebnis erhalten. \n",
" </div> \n",
"</details> "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def chop(t):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"def chop (t):\n",
" del t[0]\n",
" del t[-1]\n",
"\n",
"t=[1,2,3,4]\n",
"chop (t)\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 5\n",
"Schreiben Sie eine Funktion `is_sorted`, die eine Liste als Argument erwartet und `True` zurückgibt, falls die Liste in aufsteigender Reihenfolge sortiert ist und ansonsten `False`. Also zum Beispiel:\n",
"\n",
"```python\n",
">>> is_sorted([1, 2, 2])\n",
"True\n",
">>> is_sorted(['b', 'a'])\n",
"False\n",
"```\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",
"Wir müssen die eingegebene Liste mit der sortierten Version derselben vergleichen. Sind Sie gleich, gibt der Vergleichsoperator `True` zurück, ansonsten `False`.\n",
" \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",
"In diesem Notebook haben Sie eine eingebaute Funktion kennengelernt, die eine gegebene Liste sortiert. Schauen Sie nach, wie diese Funktion aussieht und wenden Sie diese auf die eingegebene Liste an.\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",
"Mit `==`können Sie zwei Listen in einer Zeile vergleichen. Das Ergebnis des Vergleichs ist ein `boolscher`-Wert, also `True` oder `False`. Daher können Sie die ganze Funktion in einer Zeile implementieren. \n",
" \n",
" </div> \n",
"</details> "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def is_sorted(t):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"def is_sorted(t):\n",
" return t == sorted(t)\n",
"\n",
"print(is_sorted([1, 2, 2]))\n",
"print(is_sorted(['b', 'a']))\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 6\n",
"\n",
"Zwei Wörter bilden ein *Anagramm*, wenn wir die Buchstaben des einen Wortes so anordnen können, dass sich das andere Wort ergibt. (Beispielsweise bilden *LAGER* und *REGAL* ein Anagramm.) Schreiben Sie eine Funktion `is_anagram`, die zwei Zeichenketten erwartet und `True` zurückgibt, falls sie ein Anagramm bilden (sonst `False`). \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",
"Ein Anagramm liegt dann vor, wenn die Zeichen in einer Zeichenkette und die Zeichen in einer anderen Zeichenkette genau die gleichen sind. Wie können Sie das überprüfen?\n",
" \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",
"Zeichenketten und Listen verhalten sich sehr ähnlich. Sie können die `sorted`-Funktion auf Zeichenketten anwenden und erhalten eine sortierte Liste von Zeichen in einer Zeichenkette. Bilden zwei Zeichenketten ein Anagramm sind die sortierten Listen gleich. Gehen Sie analog zu `is_sorted()` vor um zu prüfen, ob die Zeichenketten gleich sind.\n",
" \n",
" </div> \n",
"</details> \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 Sie sich im englischsprachigen Raum bewegen, sind sie nun fertig, da Sie Groß- und Kleinschreibung ignorieren können. Wenn wir für die deutsche Sprache akurate Ergebnisse erhalten wollen, müssen wir sicherstellen, dass die Zeichenketten nur Kleinbuchstaben enthält, da sonst zum Beispiel 'Lager' und 'Regal' nicht gleich sind. Wie können wir sicherstellen, dass dies der Fall ist? (D.h. gegebenenfalls Großbuchstaben umwandeln?)\n",
"\n",
" </div> \n",
"</details> \n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Verwenden Sie die Zeichenkettenmethode `lower()` um die Zeichenkette umzuwandeln. Vergessen Sie nicht, die aktualisierten Zeichenketten zu speichern. Testen Sie Ihre Funktion mit Groß- und Kleinbuchstaben.\n",
" </div> \n",
"</details>"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def is_anagram(v, w):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Zusatzaufgabe: Suchen Sie in der Wortliste aus dem [9. Kapitel](notebooks_seminar09.ipynb) nach Anagrammen."
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"def is_anagram(v, w):\n",
" # Implementieren Sie hier die Funktion\n",
" v=v.lower()\n",
" w=w.lower()\n",
" return sorted (v) == sorted (w)\n",
" \n",
"is_anagram('Lager','Regal')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 7\n",
"Schreiben Sie eine Funktion `has_duplicates`, die eine Liste als Argument erwartet und `True` zurückgibt, falls ein Element der Liste mehr als einmal in der Liste enthalten ist. Die Funktion soll die Ursprungsliste nicht verändern.\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",
"Als Basis soll die Funktion `False` zurückgeben, nur wenn zwei gleiche Elemente gefunden werden, wird stattdessen `True` zurückgegeben. Schreiben Sie die beiden möglichen Rückgaben. Wo genau diese stehen müssen, überlegen wir uns im Laufe der Entwicklung der Funktion.\n",
" \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",
"Wenn wir schauen wollen, ob sich Elemente in einer Liste wiederholen, ist es sinnvoll, die Liste zu sortieren. Wenn die Liste sortiert ist, stehe gleiche Elemente nebeneinander, statt an beliebigen -- unabhängigen -- Stellen in der Liste. Lassen Sie sich die sortierte Liste in einer 'print'-Anweisung innerhalb der Funktion ausgeben und geben Sie gleichzeitig die Originalliste aus um sicher zu gehen, dass Sie die Originalliste nicht verändern.\n",
" \n",
" </div> \n",
"</details> \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",
"Um in einer sortierten Liste zu überprüfen, ob es Duplikate gibt, müssen wir lediglich für jeden Index schauen, ob der benachbarte Index das gleiche Element enthält. Da Sie jeden Index ansteuern, müssen Sie immer nur einen Nachbarn überprüfen, je nachdem, welchen Sie auswählen, müssen Sie den Start und End Index gegebenenfalls anpassen. Hier schauen wir uns immer den rechten Nachbarn (also den mit dem nächstgrößeren Index) an. \n",
"\n",
" </div> \n",
"</details> \n",
"\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 durchlaufen die Liste mit einer `for`-Schleife. Nutzen Sie die `len`-Funktion um die Länge der Liste zu ermitteln und zu schauen, wie oft die `for`-Schleife durchlaufen werden muss. Achten Sie dabei auf den Index um sogenannte `off by one` Fehler zu vermeiden. \n",
" </div> \n",
"</details>\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"In diesem Fall wollen wir in der `for`-Schleife 2 Elemente der Liste vergleichen, daher können wir die Liste nicht einfach Element für Element durchlaufen, sondern benötigen einen Index. Schreiben Sie die Schleife und lassen Sie sich jeweils den Index ausgeben, um zu testen, dass alle benötigten Werte angenommen werden\n",
" </div> \n",
"</details>\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"In der Schleife müssen Sie das Element mit dem Index i mit dem Element mit dem Index i+1 vergleichen. Sind diese gleich, kann die Funktion abbrechen und `True` zurückgeben. Wird die Schleife durchlaufen, ohne das zwei Elemente gleich sind, wird die Schleife verlassen und Sie geben `False` zurück\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def has_duplicates(t):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"def has_dublicates(t):\n",
" '''Takes list or string\n",
" Returns True if dublicates exist, otherwise returns False'''\n",
" \n",
" t=sorted(t)\n",
" \n",
" for i in range (len(t)-1):\n",
" if t[i] == t[i+1]:\n",
" return True\n",
" return False\n",
"\n",
"\n",
"\n",
"t=['h','a', 'l', 'l', 'o']\n",
"print (has_dublicates(t))\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 8\n",
"In dieser Aufgabe geht es um das sogenannte \"Geburtstags-Paradoxon\" über das Sie mehr in [Wikipedia](http://en.wikipedia.org/wiki/Birthday_paradox) lesen können.\n",
"\n",
"Wenn 23 Studierende in Ihrem Kurs sind, wie hoch ist dann die Wahrscheinlichkeit, dass zwei davon am gleichen Tag Geburtstag haben? Sie können diese Wahrscheinlichkeit schätzen, indem Sie zufällig 23 Geburtstage auswürfeln und prüfen, ob mindestens zwei davon identisch sind.\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-info\">Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Sie können zufällige Geburtstage mit Hilfe der Funktion `randint` aus dem <a href= \"https://docs.python.org/3/library/random.html\">Modul `random`</a> erzeugen.\n",
" \n",
" </div> \n",
"</details> \n",
"\n",
"Die Originallösung aus dem Buch finden Sie [hier](http://thinkpython2.com/code/birthday.py), es folgen wie gewohnt Lösungsschritte mit denen Sie versuchen können, die Aufgabe selbstständig zu lösen.\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"In Essenz besteht diese Aufgabe aus 2 Teilen. Zum einen müssen wir eine Funktion schreiben, die eine gegebene Anzahl an Geburtstagen auswürfelt. Zum anderen brauchen wir eine Funktion, die prüft, ob zwei davon identisch sind. Und da eine einzelne Simulation keine guten Daten zu der Wahrscheinlichkeit des Datensets liefert, sollten wir eine Funktion schreiben, die diesen Test wiederholt durchführt und dann das Ergebnis zurückgibt. \n",
" \n",
" </div> \n",
"</details> \n",
"\n",
"Erstellen der Geburtstagsliste:\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 fangen mit dem Erzeugen der Geburtstagsliste an. Schreiben Sie zunächst den Kopf der Funktion. Wir verwenden n=23 als Parameter, so kann die Funktion ausgeführt werden, ohne dass ein Wert für die Länge der Liste festgelegt werden muss, aber wir haben in der Zukunft die Möglichkeit Listen unterschiedlicher Länge zu erzeugen. Ein so gestellter Parameter sagt: \"Setze für n 23 ein, ausser der Funktionsaufruf spezifiziert etwas anderes\". \n",
" </div> \n",
"</details> \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",
"Wir brauchen eine leere Liste, in der wir die zufällig erstellten Geburtstage speichern können. Erstellen Sie diese. \n",
" </div> \n",
"</details> \n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Um uns das Erzeugen von Geburtstagen einfacher zu machen, speichern wir Geburtstage nicht im TT-MM Format, sondern als eine Zahl zwischen 1 und 365 (oder 366, wenn man Schaltjahre in Betracht ziehen möchte). Da wir nur eine zufällige Zahl erzeugen wollen, können wir sehr einfach die `randint`Funktion verwenden. Die Syntax für `randint` ist: `randint(1,365)`. Wobei in den Klammern zuerst die kleinste mögliche Zahl, dann ein Komma und dann die größtmögliche Zahl steht. Vergessen Sie nicht den so erzeugten Wert in einer Variablen zu speichern. \n",
" </div> \n",
"</details>\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Es reicht natürlich nicht, einen zufälligen Geburtstag zu erzeugen, wir brauchen eine Liste von 23 zufälligen Geburtstagen. Wir können eine `for`-Schleife verwenden um `randint` entsprechend oft aufzurufen und den erzeugten Wert an die Liste anzuhängen.\n",
" </div> \n",
"</details>\n",
"\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, die Liste zurückzugeben. Rufen Sie die Funktion mehrfach auf und schauen Sie sich die Rückgabe an. Wird immer die korrekte Anzahl an Werten zurückgegeben? Liegen alle Werte im erwarteten Bereich? \n",
" </div> \n",
"</details>\n",
"\n",
"Nun haben Sie eine Liste mit zufälligen Geburtstagen. Wie können Sie weiter vorgehen?\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Überlegen Sie, wie Sie prüfen können, ob zwei Werte der Liste gleich sind. Sie dürfen Code, den Sie bereits geschrieben haben gerne wiederverwenden.\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",
"Verwenden Sie die Funktion `has_dublicates`, die Sie bereits geschrieben haben um zu prüfen, ob Sie zwei gleiche Geburtstage haben. \n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"Da ein einzelner Test nichts über die Wahrscheinlichkeit aussagen kann, ob ein Phänomen auftritt, schreiben wir nun eine Funktion, die diesen Test mehrfach durchführt und das Ergebnis ausgibt.\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",
"Schreiben Sie zunächst den Kopf der Funktion, überlegen Sie, ob Sie Werte zurückgeben lassen wollen oder lieber mit `print`-Statements arbeiten möchten. Beides ist möglich. Im Beispielcode wird mit `print`-Statements gearbeitet. Dieser Funktion müssen Sie übergeben, wie oft Sie den Test durchführen wollen. \n",
" </div> \n",
"</details>\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">10. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"Da wir am Ende wissen möchten wie viele der Tests gleiche Geburtstage hatten, müssen wir einen Zähler initialisieren, der erhöht wird, wann immer der Test auf Duplikate positiv ist. \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",
"Um den Test wiederholt mit zufälligen Werten durchzuführen, benötigen wir eine `for`-Schleife, die so oft läuft, wie wir im Kopf der Funktion angegeben haben. In der Schleife müssen wir die Geburtstagsliste erzeugen, auf Duplikate testen und wenn der Test positiv ausfällt den Zähler um 1 erhöhen. \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",
"Sie könnten die Geburtstagsliste in einer Variablen erstellen, diese Variable an `has_dublicates` übergeben, den Wert von `has_dublicates` in einer weiteren Variablen speichern und diese dann an eine `if`-Bedingung übergeben und dann die Zählererhöhung schreiben. Alternativ kann man die Funktionsaufrufe schachteln. Wir müssen die Liste nicht speichern, stattdessen können wir in der `if`-Bedingung auf has_dublicates() testen. has_dublicase wiederum kann birthdays() aufrufen. \n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">12. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"Nach dem die Schleife erfolgreich durchlaufen wurde, haben Sie die Zahl an erfolgreichen Versuchen. Diese müssen wir jetzt noch ausgeben. Schreiben Sie ein `print`-Statement, das sagt, wie viele Versuche sie durchgeführt haben, und wie viele davon mindestens einen doppelten Geburtstag hatte. \n",
"Im Beispielcode wird auch noch berechnet und ausgedruckt, welcher Anteil an Tests dies ist in Prozent. Dafür können Sie die Anzahl an Versuchen mit doppeltem Geburtstag durch die totale Anzahl an versuchen teilen und das Ergebnis mit 100 multiplizieren. \n",
" </div> \n",
"</details>\n",
"\n",
"Denken Sie daran Ihre Funktion zu testen. Was stellen Sie fest, wenn Sie die Wahrscheinlichkeitsfunktion mit n=10.000 mehrfach hintereinander aufrufen?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from random import randint\n",
"\n",
"# Implementieren Sie hier Ihr Programm"
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"from random import randint\n",
"\n",
"def birthdays (n=23):\n",
" bday_list=[]\n",
" for i in range (n):\n",
" birthday= randint(1, 365)\n",
" bday_list.append(birthday)\n",
" return bday_list\n",
"\n",
"\n",
"def likelyhood(n):\n",
" count=0\n",
" for i in range (n):\n",
" if has_dublicates(birthdays()):\n",
" count= count+1\n",
" percentage= (count/n)*100\n",
" print (\"In %d Versuchen gab es %d Versuche in denen mindestens 2 Studierende am selben Tag Geburtstag haben.\"\n",
" %(n,count))\n",
" print (\"Das sind %d Prozent der Fälle\" %percentage)\n",
" \n",
"likelyhood(10000)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 9\n",
"Schreiben Sie eine Funktion, die die Datei \"top10000de.txt\" oder \"words.txt\" einliest (siehe [Abschnitt 9.1](seminar09.ipynb#9.1-Wortlisten-einlesen)) und daraus eine Liste erzeugt mit den Wörtern als Elementen erzeugt. Implementieren Sie zwei Versionen dieser Funktion: eine, die die Methode `append` verwendet und eine, die den Operator `+` mittels `t = t + [wort]` verwendet. Welche der beiden Versionen hat eine größere Laufzeit? Warum?\n",
"\n",
"Eine Lösung für diese Aufgabe finden Sie hier: http://thinkpython2.com/code/wordlist.py\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Wenn wir die Laufzeit der beiden Methoden unterscheiden wollen, können wir ein Gerüst schreiben, das die Wortliste einliest und dann so verarbeitet, dass die Worte an die Liste angehängt werden können. Die Zeile in der jeweils das Wort an die Liste angehängt wird, unterscheidet sich dann in beiden Funktionen.\n",
" \n",
" </div> \n",
"</details> \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 erstes müssen wir eine leere Liste erzeugen und das Dokument mit der Wortliste öffnen. Wenn Sie sich nicht mehr daran erinnern können, wie Wortlisten geöffnet werden, schauen Sie in [Notebook 9](notebook_seminar09.ipynb) nach.\n",
"\n",
" </div> \n",
"</details> \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",
"In Notebook 9 haben Sie auch gesehen, wie Sie das Dokument Wort für Wort durchlaufen können. Schreiben Sie diese Schleife.\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",
"An dieser Stelle müssen Sie das Wort zu der Liste hinzufügen, hier unterscheiden sich die beiden Funktionen. Überlegen Sie was anders sein könnte.\n",
" \n",
" </div> \n",
"</details> \n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4.5 Hinweis - Append</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Wenn Sie ein Element mit Hilfe von `append()` an die Liste anhängen wollen lautet die gesamte Zeile `t.append(word)` **nicht** `t = t.append(word)`.\n",
" \n",
" </div> \n",
"</details> \n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4.5 Hinweis - Add</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Im Gegensatz dazu muss die gesamte Zeile für das Anhängen mit dem `+`-Zeichen `t= t+[word]`lauten, wenn Sie `t+[word]` nicht wieder `t` zuweisen, wird die Liste nicht länger\n",
" \n",
" </div> \n",
"</details> \n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis </summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Abschließend müssen Sie die vollständige Liste zurück zu geben. Verwenden Sie dafür ein `return`-Statement\n",
"\n",
" </div> \n",
"</details> \n",
"\n",
"Nun können Sie mit Bachgefühl bereits abschätzen welche Funktion schneller ist und welche langsamer. Im folgenden schreiben wir eine Funktion, die die tatsächliche Laufzeit zurückgibt um die Situation genau abzuschätzen.\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis </summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"In der Musterlösung wird mithilfe des `time`-Moduls ermittelt, wie lange die Funktionen jeweils zum Durchlaufen benötigen.\n",
" \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",
" Zunächst wird der Zeitpunkt festgehalten, bevor die Funktion gestartet wird, dies geschieht indem die aktuelle Zeit in Sekunden und Millisekunden seit dem Referenzzeitpunkt mit `time.time()` abgefragt und in einer Variablen gespeichert wird.\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",
"Dann wird einfach der Funktionsaufruf ausgeführt.\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",
"Sobald der Funktionsaufruf beendet ist, wird erneut die aktuelle Zeit abgefragt. Zieht man davon die Zeit ab, die wir zuvor gespeichert haben, bleibt die Anzahl an Sekunden übrig, die zwischen Referenzzeitpunkt und Ende des Funktionsaufrufs vergangen sind. Vergessen Sie nicht, das Ergebnis ausgeben zu lassen!\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"Im Folgenden wird einmal kurz das Ergebnis der Aufgabe besprochen:\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-success\">Lösung </summary>\n",
" <div class=\"alert alert-success\" role=\"alert\">\n",
" \n",
"Die Additionsfunktion hat eine größere Laufzeit. In append wird die Liste aufgerufen, bis ans Ende gelaufen und dann einmal das neue Wort geschrieben, in der Additionsfunktion hingegen, muss die liste jedes mal komplett neu geschrieben werden.\n",
" \n",
" </div> \n",
"</details>\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier die beiden Varianten Ihrer Funktion"
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"import time\n",
"def appending():\n",
" t = []\n",
" fin = open('words.txt')\n",
" for line in fin:\n",
" word = line.strip()\n",
" t.append(word)\n",
" return t\n",
"\n",
"start_time= time.time()\n",
"word_list= appending()\n",
"elapsed_time = time.time() - start_time\n",
"\n",
"print (elapsed_time)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def adding():\n",
" t = []\n",
" fin = open('words.txt')\n",
" for line in fin:\n",
" word = line.strip()\n",
" t=t+[word]\n",
" return t\n",
"\n",
"\n",
"start_time= time.time()\n",
"adding()\n",
"elapsed_time = time.time() - start_time\n",
"\n",
"print (elapsed_time)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 10\n",
"\n",
"Um zu überprüfen, ob ein Wort in einer Wortliste ist, können wir den Operator `in` verwenden, aber das wäre recht langsam, denn der Operator muss dazu die Liste linear durchlaufen.\n",
"\n",
"Wenn wir mit einer sortierten Liste arbeiten, können wir den Vorgang beschleunigen, indem wir *binäre Suche* (auch bekannt als *bisection search*) verwenden. Das entspricht dem Verfahren, welches wir verwenden, wenn wir ein Wort in einem Wörterbuch nachschlagen: wir beginnen in der Mitte und schauen, ob das gesuchte Wort vor dem Wort in der Mitte der Liste stehen müsste. Falls dem so ist, durchsuchen wir die erste Hälfte der Liste auf die gleiche Art, ansonsten durchsuchen wir die zweite Hälfte.\n",
"\n",
"In jedem Fall halbieren wir damit den Suchraum. Im Fall unserer Wortliste mit 10000 Wörtern benötigen wir höchstens 13 Schritte, um das gesuchte Wort zu finden oder festzustellen, dass die Liste das Wort nicht enthält. \n",
"\n",
"Schreiben Sie eine Funktion `binary_search` die eine sortierte Liste sowie ein Wort als Argumente erwartet und `True` zurückgibt, falls das Wort in der Liste enthalten ist, ansonsten `False`.\n",
"\n",
"Alternativ können Sie auch die [Dokumentation für das Modul `bisect`](https://docs.python.org/3.5/library/bisect) lesen und dieses verwenden. Eine Lösung finden Sie hier: http://thinkpython2.com/code/inlist.py\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-info\">Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Damit die binäre Suche funktioniert, muss die Liste sortiert sein. Das können Sie, wie wir es bereits getan haben, mit der Funktion `sort` erreichen. Mit `help(list.sort)` kriegen Sie mehr Informationen. \n",
" </div> \n",
"</details> \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",
"Wir verwenden Rekursion um die Suche durchzuführen\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",
"Wenn wir Rekursion verwenden müssen wir uns zuerst die beiden Abbruchbedingungen überlegen. Eine Abbruchbedingung für das finden des Wortes und eine Abbruchbedingung, für wenn dass Wort nicht in der Liste ist.\n",
" \n",
" </div> \n",
"</details> \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",
"Der erste Fall ist einfach: das Wort, das wir suchen, stimmt mit dem Wort überein, das wir uns gerade anschauen. Dies benötigt eine Vergleich zwischen dem gesuchten Wort und dem Wort das wir uns anschauen. Gibt dieser Vergleich 'TRUE' aus, können wir die Suche abbrechen und 'TRUE' zurückgeben. Schreiben Sie einen Platzhaltervergleich, der dies prüft. Dazu können Sie das gesuchte Wort mit einer zufälligen Zeichenkette vergleichen. Die Zeichenkette werden wir später ersetzen.\n",
"Die andere Abbruchbedingung ist das nicht finden des Wortes in der Liste. In der Rekursion halbieren wir die Wortliste in jedem Schritt bis die Liste irgendwann 0 Elemente lang ist. Erinnern Sie sich daran, wie Sie die Länge der Liste überprüfen? Wenn dieser Test 0 zurückgibt, müssen Sie 'FALSE' zurückgeben.\n",
" \n",
" </div> \n",
"</details> \n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Da wir in jedem Schritt die Liste halbieren und anschließend die Hälfte der Liste ignorieren, müssen wir entscheiden welche Hälfte der Liste wir ignorieren und mit welcher Hälfte wir weiterarbeiten. Dazu schauen wir uns das Trennelement in der Mitte der Liste an und entscheiden ob das gesuchte Wort größer oder kleiner ist als das Trennelement ist. Dazu berechnen wir den Index in der Mitte der Liste. \n",
" \n",
" </div> \n",
"</details> \n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Um den Index zu berechnen, ermitteln wir die Länge der Liste mit 'len()' und verwenden dann Ganzzahldivision um den Index herauszufinden.\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",
"Mit Hilfe von diesem Index können wir nun das Element ansteuern. Nun prüfen wir zuerst, ob das Wort an dieser Stelle gleich dem gesuchten Wort ist. Ersetzen Sie die Zeichenkette aus dem Platzhaltervergleich mit einem Zugriff auf die Liste an diesem Index. \n",
" \n",
" </div> \n",
"</details> \n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Gibt dieser Vergleich nicht 'TRUE' zurück, prüfen wir als nächstes, ob das Element an Indexstelle i größer ist, als das gesuchte Wort. Ist das Wort an dieser Stelle größer als das gesuchte Wort, wird in der vorderen Listenhälfte gesucht. Andernfalls wird in der hinteren Listenhälfte gesucht. Schreiben Sie den Vergleich und Platzhalter 'return'-Anweisungen. Testen Sie ihre Funktion und schauen Sie, ob alle 'return'-Anweisungen erreicht werden können. \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",
"An dieser Stelle fügen wir die Rekursion ein. Bisher wird nur geprüft ob das Wort genau in der Mitte steht oder ob es größer oder kleiner ist. Mithilfe der Rekursion rufen wir an der Stelle, an der wir entscheiden ob das Wort in der vorderen oder hinteren Listenhälfte steht die Funktion erneut auf, diesmal aber mit der geteilten Liste. \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",
"\n",
"In den 'return'-Anweisugen rufen wir die binäre Suche Funktion auf, dabei übergeben wir immer noch das gesuchte Wort, aber statt der ursprünglichen List übergeben wir nur die halbe Liste. Das erreichen wir, indem wir die ursprüngliche Liste zusamen mit einem Segementoperator übergeben, in dem wir entweder auf die Liste bis zum *i*-ten Element zugreifen, oder aber erst auf die Liste ab dem *i+1*-ten Element zugreifen.\n",
" \n",
" </div> \n",
"</details>\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def binary_search(t, w):\n",
" # Implementieren Sie hier die Funktion\n"
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"def binary_search(word_list, word):\n",
" '''Vorbedingung: Sortierte Liste'''\n",
" \n",
" if len(word_list) == 0:\n",
" return False \n",
"\n",
" i = len(word_list) // 2\n",
" \n",
" if word_list[i] == word:\n",
" return True\n",
"\n",
" if word_list[i] > word:\n",
" # search the first half\n",
" return binary_search(word_list[:i], word)\n",
" else:\n",
" # search the second half\n",
" return binary_search(word_list[i+1:], word)\n",
"\n",
"t=sorted([1,3,6,2,7,19,22])\n",
"binary_search(t,24)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 11\n",
"Zwei Wörter sind ein \"umgekehrtes Paar\" (*reverse pair*), wenn jedes Wort rückwärts gelesen das jeweils andere ergibt (wie bei \"LAGER\" und \"REGAL\"). Schreiben Sie ein Programm, welches alle umgekehrten Paare in unserer Wortliste findet. (Ignorieren Sie dabei wieder Groß- und Kleinschreibung oder verwenden sie die englischsprachige Liste) Eine Lösung finden Sie hier: http://thinkpython2.com/code/reverse_pair.py\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-info\">Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"Wenn Sie die deutsche Wortliste verwenden, werden Sie einige doppelte Paare finden, was daran liegt, dass in top10000.txt Groß- und Kleinschreibung unterschieden wird. \n",
" </div> \n",
"</details>\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",
"An dieser Stelle werden eigentlich 2 Funktionen gesucht. Eine Funktion, die ein umgekehrtes Paar findet, und eine Funktion, die die gesamte Liste durchläuft und für jedes Wort prüft ob es Teil eines umgekehrten Paares ist und diese Antwort zurückgibt. Teilen wir also die Aufgabe und konzentrieren uns zunächst einmal darauf ein umgekehrtes Paar zu finden, wenn ein beliebiges Wort eingegeben wird.\n",
" \n",
" </div> \n",
"</details> \n",
"\n",
"Teil 1\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Der Funktion müssen natürlich ein Wort und die komplette Wortliste übergeben werden, damit wir unser wort mit der Liste vergleichen 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",
"Der einfachste Weg rauszufinden ob das Wort, das wir übergeben, Teil eines umgekehrten Paares ist, ist es das umgekehrte Wort dieses Wortes zu bilden und zu schauen, ob es in der Liste vorhanden ist. In Seminar 8 haben Sie gelernt, wie man ein Wort schrittweise rückwärts durchläuft, dies können Sie nutzen um das umgekehrte Wort zu bilden.\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",
" Nun können wir die binäre Suche von vorher wiederverwenden um zu überprüfen, ob das so gebildete Wort in der Liste ist. Diese Funktion gibt 'TRUE' zurück, wenn dies der Fall ist. Hier könnten wir das Wortpaar ausgeben. In dem Beispielcode gibt diese Funktion allerdings 'TRUE' oder 'FALSE' an die nächste Funktion, die wir schreiben zurück, die dann wiederum die Ausgabe händelt.\n",
" </div> \n",
"</details> \n",
"\n",
"Teil 2 \n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Um alle Worte in der Liste zu finden, die Teil eines umgekehrten Paases sind, müssen wir mit einer Schleife die Liste Wort für Wort durchlaufen.\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",
"Wenn Sie die deutsche Liste verwenden, stellen Sie sicher, dass sie die Liste auf Kleinschreibung normalisieren, wie wir das bereits in anderen Aufgaben dieses Notebooks gemacht haben.\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",
"Rufen Sie innerhalb der Schleife die Funktion auf, die wir in Teil 1 geschrieben haben. Übergeben Sie jeweils das aktuelle Wort in der Schleife. Da die Funktion 'TRUE' oder 'FALSE' zurückgibt, können Sie sie verwenden um zu entscheiden ob das Wort als Teil eines umgekehrten Paares ausgegeben oder aber übersprungen werden soll. Wie können wir solche Entscheidungen treffen?\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",
"Innerhalb der if-Bedingung müssen wir das gesamte umgekehrte Paar ausgeben. Sie dürfen die Umkehrung des Wortes analog zu Teil 1 treffen. Verwenden Sie für die Ausgabe eine 'print'-Anweisung.\n",
" </div> \n",
"</details>"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier Ihr Programm\n"
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"def reverse_pair(word_list, word):\n",
" reverse = word[::-1]\n",
" return binary_search (word_list, reverse)\n",
"\n",
"\n",
"def reverse_list(word_list):\n",
" for word in word_list:\n",
" word= word.lower()\n",
" if reverse_pair(word_list, word): \n",
" print (word, word[::-1])\n",
"\n",
"reverse_list(word_list)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Aufgabe 12\n",
"Zwei Wörter \"greifen ineinander\" (*interlock*), wenn sich durch abwechselndes Hinzufügen eines Buchstabens aus beiden Wörtern ein neues Wort ergibt. Beispielsweise greifen \"Mai\" und \"im\" ineinander und bilden das Wort \"Miami\". \n",
"\n",
"\n",
"\n",
"1. Schreiben Sie ein Program, welches alle Wortpaare findet, die ineinandergreifen. \n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-info\">Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" Durchlaufen Sie nicht alle möglichen Wortpaare!\n",
" </div> \n",
"</details>\n",
"\n",
"2. Gibt es Wörter, die dreifach ineinandergreifen; das heißt, jeder dritte Buchstabe ergibt ein Wort, beginnend mit dem ersten, zweiten oder dritten Buchstaben? (*Leider ist unsere Wortliste mit 10000 Wörtern recht kurz ... als einziges einigermaßen sinnvolles Beispiel ergibt sich \"bekommt\", welches die \"Wörter\" \"Bot\", \"EM\", und \"km\" enthält.*)\n",
"\n",
"(Diese Aufgabe wurde durch ein Beispiel auf http://puzzlers.org/ inspiriert, eine Lösung finden Sie hier: http://thinkpython2.com/code/interlock.py)\n",
"\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"Ähnlich wie in der vorherigen Aufgabe benötigen wir wieder 2 Funktionen um die Frage zu beantworten. Eine Funktion, die prüft ob ein gegebenes Wort aus n ineinander greifenden Wörtern besteht und eine zweite Funktion, die die ganze Liste Wort für Wort ausliest. Auch in diesem Fall schreiben wir zuerst den Test dafür ob ein einzelnes Wort aus anderen -- in der Wortliste vorkommenden -- Worten zusammengesetzt ist.\n",
" </div> \n",
"</details>\n",
"\n",
"Teil 1 \n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"Im Kopf der Funktion müssen wir das Wort, die Liste, in der wir die Teilworte finden wollen, und die Schrittweite, also die Anzahl an Teilworten aus denen das gegebene Wort zusammengesetzt sein soll, übergeben. Schreiben Sie den Kopf der Funktion.\n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" Analog zur vorherigen Aufgabe müssen wir wieder aus dem Original Wort die Worte bilden, die wir in der Wortliste suchen wollen. Überlegen Sie sich wie Sie dabei vorgehen können.\n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"Um die Teilworte zu bilden nutzen wir den Segment-Operatoren. Wir können hier den ersten Buchstaben und die Schrittweite festlegen. Mit diesen Angaben werden dann nur die gewünschten Buchstaben genommen. Diese können Sie in einer Variable speichern. Versuchen Sie zunächst diesen Teil der Aufgabe zu lösen indem Sie die Teilworte jeweils ausgeben lassen und prüfen ob das gegebene Ergebnis mit dem erwarteten übereinstimmt. Testen Sie dies indem sie alle \"Teilworte\" (sinnvoll oder nicht) eines beliebigen Wortes sowohl für 2 als auch für 3 Teilworte erstellen. Behalten Sie diese Anweisungen, wir benötigen sie im nächsten Schritt.\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",
"Da wir die Aufgabe sowohl für 2 als auch für 3 Teilworte lösen wollen, ist es ratsam diese Erstellung so allgemein zu halten, dass sie mit jeder beliebigen Schrittweite funktionieren würde. Dies können wir mit einer Schleife erreichen. Schauen Sie sich die Segmentoperatoren an, die Sie geschrieben haben. Was fällt Ihnen auf? Wie könnte man das verallgemeinern?\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",
" Wir verwenden eine 'for'-Schleife, in der eine Platzhalter-Variable hochgezählt wird, bis wir die Schrittweite also die Anzahl an Worten erreichen. Damit wird die korrekte Anzahl an Worten gefunden. Das erste Wort beginnt am Index 0, das Zweite am Index 1 und so weiter. Damit dann diese Hilfsvariable verwendet werden um den Startpunkt für jedes der Worte zu setzten. Die Schrittweite ist für alle Worte gleich und ist als Variable vorhanden. Diese kann daher übergeben werden. \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",
" Für jedes Wort, das wir so erzeugen, müssen wir prüfen, ob das Wort in der übergebenen Liste enthalten ist. Wie haben wir dies bisher im Notebook erledigt?\n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">8. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Da alle erzeugten Wörter in der Wortliste vorhanden sein müssen und wir möglichst wenige Operationen durchführen wollen, testen wir in der in der Schleife direkt nach der Erstellung das Wort. Was passiert, wenn wir einen einfachen Wahrheitstest machen und das Ergebnis zurück geben? Was passiert, wenn das erste Wort zwar in der Wortliste ist, das zweite oder dritte aber nicht? Überlegen Sie, wie Sie sicherstellen können, dass nur dann 'TRUE' zurückgegeben wird, wenn alle Worte in der Liste sind.\n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">9. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Wir geben nur dann 'TRUE' zurück, wenn die Schleife verlassen wird. Daher prüfen wir in der Schleife ob wir 'FALSE' zurück geben müssen. Wenn des Ergebnis von 'binary_search' 'TRUE' ist, wird in der Schleife nichts weiter mit dem Wort gemacht und die Schleife startet -- falls nötig -- mit dem nächsten Wort. Sobald eines der Wörter nicht in der Liste ist, wird 'FALSE' zurück gegeben. Mit 'if not' können Sie eine Anweisung schreiben, die sagt: \"Wenn das Ergebnis von 'binary_search' nicht 'TRUE' ist, dann tue:\"\n",
" </div> \n",
"</details>\n",
"\n",
"Teil 2:\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">10. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
" In dieser Funktion wollen wir alle Worte finden, die aus einer bestimten Anzahl an ineinander greifenden Worten bestehen. Als solches muss diese Funktion die Liste und die gewünschte Anzahl an ineinander greifenden Worten übergeben bekommen. Schreiben Sie den Kopf der Funktion.\n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">11. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Innerhalb der Funktion müssen wir die Liste Wort für Wort durchlaufen und prüfen ob das Wort ineinander greifende Worte innerhalb der Liste enthält.\n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">12. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"Jedes Wort, das kürzer ist als die Anzahl an ineinander greifenden Worten, können wir komplett überspringen. Schreiben Sie das 'if'-Statement, das dies überprüft. Mit 'pass' können Sie den Rest eines Schleifendurchlaufs überspringen. \n",
" \n",
" \n",
" \n",
"wenn wir ein wort finden, wollen wir dieses ausgeben. Hier drucken wir dafür einen Header, der anzeigt, dass ein wort gefunden wurde und das wort ausgibt, bevor ähnlich wie in der prüffunktion die subworte aus dem originalwort erzuegt und einzel ausgedruckt werden. Dabei wird jedes wort in einer eigenen zeile ausgegeben, aber dafür kann die funktion ohne angepasst zu werden worte mit beliebig vielen unterworten finden. \n",
" </div> \n",
"</details>\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">13. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
" \n",
"Die erste Funktion gibt entweder 'TRUE' oder 'FALSE' zurück. Schreiben Sie ein 'if'-Statement analog zu dem in der Funktion zum finden von umgekehrten Paaren.\n",
" </div> \n",
"</details>\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-primary\">14. Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Innerhalb dieser 'if'-Bedingung wollen wir die ineinandergreifenden Worte ausgeben. Um die Funktion weiterhin für jede beliebige Menge an Teilworten nutzen zu können, können wir die Schleife aus der ersten Funktion wiederverwenden. Statt innerhalb der Schleife zu prüfen ob das Wort in der Liste ist, können wir das Wort mit einem 'print'-Statement ausgeben. Das bedeutet, dass jedes Wort und jedes Teilwort in einer eigenen Zeile gedruckt wird. Vergessen Sie nicht, dass vollständige Wort auszugeben. Es ist daher auch hilfreich eine Trennzeile auszudrucken in der gesagt wird, dass eine neues Wort folgt.\n",
" \n",
" </div> \n",
"</details>"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier das Programm"
]
},
{
"cell_type": "markdown",
"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,
"metadata": {},
"outputs": [],
"source": [
"def interwoven(word_list, word, n=3):\n",
" for i in range(n):\n",
" sub = word[i::n]\n",
" if not binary_search(word_list, sub):\n",
" return False \n",
" return True\n",
" \n",
"def find_interwoven(word_list, n):\n",
" for word in word_list:\n",
" if len(word)<n:\n",
" pass\n",
" if interwoven(word_list, word, n):\n",
" print (\"New word found:\")\n",
" print (word)\n",
" for i in range (n):\n",
" print(word[i::n]) \n",
" \n",
"find_interwoven(word_list, 2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). \n",
"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",
"metadata": {},
"source": [
"\n",
"\n",
"Herzlichen Glückwunsch! Sie haben das 10. Kapitel geschafft. Weiter geht es in [11: assoziative Felder](seminar11.ipynb)."
]
}
],
"metadata": {
"language_info": {
"name": "python",
"pygments_lexer": "ipython3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}