{
"cells": [
{
"cell_type": "markdown",
"id": "0196f382-d7f1-49b2-a6df-5770a42850e9",
"metadata": {},
"source": [
"# Kapitel 9: Listen\n",
"[Chapter 9: Lists](https://colab.research.google.com/github/AllenDowney/ThinkPython/blob/v3/chapters/chap09.ipynb)\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",
"In den Übungen am Ende des Kapitels werden wir eine Wortliste erstellen und diese nutzen, um nach besonderen Worten wie zum Beispiel Palindromen und Anagrammen zu suchen.\n",
"\n",
"### Ihre Lernziele:\n",
"\n",
"Beschreiben Sie in 2-3 Stichpunkten kurz was Sie im Seminar heute lernen wollen. Klicken Sie dazu doppelt auf diesen Text und bearbeiten Sie dann den Text:\n",
"\n",
"- \n",
"- \n",
"- \n",
"\n",
"## Exkurs: Was mir an Python gefällt\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",
"Die Python-Standardbibliothek bietet viele Module, die die Arbeit erleichtern. Beispielsweise ermöglicht das Modul [json](https://docs.python.org/3/library/json.html) das Lesen und Schreiben von [JSON](https://en.wikipedia.org/wiki/JSON)-Dateien:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8ef712a9-7454-4969-8de2-21185bd01706",
"metadata": {},
"outputs": [],
"source": [
"import json # Modul für JSON-Dateien\n",
"from collections import Counter # wir wollen wieder etwas zählen\n",
"\n",
"def count_words(counter, lines): # eine Funktion zum Wörterzählen\n",
" \"\"\"Zählt die Vorkommen der Wörter in lines.\n",
" counter: ein Zählobjekt (collections.Counter)\n",
" lines: eine Liste von Zeichenketten\n",
" \"\"\"\n",
" for line in lines: # alle Zeilen durchlaufen\n",
" for word in line.split(): # Zeichenketten in Wörter aufteilen\n",
" counter[word] += 1 # Vorkommen des Wortes zählen\n",
"\n",
"\n",
"nb = json.load(open(\"seminar11.ipynb\", \"r\")) # Jupyter-Notebooks sind JSON-Dateien!\n",
"counter = Counter() # zählt Vorkommen von Wörtern\n",
"\n",
"for c in nb[\"cells\"]: # über alle Zellen iterieren\n",
" if c[\"cell_type\"] == \"markdown\": # für jede Markdown-Zelle ...\n",
" count_words(counter, c[\"source\"]) # Wörter im Text zählen\n",
"\n",
"for word, freq in counter.most_common(10): # die zehn häufigsten Wörter finden ...\n",
" print(word, freq, sep='\\t') # und ausgeben"
]
},
{
"cell_type": "markdown",
"id": "9a0b03e4-0e53-40b4-8850-5fa03078f99a",
"metadata": {},
"source": [
"## Herunterladen des unterstützenden Codes\n",
"Die folgende Zelle lädt eine Datei herunter und führt einen Code aus, der speziell für dieses Notebook verwendet wird. Sie müssen diesen Code nicht verstehen, aber Sie sollten die Zelle vor allen weiteren Zellen in diesem Notebook ausführen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bde1c3f9",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"from os.path import basename, exists\n",
"\n",
"def download(url):\n",
" filename = basename(url)\n",
" if not exists(filename):\n",
" from urllib.request import urlretrieve\n",
"\n",
" local, _ = urlretrieve(url, filename)\n",
" print(\"Downloaded \" + str(local))\n",
" return filename\n",
"\n",
"download('https://github.com/AllenDowney/ThinkPython/raw/v3/thinkpython.py');\n",
"download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');\n",
"\n",
"import thinkpython"
]
},
{
"cell_type": "markdown",
"id": "ad8dd14f-e3be-48b1-bca8-a247caa655fa",
"metadata": {},
"source": [
"## Eine Liste ist eine Folge\n",
"\n",
"Wie eine Zeichenkette, ist eine **Liste** (Englisch: *list*) eine Folge (Englisch: *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** (Englisch: *items* oder *elements*).\n",
"\n",
"Es gibt mehrere Möglichkeiten, eine neue Liste zu erzeugen. Die einfachste ist es, Elemente in eckigen Klammern einzuschließen (`[` und `]`).\n",
"Hier ist zum Beispiel eine Liste mit zwei ganzen Zahlen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a16a119b",
"metadata": {},
"outputs": [],
"source": [
"zahlen = [42, 123]"
]
},
{
"cell_type": "markdown",
"id": "b5d6112c",
"metadata": {},
"source": [
"Und diese Liste enthält drei Zeichenketten:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ac7a4a0b",
"metadata": {},
"outputs": [],
"source": [
"käse = ['Cheddar', 'Edamer', 'Gouda']"
]
},
{
"cell_type": "markdown",
"id": "dda58c67",
"metadata": {},
"source": [
"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,
"id": "18fb0e21",
"metadata": {},
"outputs": [],
"source": [
"t = ['spam', 2.0, 5, [10, 20]]"
]
},
{
"cell_type": "markdown",
"id": "77f6db2e-4e7d-4bfb-b387-113cd769f136",
"metadata": {},
"source": [
"Eine Liste innerhalb einer anderen Liste ist **verschachtelt** (Englisch: *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,
"id": "0ff58916",
"metadata": {},
"outputs": [],
"source": [
"leer = []"
]
},
{
"cell_type": "markdown",
"id": "f95381bc",
"metadata": {},
"source": [
"Die `len`-Funktion gibt die Länge einer Liste zurück:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f3153f36",
"metadata": {},
"outputs": [],
"source": [
"len(käse)"
]
},
{
"cell_type": "markdown",
"id": "371403a3",
"metadata": {},
"source": [
"Die Länge einer leeren Liste ist `0`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "58727d35",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"len(leer)"
]
},
{
"cell_type": "markdown",
"id": "d3589a5d",
"metadata": {},
"source": [
"Die folgende Abbildung zeigt Zustandsdiagramme für `käse`, `zahlen` und `leer`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "25582cad",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"from diagram import make_list, Binding, Value\n",
"\n",
"list1 = make_list(käse, dy=-0.3, offsetx=0.17)\n",
"binding1 = Binding(Value('käse'), list1)\n",
"\n",
"list2 = make_list(zahlen, dy=-0.3, offsetx=0.17)\n",
"binding2 = Binding(Value('zahlen'), list2)\n",
"\n",
"list3 = make_list(leer, dy=-0.3, offsetx=0.1)\n",
"binding3 = Binding(Value('leer'), list3)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "925c7d67",
"metadata": {
"tags": [
"remove-input"
]
},
"outputs": [],
"source": [
"from diagram import diagram, adjust, Bbox\n",
"\n",
"width, height, x, y = [3.66, 1.58, 0.45, 1.2]\n",
"ax = diagram(width, height)\n",
"bbox1 = binding1.draw(ax, x, y)\n",
"bbox2 = binding2.draw(ax, x+2.25, y)\n",
"bbox3 = binding3.draw(ax, x+2.25, y-1.0)\n",
"\n",
"bbox = Bbox.union([bbox1, bbox2, bbox3])\n",
"#adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "503f25d8",
"metadata": {},
"source": [
"Listen werden durch Kästen dargestellt, die innen die nummerierten Elemente der Liste enthalten und an denen außen das Wort \"list“ steht."
]
},
{
"cell_type": "markdown",
"id": "8fe05ed4-8c46-4b00-a7b8-a3bc10bb83d9",
"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,
"id": "9deb85a3",
"metadata": {},
"outputs": [],
"source": [
"käse[0]"
]
},
{
"cell_type": "markdown",
"id": "2813f922-4791-4e17-ad42-f376c8879b91",
"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,
"id": "98ec5d9c",
"metadata": {},
"outputs": [],
"source": [
"zahlen[1] = 17\n",
"zahlen"
]
},
{
"cell_type": "markdown",
"id": "5097a517",
"metadata": {},
"source": [
"Das zweite Element von `numbers`, welches `123` war, ist jetzt `17`.\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,
"id": "000aed26",
"metadata": {},
"outputs": [],
"source": [
"'Edamer' in käse"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bcb8929c",
"metadata": {},
"outputs": [],
"source": [
"'Wensleydale' in käse"
]
},
{
"cell_type": "markdown",
"id": "89d01ebf",
"metadata": {},
"source": [
"Obwohl eine Liste eine andere Liste enthalten kann, zählt die verschachtelte Liste trotzdem als einzelnes Element -- die folgende Liste enthält also nur vier Elemente:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5ad51a26",
"metadata": {},
"outputs": [],
"source": [
"t = ['spam', 2.0, 5, [10, 20]]\n",
"len(t)"
]
},
{
"cell_type": "markdown",
"id": "4e0ea41d",
"metadata": {},
"source": [
"Und `10` wird nicht als Element von `t` betrachtet, da es ein Element der verschachtelten Liste und keines von `t` ist:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "156dbc10",
"metadata": {},
"outputs": [],
"source": [
"10 in t"
]
},
{
"cell_type": "markdown",
"id": "1ee7a4d9",
"metadata": {},
"source": [
"## Listen-Segmente\n",
"\n",
"Der `slice`-Operator funktioniert mit Listen genauso wie mit Zeichenketten.\n",
"Im folgenden Beispiel werden das zweite und dritte Element aus einer Liste mit vier Buchstaben ausgewählt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "70b16371",
"metadata": {},
"outputs": [],
"source": [
"buchstaben = ['a', 'b', 'c', 'd']\n",
"buchstaben[1:3]"
]
},
{
"cell_type": "markdown",
"id": "bc59d952",
"metadata": {},
"source": [
"Wenn wir den ersten Index weglassen, dann beginnt das Segment mit dem Anfang der Liste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e67bab33",
"metadata": {},
"outputs": [],
"source": [
"buchstaben[:2]"
]
},
{
"cell_type": "markdown",
"id": "1aaaae86",
"metadata": {},
"source": [
"Wenn wir den zweiten Index weglassen, dann geht das Segment bis zum Ende der Liste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a310f506",
"metadata": {},
"outputs": [],
"source": [
"buchstaben[2:]"
]
},
{
"cell_type": "markdown",
"id": "67ad02e8",
"metadata": {},
"source": [
"Wenn wir also beide weglassen, dann ist das Segment eine Kopie der gesamten Liste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1385a75e",
"metadata": {},
"outputs": [],
"source": [
"buchstaben[:]"
]
},
{
"cell_type": "markdown",
"id": "9232c1ef",
"metadata": {},
"source": [
"Ein weiterer Weg, eine Liste zu kopieren, ist die `list`-Funktion zu verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a0ca0135",
"metadata": {},
"outputs": [],
"source": [
"list(buchstaben)"
]
},
{
"cell_type": "markdown",
"id": "50e4b182",
"metadata": {},
"source": [
"Weil `list` schon der Name einer eingebauten Funktion ist, sollten Sie es vermeiden, diesen als Variablennamen zu verwenden.\n"
]
},
{
"cell_type": "markdown",
"id": "3cd2df79-fea5-4691-8524-dc3586fcc84c",
"metadata": {},
"source": [
"## Listenoperatoren\n",
"\n",
"Der `+`-Operator verknüpft Listen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "66804de0",
"metadata": {},
"outputs": [],
"source": [
"t1 = [1, 2]\n",
"t2 = [3, 4]\n",
"t1 + t2"
]
},
{
"cell_type": "markdown",
"id": "f2dbc75e-c3ee-4cd5-98d9-cd9bbd6900cc",
"metadata": {},
"source": [
"Der `*`-Operator wiederholt eine Liste so oft wie angegeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "96620f93",
"metadata": {},
"outputs": [],
"source": [
"['spam'] * 4"
]
},
{
"cell_type": "markdown",
"id": "5b33bc51",
"metadata": {},
"source": [
"Darüber hinaus sind keine der anderen mathematischen Operatoren mit Listen verwendbar, aber die eingebaute Funktion `sum` addiert die Elemente der Liste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0808ed08",
"metadata": {},
"outputs": [],
"source": [
"sum(t1)"
]
},
{
"cell_type": "markdown",
"id": "f216a14d",
"metadata": {},
"source": [
"Und `min` und `max` finden jeweils das kleinste und das größte Element:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7ed7e53d",
"metadata": {},
"outputs": [],
"source": [
"min(t1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "dda02e4e",
"metadata": {},
"outputs": [],
"source": [
"max(t2)"
]
},
{
"cell_type": "markdown",
"id": "533a2009",
"metadata": {},
"source": [
"## Methoden für Listen\n",
"\n",
"Python stellt Methoden zur Verfügung, die auf Listen angewendet werden können. `append` fügt zum Beispiel ein neues Element am Ende einer Liste hinzu:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bcf04ef9",
"metadata": {},
"outputs": [],
"source": [
"buchstaben.append('e')\n",
"buchstaben"
]
},
{
"cell_type": "markdown",
"id": "ccc57f77",
"metadata": {},
"source": [
"`extend` nimmt eine Liste als Argument auf und hängt alle Elemente an:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "be55916d",
"metadata": {},
"outputs": [],
"source": [
"buchstaben.extend(['f', 'g'])\n",
"buchstaben"
]
},
{
"cell_type": "markdown",
"id": "0f39d9f6",
"metadata": {},
"source": [
"Es gibt zwei Methoden, um Elemente einer Liste zu entfernen.\n",
"Wenn wir den Index des gewünschten Elements kennen, können wir `pop` verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b22da905",
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"t.pop(1)"
]
},
{
"cell_type": "markdown",
"id": "6729415a",
"metadata": {},
"source": [
"Der Rückgabewert ist das Element, das entfernt wurde.\n",
"Nun können wir überprüfen, ob die Liste angepasst wurde:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "01bdff91",
"metadata": {},
"outputs": [],
"source": [
"t"
]
},
{
"cell_type": "markdown",
"id": "1e97ee7d",
"metadata": {},
"source": [
"Wenn wir das Element kennen, dass wir entfernen wollen (aber nicht dessen Index), können wir `remove` verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "babe366e",
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"t.remove('b')"
]
},
{
"cell_type": "markdown",
"id": "60e710fe",
"metadata": {},
"source": [
"Der Rückgabewert von `remove` ist `None`.\n",
"Aber wir können auch hier durch eine Überprüfung bestätigen, dass die Liste verändert wurde:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f80f5b1d",
"metadata": {},
"outputs": [],
"source": [
"t"
]
},
{
"cell_type": "markdown",
"id": "2a9448a8",
"metadata": {},
"source": [
"Wenn das Element, das wir versuchen zu entfernen kein Teil der Liste ist, führt das zu einem `ValueError`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "861f8e7e",
"metadata": {
"tags": [
"raises-exception"
]
},
"outputs": [],
"source": [
"%%expect ValueError\n",
"\n",
"t.remove('d')"
]
},
{
"cell_type": "markdown",
"id": "7393b28c-4ac4-4426-84f7-76e278be9684",
"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,
"id": "1b50bc13",
"metadata": {},
"outputs": [],
"source": [
"s = 'spam'\n",
"t = list(s)\n",
"t"
]
},
{
"cell_type": "markdown",
"id": "0291ef69",
"metadata": {},
"source": [
"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,
"id": "c28e5127",
"metadata": {},
"outputs": [],
"source": [
"s = 'Sehnsucht nach den Fjorden'\n",
"t = s.split()\n",
"t"
]
},
{
"cell_type": "markdown",
"id": "90a87af6-e398-4053-9849-237b7beae108",
"metadata": {},
"source": [
"Ein optionales Argument, genannt **Trennzeichen** (Englisch: *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,
"id": "ec6ea206",
"metadata": {},
"outputs": [],
"source": [
"s = 'Ex-Papagei'\n",
"t = s.split('-')\n",
"t"
]
},
{
"cell_type": "markdown",
"id": "5e553ac1-ac4c-4748-af60-5fe739f168f7",
"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,
"id": "75c74d3c",
"metadata": {},
"outputs": [],
"source": [
"trennzeichen = ' '\n",
"t = ['Sehnsucht', 'nach', 'den', 'Fjorden']\n",
"s = trennzeichen.join(t)\n",
"s"
]
},
{
"cell_type": "markdown",
"id": "5d2cc997-2083-4042-a298-e314604e8a20",
"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",
"id": "d4efc177-b393-457d-a09d-e17833b2e61e",
"metadata": {},
"source": [
"## Eine Liste durchlaufen\n",
"\n",
"Wir können eine `for`-Anweisung verwenden, um in einer Schleife durch die Elemente einer Liste zu laufen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a5df1e10",
"metadata": {},
"outputs": [],
"source": [
"for käse in käse:\n",
" print(käse)"
]
},
{
"cell_type": "markdown",
"id": "c0e53a09",
"metadata": {},
"source": [
"Wir können `for` zum Beispiel verwenden, nachdem wir mit `split` eine Liste mit Wörtern erstellt haben, um diese zu durchlaufen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "76b2c2e3",
"metadata": {},
"outputs": [],
"source": [
"s = 'Sehnsucht nach den Fjorden'\n",
"\n",
"for word in s.split():\n",
" print(word)"
]
},
{
"cell_type": "markdown",
"id": "0857b55b",
"metadata": {},
"source": [
"Eine `for`-Schleife über einer leeren Liste führt die eingerückten Anweisungen niemals aus:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7e844887",
"metadata": {},
"outputs": [],
"source": [
"for x in []:\n",
" print('Das passiert nie.')"
]
},
{
"cell_type": "markdown",
"id": "6e5f55c9",
"metadata": {},
"source": [
"## Listen sortieren\n",
"\n",
"Python stellt eine eingebaute Funktion namens `sorted` zur Verfügung, die die Elemente einer Liste sortiert:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9db54d53",
"metadata": {},
"outputs": [],
"source": [
"durcheinander = ['c', 'a', 'b']\n",
"sorted(durcheinander)"
]
},
{
"cell_type": "markdown",
"id": "44e028cf",
"metadata": {},
"source": [
"Die ursprüngliche Liste bleibt unverändert:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "33d11287",
"metadata": {},
"outputs": [],
"source": [
"durcheinander"
]
},
{
"cell_type": "markdown",
"id": "530146af",
"metadata": {},
"source": [
"`sorted` funktioniert mit jeder Art von Abfolge, nicht nur Listen. Also können wir so auch die Buchstaben einer Zeichenkette sortieren:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "38c7cb0c",
"metadata": {},
"outputs": [],
"source": [
"sorted('buchstaben')"
]
},
{
"cell_type": "markdown",
"id": "f90bd9ea",
"metadata": {},
"source": [
"Das Ergebnis ist eine Liste.\n",
"Um diese in eine Zeichenkette umzuwandeln können wir `join` verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2adb2fc3",
"metadata": {},
"outputs": [],
"source": [
"''.join(sorted('buchstaben'))"
]
},
{
"cell_type": "markdown",
"id": "a57084e2",
"metadata": {},
"source": [
"Mit einer leeren Zeichenkette als Trennzeichen werden die Elemente der Liste ohne etwas dazwischen zusammengefügt."
]
},
{
"cell_type": "markdown",
"id": "7ef44d57-0c4d-4501-be28-850a17de4145",
"metadata": {},
"source": [
"## Objekte und Werte\n",
"\n",
"Wenn wir diese beiden Zuweisungen ausführen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "aa547282",
"metadata": {},
"outputs": [],
"source": [
"a = 'banana'\n",
"b = 'banana'"
]
},
{
"cell_type": "markdown",
"id": "33d020aa",
"metadata": {},
"source": [
"wissen wir, dass sowohl `a` als auch `b` auf eine Zeichenkette verweisen, aber wir wissen nicht, ob sie auf *dieselbe* Zeichenkette verweisen. Es gibt zwei mögliche Zustände:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "95a2aded",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"from diagram import Frame, Stack\n",
"\n",
"s = 'banana'\n",
"bindings = [Binding(Value(name), Value(repr(s))) for name in 'ab']\n",
"frame1 = Frame(bindings, dy=-0.25)\n",
"\n",
"binding1 = Binding(Value('a'), Value(repr(s)), dy=-0.11)\n",
"binding2 = Binding(Value('b'), draw_value=False, dy=0.11)\n",
"frame2 = Frame([binding1, binding2], dy=-0.25)\n",
"\n",
"stack = Stack([frame1, frame2], dx=1.7, dy=0)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3d75a28c",
"metadata": {
"tags": [
"remove-input"
]
},
"outputs": [],
"source": [
"width, height, x, y = [2.85, 0.76, 0.17, 0.51]\n",
"ax = diagram(width, height)\n",
"bbox = stack.draw(ax, x, y)\n",
"# adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "2f0b0431",
"metadata": {},
"source": [
"Im ersten Fall verweisen `a` und `b` auf zwei unterschiedliche **Objekte** (Englisch: *object*), die den gleichen Wert haben. Im zweiten Fall verweisen sie auf dasselbe Objekt.\n",
"\n",
"Um zu prüfen, ob zwei Variablen auf dasselbe Objekt verweisen, können wir den `is`-Operator verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a37e37bf",
"metadata": {},
"outputs": [],
"source": [
"a = 'banana'\n",
"b = 'banana'\n",
"a is b"
]
},
{
"cell_type": "markdown",
"id": "82c68f74-bb6b-4e3f-b8d4-7908cce4b74d",
"metadata": {},
"source": [
"In diesem Beispiel erzeugt Python nur ein Zeichenketten-Objekt und sowohl `a` als auch `b` verweisen darauf. Wenn wir jedoch zwei Listen erzeugen, erhalten wir zwei Objekte:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d6af7316",
"metadata": {},
"outputs": [],
"source": [
"a = [1, 2, 3]\n",
"b = [1, 2, 3]\n",
"a is b"
]
},
{
"cell_type": "markdown",
"id": "a8d4c3d4",
"metadata": {},
"source": [
"Das Zustandsdiagramm sieht in diesem Fall so aus:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "dea08b82",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"t = [1, 2, 3]\n",
"binding1 = Binding(Value('a'), Value(repr(t)))\n",
"binding2 = Binding(Value('b'), Value(repr(t)))\n",
"frame = Frame([binding1, binding2], dy=-0.25)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7e66ee69",
"metadata": {
"tags": [
"remove-input"
]
},
"outputs": [],
"source": [
"width, height, x, y = [1.16, 0.76, 0.21, 0.51]\n",
"ax = diagram(width, height)\n",
"bbox = frame.draw(ax, x, y)\n",
"# adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "cc115a9f",
"metadata": {},
"source": [
"In diesem Fall würden wir sagen, dass die beiden Listen **äquivalent** (Englisch: *equivalent*) sind, denn sie enthalten die gleichen Elemente, aber sie sind nicht **identisch** (Englisch: *identical*), 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."
]
},
{
"cell_type": "markdown",
"id": "e2f153e6-7cb6-4d7d-8387-dad350ccb2af",
"metadata": {},
"source": [
"## Aliasing\n",
"\n",
"Wenn `a` auf ein Objekt verweist und wir die Zuweisung `b = a` ausführen, dann verweisen beide Variablen auf dasselbe Objekt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d6a7eb5b",
"metadata": {},
"outputs": [],
"source": [
"a = [1, 2, 3]\n",
"b = a\n",
"b is a"
]
},
{
"cell_type": "markdown",
"id": "f6ab3262",
"metadata": {},
"source": [
"Das Zustandsdiagramm sieht dann folgendermaßen aus:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "dd406791",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"t = [1, 2, 3]\n",
"binding1 = Binding(Value('a'), Value(repr(t)), dy=-0.11)\n",
"binding2 = Binding(Value('b'), draw_value=False, dy=0.11)\n",
"frame = Frame([binding1, binding2], dy=-0.25)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "552e1e1e",
"metadata": {
"tags": [
"remove-input"
]
},
"outputs": [],
"source": [
"width, height, x, y = [1.11, 0.81, 0.17, 0.56]\n",
"ax = diagram(width, height)\n",
"bbox = frame.draw(ax, x, y)\n",
"# adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "c676fde9",
"metadata": {},
"source": [
"Die Verbindung einer Variable mit einem Objekt wird **Referenz** (Englisch: *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 ein **Alias** besitzt. \n",
"\n",
"Falls das Objekt mit Alias veränderbar ist, dann betreffen Veränderungen, die an einem Alias vorgenommen werden auch das andere.\n",
"\n",
"Verändern wir in diesem Beispiel also das Objekt, auf das sich `b` bezieht, verändern wir auch das Objekt, auf das sich `a` bezieht:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6e3c1b24",
"metadata": {},
"outputs": [],
"source": [
"b[0] = 5\n",
"a"
]
},
{
"cell_type": "markdown",
"id": "e3ef0537",
"metadata": {},
"source": [
"Also würden wir hier sagen, dass `a` diese Veränderung \"sieht\".\n",
"Obwohl dieses Verhalten nützlich sein kann, ist es auch fehleranfällig. Im Allgemeinen ist es sicherer, **Aliasing** (Englisch:**) 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:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "dad8a246",
"metadata": {},
"outputs": [],
"source": [
"a = 'banana'\n",
"b = 'banana'"
]
},
{
"cell_type": "markdown",
"id": "952bbf60",
"metadata": {},
"source": [
"macht es so gut wie nie einen Unterschied, ob `a` und `b` auf die gleiche Zeichenkette verweisen oder nicht."
]
},
{
"cell_type": "markdown",
"id": "35045bef",
"metadata": {},
"source": [
"## Listenargumente\n",
"\n",
"Wenn Sie eine Liste an eine Funktion übergeben, erhält die Funktion eine Referenz zur Liste. Wenn die Funktion die Liste abändert, sieht der Aufrufer die Änderung. Zum Beispiel verwendet `pop_first` die Listenmethode `pop`, um das erste Element aus einer Liste zu entfernen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "613b1845",
"metadata": {},
"outputs": [],
"source": [
"def pop_first(lst):\n",
" return lst.pop(0)"
]
},
{
"cell_type": "markdown",
"id": "4953b0f9",
"metadata": {},
"source": [
"Wir können das so verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3aff3598",
"metadata": {},
"outputs": [],
"source": [
"buchstaben = ['a', 'b', 'c']\n",
"pop_first(buchstaben)"
]
},
{
"cell_type": "markdown",
"id": "ef5d3c1e",
"metadata": {},
"source": [
"Der Rückgabewert ist das erste Element, das aus der Liste entfernt wurde -- wie wir durch Anzeigen der veränderten Liste sehen können:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c10e4dcc",
"metadata": {},
"outputs": [],
"source": [
"buchstaben"
]
},
{
"cell_type": "markdown",
"id": "e5288e08",
"metadata": {},
"source": [
"In diesem Beispiel sind der Parameter `lst` und die variable `buchstaben` Aliase desselben Objekts, das Zustandsdiagramm sieht also so aus:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a13e72c7",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"lst = make_list('abc', dy=-0.3, offsetx=0.1)\n",
"binding1 = Binding(Value('buchstaben'), draw_value=False)\n",
"frame1 = Frame([binding1], name='__main__', loc='left')\n",
"\n",
"binding2 = Binding(Value('lst'), draw_value=False, dx=0.61, dy=0.35)\n",
"frame2 = Frame([binding2], name='pop_first', loc='left', offsetx=0.08)\n",
"\n",
"stack = Stack([frame1, frame2], dx=-0.3, dy=-0.5)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1a06dae9",
"metadata": {
"tags": [
"remove-input"
]
},
"outputs": [],
"source": [
"width, height, x, y = [2.04, 1.24, 1.06, 0.85]\n",
"ax = diagram(width, height)\n",
"bbox1 = stack.draw(ax, x, y)\n",
"bbox2 = lst.draw(ax, x+0.5, y)\n",
"bbox = Bbox.union([bbox1, bbox2])\n",
"#adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "c1a093d2",
"metadata": {},
"source": [
"Eine Referenz zu einem Objekt als Argument an eine Funktion zu übergeben, stellt eine Form des Aliasing dar.\n",
"Wenn die Funktion das Objekt verändert, bleiben diese Änderungen auch bestehen, nachdem die Funktion durchgelaufen ist:"
]
},
{
"cell_type": "markdown",
"id": "88c07ec9",
"metadata": {
"tags": [
"section_word_list"
]
},
"source": [
"## Erstellen einer Wortliste\n",
"\n",
"Im vorherigen Kapitel haben wir die Datei `words.txt` gelesen und nach Wörtern mit bestimmten Eigenschaften, zum Beispiel die Verwendung des Buchstaben `e`, durchsucht.\n",
"Allerdings haben wir hierfür die gesamte Datei sehr oft gelesen, was nicht effizient ist.\n",
"Es ist besser, die Datei nur einmal zu lesen und die Wörter einer Liste hinzuzufügen.\n",
"Die folgende Schleife zeigt wie das geht:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6550f0b8",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e5a94833",
"metadata": {},
"outputs": [],
"source": [
"word_list = []\n",
"\n",
"for line in open('words.txt'):\n",
" word = line.strip()\n",
" word_list.append(word)\n",
" \n",
"len(word_list)"
]
},
{
"cell_type": "markdown",
"id": "44450ffa",
"metadata": {},
"source": [
"Vor der Schleife wird `word_list` mit einer leeren Liste initialisiert.\n",
"Bei jedem Durchlauf der Schleife fügt die `append`-Methode ein Wort am das Ende der Liste hinzu.\n",
"Wenn die Schleife endet, enthält die Liste mehr als 113.000 Wörter.\n",
"\n",
"Eine andere Art, das zu tun, ist `read` zu verwenden, um die gesamte Datei in eine Zeichenkette einzulesen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "32e28204",
"metadata": {},
"outputs": [],
"source": [
"string = open('words.txt').read()\n",
"len(string)"
]
},
{
"cell_type": "markdown",
"id": "65718c7f",
"metadata": {},
"source": [
"Das Ergebnis ist eine einzelne Zeichenkette mit mehr als einer Millionen Zeichen.\n",
"Wir können die `split`-Methode verwenden, um diese in eine Liste aus Wörtern aufzuteilen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4e35f7ce",
"metadata": {},
"outputs": [],
"source": [
"word_list = string.split()\n",
"len(word_list)"
]
},
{
"cell_type": "markdown",
"id": "1b5b25a3",
"metadata": {},
"source": [
"Jetzt können wir, um zu überprüfen, ob eine Zeichenkette in der Liste auftaucht, den `in`-Operator verwenden.\n",
"Das englische Wort `'demiotic'` befindet sich zum Beispiel in der Liste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a778a62a",
"metadata": {},
"outputs": [],
"source": [
"'demotic' in word_list"
]
},
{
"cell_type": "markdown",
"id": "9df6674d",
"metadata": {},
"source": [
"`'contrafibularities'` hingegen ist nicht auf der Liste zu finden. (*Anmerkung: 'contrafibularieties' ist ein erfundenes Wort aus der britischen Serie \"Blackadder\"*)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "63341c0e",
"metadata": {},
"outputs": [],
"source": [
"'contrafibularities' in word_list"
]
},
{
"cell_type": "markdown",
"id": "243c25b6",
"metadata": {},
"source": [
"Und ich muss sagen, dass ich darüber 'anaspeptic' bin. (*Anmerkung: 'anaspeptic' ist ebenfalls ein erfundenes Wort aus \"Blackadder\"*)"
]
},
{
"cell_type": "markdown",
"id": "ce9ffd79",
"metadata": {},
"source": [
"## Debugging\n",
"\n",
"### Denken Sie daran, dass die meisten Methoden für Listen das Argument verändern und `None` zurückgeben.\n",
"Das ist das Gegenteil von Methoden für Zeichenketten, die eine neue Zeichenkette zurückgeben und das Original nicht verändern.\n",
"\n",
"Wenn Sie daran gewöhnt sind, auf diese Weise Code für Zeichenketten zu schreiben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "88872f14",
"metadata": {},
"outputs": [],
"source": [
"word = 'Gefieder!'\n",
"word = word.strip('!')\n",
"word"
]
},
{
"cell_type": "markdown",
"id": "d2117582",
"metadata": {},
"source": [
"ist es verlockend, solchen Code für Listen zu schreiben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e28e7135",
"metadata": {},
"outputs": [],
"source": [
"t = [1, 2, 3]\n",
"t = t.remove(3) # FALSCH!"
]
},
{
"cell_type": "markdown",
"id": "991c439d",
"metadata": {},
"source": [
"`remove` verändert die Liste und gibt `None` zurück, die nächste Operation, die Sie versuchen mit `t` auszuführen wird also wahrscheinlich fehlschlagen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "97cf0c61",
"metadata": {
"tags": [
"raises-exception"
]
},
"outputs": [],
"source": [
"%%expect AttributeError\n",
"\n",
"t.remove(2)"
]
},
{
"cell_type": "markdown",
"id": "c500e2d8",
"metadata": {},
"source": [
"Diese Fehlermeldung benötigt einiges an Erklärung.\n",
"Ein **Attribut** eines Objekts ist eine Variable oder eine Methode, die damit in Verbindung steht.\n",
"In diesem Fall ist der Wert von `t` `None`, was ein `NoneType`-Objekt ist. Dieses hat kein Attribut namens `remove`, also ist das Ergebnis ein `AttributeError`.\n",
"\n",
"Wenn Sie eine solche Fehlermeldung sehen sollten Sie rückwärts durch das Programm gehen, um festzustellen, ob Sie vielleicht eine Listen-Methode falsch aufgerufen haben."
]
},
{
"cell_type": "markdown",
"id": "7a113d88-a078-4b89-b887-ccaed7981eef",
"metadata": {
"jp-MarkdownHeadingCollapsed": true
},
"source": [
"## Glossar\n",
"\n",
"Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 9 gelernt haben:\n",
"\n",
"- Liste: eine Folge von Werten\n",
"- Element:\n",
"- verschachtelte Liste: \n",
"- Objekt:\n",
"- äquivalent:\n",
"- identisch:\n",
"- Referenz:\n",
"- Aliasing:\n",
"- Trennzeichen:\n",
"- Attribut: einer der benannten Werte, die mit einem Objekt verknüpft sind\n",
"\n",
"Ergänzen Sie die Liste in eigenen Worten. Das ist eine gute Erinnerungs- und Übungsmöglichkeit.\n"
]
},
{
"cell_type": "markdown",
"id": "e67864e5",
"metadata": {},
"source": [
"## Übung\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a4e34564",
"metadata": {
"tags": [
"remove-print"
]
},
"outputs": [],
"source": [
"# Diese Zelle weist Jupyter an, detallierte Debugging-Informationen auszugeben, wenn ein Laufzeitfehler\n",
"# passiert. Lassen Sie sie daher laufen, bevor Sie beginnen an den Aufgaben zu arbeiten.\n",
"\n",
"%xmode Verbose"
]
},
{
"cell_type": "markdown",
"id": "ae9c42da",
"metadata": {},
"source": [
"### Fragen Sie einen virtuellen Assistenten\n",
"\n",
"In diesem Kapitel habe ich die Wörter \"contrafibularities\" und \"anaspeptic\" verwendet, die gar keine echten englischen Wörter sind.\n",
"Sie wurden in der britischen TV-Serie *Blackadder*, in Staffel 3, Folge 2, \"Leidende Literaten\" (Englisch: *\"Ink and Incapability\"*) verwendet.\n",
"\n",
"Als ich allerdings ChatGPT 3.5 (Version vom 03. August 2023) fragte, wo diese Wörter herkommen, behauptete es zunächst, sie kämen von Monty Python, und später, sie seien aus dem Stück *Rosencrantz und Guildenstern sind tot* von Tom Stoppard.\n",
"\n",
"Wenn Sie jetzt diese Frage stellen, erhalten Sie vielleicht ein anderes Ergebnis.\n",
"Aber dieses Beispiel ist eine Erinnerung daran, dass virtuelle Assistenten nicht immer zuverlässig sind und Sie daher immer überprüfen sollten, ob die Ergebnisse korrekt sind.\n",
"Mit zunehmender Erfahrung werden Sie ein Gespür dafür entwickeln, welche Fragen virtuelle Assistenten zuverlässig beantworten können.\n",
"In diesem Beispiel kann eine einfache Web-Suche die Quelle der Wörter schnell identifizieren.\n",
"\n",
"Wenn Sie bei einer der Übungen zu diesem Kapitel hängenbleiben, denken Sie darüber nach, einen virtuellen Assistenten um Hilfe zu fragen.\n",
"Wenn Sie ein Ergebnis erhalten, das Funktionen verwendet, die wir noch nicht gelernt haben, können Sie dem VA eine \"Rolle\" zuweisen.\n",
"\n",
"Probieren Sie zum Beispiel \"Rolle: Lehrer für grundlegende Python-Programmierung\" einzugeben, bevor Sie eine Frage stellen.\n",
"Wenn Sie immer noch Funktionen sehen, die Sie noch nicht kennen, können sie im Anschluss fragen: \"Kannst du das umschreiben und diesmal nur grundlegende Python-Funktionen verwenden?\"."
]
},
{
"cell_type": "markdown",
"id": "7a1bb62b-cc40-4497-8378-a1593360f119",
"metadata": {},
"source": [
"### Aufgabe 1\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 *ATLAS* und *SALAT* 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,
"id": "b0994f48-be76-4b14-9e43-c67d187101ff",
"metadata": {},
"outputs": [],
"source": [
"def is_anagram(v, w):\n",
" pass\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"id": "a86e7403",
"metadata": {
"tags": [
"remove-cell"
]
},
"source": [
"Sie können `doctest` verwenden, um Ihre Funktion zu testen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ce7a96ec",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"from doctest import run_docstring_examples\n",
"\n",
"def run_doctests(func):\n",
" run_docstring_examples(func, globals(), name=func.__name__)\n",
"\n",
"run_doctests(is_anagram)"
]
},
{
"cell_type": "markdown",
"id": "8501f3ba",
"metadata": {},
"source": [
"Finden Sie unter Verwendung Ihrer Funktion und der Wortliste alle Anagramme von `takes`."
]
},
{
"cell_type": "markdown",
"id": "98b475b9-c973-40b4-b994-a5c8d5486422",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f83b1b10-8d7e-43c4-ab57-52e1f2a5871a",
"metadata": {},
"outputs": [],
"source": [
"def is_anagram(word1, word2):\n",
" \"\"\"Checks whether two words are anagrams\n",
"\n",
" word1: string or list\n",
" word2: string or list\n",
"\n",
" returns: boolean\n",
" \"\"\"\n",
"\n",
" return sorted(word1) == sorted(word2)\n"
]
},
{
"cell_type": "markdown",
"id": "7f279f2f",
"metadata": {},
"source": [
"### Aufgabe 2\n",
"\n",
"Python stellt eine eingebaute Funktion namens `reversed` zur Verfügung, die als Argument eine Abfolge von Elementen -- wie eine Liste oder Zeichenkette -- aufnimmt und ein `reversed`-Objekt zurückgibt, das die Elemente in umgekehrter Reihenfolge enthält:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "aafa5db5",
"metadata": {},
"outputs": [],
"source": [
"reversed('parrot')"
]
},
{
"cell_type": "markdown",
"id": "0f95c76f",
"metadata": {},
"source": [
"Wenn Sie diese umgekehrten Elemente in einer Liste speichern wollen, können Sie die `list`-Funktion verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "06cbb42a",
"metadata": {},
"outputs": [],
"source": [
"list(reversed('parrot'))"
]
},
{
"cell_type": "markdown",
"id": "21550b5f",
"metadata": {},
"source": [
"Wie in den Kapiteln zuvor erklärt, ist ein Palindrom ist ein Wort, welches vorwärts und rückwärts gleich geschrieben wird, wie \"Rentner\" oder \"Regallager\".\n",
"Schreiben Sie die Funktion `is_palindrome` um. Nutzen Sie hierzu die neuen Funktionen aus dieser Lektion: `reversed`, `list` und `join`."
]
},
{
"cell_type": "markdown",
"id": "3748b4e0",
"metadata": {
"tags": [
"remove-cell"
]
},
"source": [
"Hier ist eine Struktur für die Funktion, die Doctests enthält, mit denen Sie Ihre Funktion testen können."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9179d51c",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"def is_palindrome(word):\n",
" \"\"\"Prüfen ob ein Wort ein Palindrom ist.\n",
" \n",
" >>> is_palindrome('bob')\n",
" True\n",
" >>> is_palindrome('alice')\n",
" False\n",
" >>> is_palindrome('a')\n",
" True\n",
" >>> is_palindrome('')\n",
" True\n",
" \"\"\"\n",
" return False"
]
},
{
"cell_type": "markdown",
"id": "c083d1aa-ed3c-47d1-842d-a8b1ea962abc",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "16d493ad",
"metadata": {},
"outputs": [],
"source": [
"def is_palindrome(word):\n",
" \"\"\"Prüfen ob ein Wort ein Palindrom ist.\n",
" \n",
" >>> is_palindrome('bob')\n",
" True\n",
" >>> is_palindrome('alice')\n",
" False\n",
" >>> is_palindrome('a')\n",
" True\n",
" >>> is_palindrome('')\n",
" True\n",
" \"\"\"\n",
" return word == ''.join(reversed(word)) "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "33c9b4ec",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"run_doctests(is_palindrome)"
]
},
{
"cell_type": "markdown",
"id": "ad857abf",
"metadata": {},
"source": [
"Sie können die folgende Schleife verwenden, um alle Palindrome in der Wortliste zu finden, die mindestens 7 Buchstaben haben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fea01394",
"metadata": {
"tags": [
"remove-output"
]
},
"outputs": [],
"source": [
"for word in word_list:\n",
" if len(word) >= 7 and is_palindrome(word):\n",
" print(word)"
]
},
{
"cell_type": "markdown",
"id": "11386f70",
"metadata": {},
"source": [
"### Aufgabe 3\n",
"\n",
"Schreiben Sie eine Funktion namens `reverse_sentence`, die als Argument eine Zeichenkette mit einer beliebigen Anzahl durch Leerzeichen getrennter Wörter enthält.\n",
"Sie sollte eine neue Zeichenkette zurückgeben, die die gleichen Wörter in umgekehrter Reihenfolge enthält.\n",
"Wenn das Argument zum Beispiel \"Drehe diesen Satz um\" ist, sollte das Ergebnis \"Um Satz diesen drehe\" sein.\n",
"\n",
"Tipp: Sie können die `capitalize`-Methoden verwenden, um den ersten Buchstaben des ersten Wortes großzuschreiben. "
]
},
{
"cell_type": "markdown",
"id": "13882893",
"metadata": {
"tags": [
"remove-cell"
]
},
"source": [
"Für den Anfang ist hier eine Gliederung der Funktion mit Doctests:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d9b5b362",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"def reverse_sentence(input_string):\n",
" ''' Kehre die Reihenfolge der Wörter eines Strings um und schreibe das erste Wort groß.\n",
" \n",
" >>> reverse_sentence('Schreibe diesen Satz umgekehrt')\n",
" 'Umgekehrt Satz diesen Schreibe'\n",
" \n",
" >>> reverse_sentence('Python')\n",
" 'Python'\n",
" \n",
" >>> reverse_sentence('')\n",
" ''\n",
" \n",
" >>> reverse_sentence('One for all and all for one')\n",
" 'One for all and all for one'\n",
" '''\n",
"\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a2cb1451",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "769d1c7a",
"metadata": {
"tags": [
"remove-cell"
]
},
"outputs": [],
"source": [
"run_doctests(reverse_sentence)"
]
},
{
"cell_type": "markdown",
"id": "fb5f24b1",
"metadata": {},
"source": [
"### Aufgabe 4\n",
"\n",
"Schreiben Sie eine Funktion namens `total_length`, die eine Liste mit Zeichenketten aufnimmt und die Gesamtlänge der Zeichenketten zurückgibt.\n",
"Die Gesamtlänge der Wörter in `word_list` sollte $902{.}728$ sein."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1fba5377",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "bc6f1873-413c-4915-aa23-851092691049",
"metadata": {},
"source": [
"### Aufgabe 5\n",
"Schreiben Sie eine Funktion `nested_sum`, die eine Liste von Listen von ganzen Zahlen erwartet, 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 außerhalb 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,
"id": "0a7b753f-8573-4f4c-9ab6-96fc2f84aaad",
"metadata": {},
"outputs": [],
"source": [
"def nested_sum(t):\n",
" # Implementieren Sie hier die Funktion\n",
" pass"
]
},
{
"cell_type": "markdown",
"id": "5f0715b2-886e-4a76-a267-e72682525750",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d366fcdd-6e26-4a38-8b35-3b81738ea6c6",
"metadata": {},
"outputs": [],
"source": [
"def nested_sum(t):\n",
" \"\"\"Berechnet die Gesamtsumme aller Zahlen in einer Liste mit Listen.\n",
" \n",
" t: Liste mit Listen von ganzen Zahlen\n",
"\n",
" Rückgabe: Zahl\n",
" \"\"\"\n",
" total = 0\n",
" for nested in t:\n",
" total += sum(nested)\n",
" return total\n",
"\n",
"t = [[1, 2], [3], [4, 5, 6]]\n",
"nested_sum(t)"
]
},
{
"cell_type": "markdown",
"id": "4f39e8a2-97b6-4bd9-9b2a-efb409b34737",
"metadata": {},
"source": [
"### Aufgabe 6\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,
"id": "bb025e8f-3e0c-446e-8ae3-3d1a5e6c4aa0",
"metadata": {},
"outputs": [],
"source": [
"def cumsum(t):\n",
" # Implementieren Sie hier die Funktion\n",
" pass"
]
},
{
"cell_type": "markdown",
"id": "3790c014-af70-46da-ac31-002545ef4e36",
"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,
"id": "dfe3c138-c1c9-40c0-a1f2-be5c0d15326d",
"metadata": {},
"outputs": [],
"source": [
"#Testen Sie hier verschiedene Listen, bis Sie das korrekte Ergebnis erhalten."
]
},
{
"cell_type": "markdown",
"id": "18656334-4c9f-4778-a2ca-177b7f078b2c",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "880c2de7-099f-42f9-94a7-8286a4c96060",
"metadata": {},
"outputs": [],
"source": [
"def cumsum(t):\n",
" \"\"\"Berechnet die kumulative Summe der Zahlen in t.\n",
"\n",
" t: Liste mit Zahlen\n",
"\n",
" Rückgabe: Liste mit Zahlen\n",
" \"\"\"\n",
" total = 0\n",
" res = []\n",
" for x in t:\n",
" total += x\n",
" res.append(total)\n",
" return res\n",
"\n",
"t = [1,4,1,6,9] \n",
"cumsum(t)\n"
]
},
{
"cell_type": "markdown",
"id": "dbd442f9-25f3-46b7-822e-bf7e05c23297",
"metadata": {},
"source": [
"### Aufgabe 7\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",
"<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 Indizes bis es richtig funktioniert.\n",
" \n",
" </div> \n",
"</details> "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0e142393-cba1-48d6-856f-dc0c557ffe09",
"metadata": {},
"outputs": [],
"source": [
"def middle(t):\n",
" # Implementieren Sie hier die Funktion\n",
" pass"
]
},
{
"cell_type": "markdown",
"id": "c501df1c-44b1-4238-abd0-8a9268f41691",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b40ab9dc-1c5e-4111-bea0-79e7cc4b4ea6",
"metadata": {},
"outputs": [],
"source": [
"def middle(t):\n",
" \"\"\"Gibt alles außer dem ersten und letzten Element von t zurück.\n",
"\n",
" t: Liste\n",
"\n",
" Rückgabe: neue Liste\n",
" \"\"\"\n",
" return t[1:-1]\n",
"\n",
"t = [5,4,6,7,9]\n",
"middle(t)\n"
]
},
{
"cell_type": "markdown",
"id": "dfeb6f71-e01c-4f02-bec3-a93c83bdc695",
"metadata": {},
"source": [
"### Aufgabe 8\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. Worin besteht der Unterschied zur Funktion `middle` von Aufgabe 7? \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": "markdown",
"id": "be413cb5-7e8d-4983-98c6-f7a6a1bf73b3",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6b87d1a4-5c1d-4e03-997b-6c76056a8ea2",
"metadata": {},
"outputs": [],
"source": [
"def chop(t):\n",
" \"\"\"Removes the first and last elements of t.\n",
"\n",
" t: list\n",
"\n",
" returns: None\n",
" \"\"\"\n",
" del t[0]\n",
" del t[-1]\n",
"\n",
"t = [5,4,6,7,9]\n",
"chop(t)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "88c84c5c-2737-4c52-b578-f5f0e7536db5",
"metadata": {},
"outputs": [],
"source": [
"t"
]
},
{
"cell_type": "markdown",
"id": "1ea83c61-0175-48f5-8f8f-af57980817f5",
"metadata": {},
"source": [
"### Aufgabe 9\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,
"id": "6bc9eb11-551f-411d-b936-38fa72f7e4e2",
"metadata": {},
"outputs": [],
"source": [
"def is_sorted(t):\n",
" # Implementieren Sie hier die Funktion\n",
" pass"
]
},
{
"cell_type": "markdown",
"id": "fa1ce82b-7845-40f1-8d6e-0053c66fea23",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8902bff9-88ab-4fa2-86a0-36824ffd3a8a",
"metadata": {},
"outputs": [],
"source": [
"def is_sorted(t):\n",
" \"\"\"Überprüft, ob eine Liste sortiert ist.\n",
"\n",
" t: Liste\n",
"\n",
" Rückgabe: Boolscher Wert\n",
" \"\"\"\n",
" return t == sorted(t)\n",
"\n",
"t = [1,4,7,8]\n",
"is_sorted(t)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4987b893-9f4e-4374-af90-0de2e6bb0830",
"metadata": {},
"outputs": [],
"source": [
"t = [3,2,7,8]\n",
"is_sorted(t)"
]
},
{
"cell_type": "markdown",
"id": "11c7f5c3-7d38-418f-9c0c-bce6a44bdc8d",
"metadata": {},
"source": [
"### Aufgabe 10\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",
"<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 dass zwei Elemente gleich sind, wird die Schleife verlassen und `False` zurückgegeben.\n",
" \n",
" </div> \n",
"</details>\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "788ac1f0-ef79-4d24-ab4d-e0cd535c57d5",
"metadata": {},
"outputs": [],
"source": [
"def has_duplicates(t):\n",
" # Implementieren Sie hier die Funktion\n",
" pass"
]
},
{
"cell_type": "markdown",
"id": "a8c753b8-6906-4f3b-b736-2a4c9198b2e2",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "02ff21b8-d1d2-4d4b-8796-65db9ada8e91",
"metadata": {},
"outputs": [],
"source": [
"def has_duplicates(s):\n",
" \"\"\"Gibt True zurück, wenn ein Element mehr als einmal in einer Folge autaucht.\n",
"\n",
" s: Zeichenkette oder Liste\n",
"\n",
" Rückgabe: Boolscher Wert\n",
" \"\"\"\n",
" # Kopie von t erstellen, um nicht den Parameter zu verändern\n",
" t = list(s)\n",
" t.sort()\n",
"\n",
" # prüfe auf benachbarte Elemente, die gleich sind\n",
" for i in range(len(t)-1):\n",
" if t[i] == t[i+1]:\n",
" return True\n",
" return False\n",
"\n",
"t = [1, 4, 7, 5]\n",
"has_duplicates(t)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9318c92a-3b54-4867-8475-6e00c2caf02b",
"metadata": {},
"outputs": [],
"source": [
"t = [1, 5, 5, 9]\n",
"has_duplicates(t)\n"
]
},
{
"cell_type": "markdown",
"id": "101d5319-4dab-4c57-97d0-431356b397c7",
"metadata": {},
"source": [
"### Aufgabe 11\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_duplicates`, 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_duplicates` übergeben, den Wert von `has_duplicates` 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_duplicates() testen. has_duplicates 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",
"Nachdem die Schleife erfolgreich durchlaufen wurde, haben Sie die Zahl der erfolgreichen Versuche. 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 ausgegeben, welcher Anteil an Tests dies in Prozent ist. Dafür können Sie die Anzahl an Versuchen mit doppeltem Geburtstag durch die Gesamtzahl 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,
"id": "2009e6de-7f5d-4566-b172-08451d42c108",
"metadata": {},
"outputs": [],
"source": [
"from random import randint\n",
"\n",
"# Implementieren Sie hier Ihr Programm"
]
},
{
"cell_type": "markdown",
"id": "975c4078-ca0f-4df3-bf20-b9ad3495d81d",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4855f654-6b05-40d2-b612-e8013d65ae39",
"metadata": {},
"outputs": [],
"source": [
"from random import randint\n",
" \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_duplicates(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",
"id": "ff35c13e-5f6d-4d01-99c3-50cae29364cf",
"metadata": {},
"source": [
"### Aufgabe 12\n",
"\n",
"Schreiben Sie eine Funktion, die die Datei `top10000de.txt` (siehe [unser Verzeichnis](https://scm.cms.hu-berlin.de/ibi/python/-/blob/tp3_seminar09/notebooks/top10000de.txt?ref_type=heads)) oder `words.txt` einliest (siehe [Abschnitt 9.1](seminar09.ipynb#9.1-Wortlisten-einlesen)) und daraus eine 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 weiter oben in diesem Notebook 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",
"Sie haben in diesem Notebook 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",
"\n",
"Nun können Sie mit Bauchgefü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",
"Hinweise zum Modul `time`:\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 Variable 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. Ziehen wir 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,
"id": "8d29d249-6521-4a1e-91ef-2c8596c22878",
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier die beiden Varianten Ihrer Funktion"
]
},
{
"cell_type": "markdown",
"id": "21f4f6f6-7c10-46dd-b23d-2ebdbf28a220",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6283ba87-4971-4efe-86b2-f76fae25953f",
"metadata": {},
"outputs": [],
"source": [
"import time\n",
"\n",
"def appending():\n",
" t = []\n",
" fin = open('top10000de.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)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "32db6dcd-1522-4036-b53d-031206efaca8",
"metadata": {},
"outputs": [],
"source": [
"def adding():\n",
" t = []\n",
" fin = open('top10000de.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)\n"
]
},
{
"cell_type": "markdown",
"id": "49582473-a952-4e4b-9a41-17f8410eeae7",
"metadata": {},
"source": [
"### Aufgabe 13\n",
"\n",
"Um zu überprüfen, ob sich ein Wort in einer Wortliste befindet, können wir den Operator `in` verwenden, was aber recht lange dauert, da der Operator dazu die Liste linear durchlaufen muss.\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: https://github.com/AllenDowney/ThinkPython2/blob/master/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 den Fall, dass das 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 einen 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`-Anweisungen rufen wir die `binary_search`-Funktion auf, dabei übergeben wir immer noch das gesuchte Wort, aber statt der ursprünglichen Liste übergeben wir nur die halbe Liste. Das erreichen wir, indem wir die ursprüngliche Liste zusamen mit einem Segementoperator übergeben, indem 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,
"id": "33d98076-aecb-46c7-a151-dbf74567b658",
"metadata": {},
"outputs": [],
"source": [
"def binary_search(t, w):\n",
" # Implementieren Sie hier die Funktion\n",
" pass"
]
},
{
"cell_type": "markdown",
"id": "ed0cde42-1199-4a5c-83b6-e585538433a3",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "44d64aa5-3d80-4600-a798-4d95f02ed765",
"metadata": {},
"outputs": [],
"source": [
"def binary_search(word_list, word):\n",
" \n",
" word_list = sorted(word_list)\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 = [1,3,6,2,7,19,22]\n",
"binary_search(t, 29)"
]
},
{
"cell_type": "markdown",
"id": "30652d09-6683-4e0e-8427-8811080ed26c",
"metadata": {},
"source": [
"### Aufgabe 14\n",
"Zwei Wörter sind ein \"umgekehrtes Paar\" (Englisch: *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: https://github.com/AllenDowney/ThinkPython2/blob/master/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 herauszufinden, 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 Notebook 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,
"id": "8e9a9bb3-6a64-4952-a788-d836ed56b7d1",
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier Ihr Programm\n"
]
},
{
"cell_type": "markdown",
"id": "f341342f-7b7c-4977-957c-ac7641a038aa",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e073dbc6-185a-4e2b-8cbf-7d03dfebb254",
"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",
"t = [\"viel\", \"lager\", \"regal\", \"als\", \"lief\"]\n",
"reverse_list(t)\n"
]
},
{
"cell_type": "markdown",
"id": "e451ec9c-bb98-4bc0-acba-32d7f9c6966e",
"metadata": {},
"source": [
"### Aufgabe 15\n",
"Zwei Wörter \"greifen ineinander\" (Englisch: *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 Programm, 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: https://github.com/AllenDowney/ThinkPython2/blob/master/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 zwei 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-Operator. 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",
"Wenn wir ein Wort finden, wollen wir dieses ausgeben. Hierfür geben wir einen Header aus, der anzeigt, dass ein Wort gefunden wurde und das Wort ausgibt, bevor ähnlich wie in der Prüffunktion die Subworte aus dem Originalwort erzeugt und einzeln ausgegeben 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 eine `if`-Anweisung analog zu der 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 ineinander greifenden 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 einer `print`-Anweisung ausgeben. Das bedeutet, dass jedes Wort und jedes Teilwort in einer eigenen Zeile ausgegeben wird. Vergessen Sie nicht, dass vollständige Wort auszugeben. Es ist daher auch hilfreich eine Trennzeile auszugeben, in der gesagt wird, dass ein neues Wort folgt.\n",
" \n",
" </div> \n",
"</details>"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f46fa0a1-c874-4324-bd16-6c0c05ddcf04",
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier das Programm"
]
},
{
"cell_type": "markdown",
"id": "ad5b01df-8750-4d7a-9e90-f05bcc6cad2b",
"metadata": {},
"source": [
"Schauen Sie mit Ihrer Funktion nach, ob es ineinandergreifende Wörter gibt in der Liste `top10000de.txt`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b6e581d0-9c49-4995-8afa-082ae9fbb1b0",
"metadata": {},
"outputs": [],
"source": [
"# erstellen der Wortliste\n",
"reader = open('top10000de.txt')\n",
"word_list = []\n",
"for line in reader:\n",
" word_list.append(line.strip())\n",
" "
]
},
{
"cell_type": "markdown",
"id": "b4d29a34-f7e0-402a-9e8c-bddea9e82f4b",
"metadata": {},
"source": [
"\n",
"<a data-flickr-embed=\"true\" href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
"\n",
"(Quelle: Jason Eppink, Flickr)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e1839ab1-afd9-467b-81cb-9e4876be2cc2",
"metadata": {},
"outputs": [],
"source": [
"def interlock(word_list, word):\n",
" \"\"\"Prüft, ob ein Wort zwei ineinandergreifende Wörter enthält.\n",
" word_list: Liste der Wörter\n",
" word: Wort\n",
" \"\"\"\n",
" evens = word[::2] # Buchstaben auf geraden Indizes\n",
" odds = word[1::2] # Buchstaben auf ungeraden Indizes\n",
" print(odds)\n",
" print(evens)\n",
" return binary_search(word_list, evens) and binary_search(word_list, odds) \n",
" \n",
"\n",
"def interlock_general(word_list, word, n=3):\n",
" \"\"\"Prüft, ob ein Wort zwei ineinandergreifende Wörter enthält.\n",
" word_list: Liste der Wörter\n",
" word: Wort\n",
" n: Anzahl der ineinandergreifenden Wörter\n",
" \"\"\"\n",
" for i in range(n):\n",
" inter = word[i::n]\n",
" if not binary_search(word_list, inter):\n",
" return False\n",
" return True\n",
"\n",
"def find_interlock(word_list, n):\n",
" for word in word_list:\n",
" if len(word)<n:\n",
" pass\n",
" if interlock_general(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_interlock(word_list, 2)\n"
]
},
{
"cell_type": "markdown",
"id": "aadee942-b8dd-4679-a331-e6023b569ad6",
"metadata": {},
"source": [
" Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). Rufen Sie dazu im Menü *File* den Punkt *Download as* → *Notebook* auf und nutzen Sie beispielsweise einen USB-Stick, E-Mail, Google Drive, Dropbox oder Ihre [HU-Box](https://box.hu-berlin.de/). \n"
]
},
{
"cell_type": "markdown",
"id": "3f98530e-bfe6-4319-9898-50940c840ba4",
"metadata": {},
"source": [
"\n",
"\n",
"Herzlichen Glückwunsch! Sie haben das 9. Kapitel geschafft!"
]
},
{
"cell_type": "markdown",
"id": "5cf853f4-5575-408c-8446-bc993452dc66",
"metadata": {},
"source": [
"<img src=\"https://scm.cms.hu-berlin.de/ibi/python/-/raw/master/img/by-nc-sa.png\" alt=\"CC BY-NC-SA\" style=\"width: 150px;\"/>\n",
"\n",
"Der Text dieses Notebooks ist als freies Werk unter der Lizenz [CC BY-NC-SA 4.0 ](https://creativecommons.org/licenses/by-nc-sa/4.0/) verfügbar.\n",
"Der Code dieses Notebooks ist als freies Werk unter der Lizenz [MIT License](https://mit-license.org/) verfügbar.\n",
"\n",
"Es handelt sich um übersetzte und leicht veränderte Notebooks von [Allen B. Downey](https://allendowney.com) aus [Think Python: 3rd Edition](https://allendowney.github.io/ThinkPython/index.html).\n"
]
}
],
"metadata": {
"celltoolbar": "Tags",
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.2"
}
},
"nbformat": 4,
"nbformat_minor": 5
}