seminar08.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Seminar Problemorientierte Programmierung\n",
    "\n",
    "## Exkurs: Was mir an Python gefällt\n",
    "\n",
    "In dieser Rubrik, die immer am Anfang eines Kapitels steht, möchte ich Ihnen zeigen, wofür ich Python nutze und warum ich es mag. Sie werden vielleicht noch nicht verstehen, was ich genau mache, aber Sie sehen damit schon einmal die Möglichkeiten von Python und können später darauf zurückgreifen. Da dies auch ein Exkurs ist, können Sie diese Rubrik gerne auch erst einmal überspringen.\n",
    "\n",
    "Mit den Operatoren aus diesem Kapitel können wir ganz leicht das Verfahren zur Umwandlung einer Dezimalzahl in ihre Binärdarstellung implementieren:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8 Zeichenketten\n",
    "\n",
    "Zeichenketten sind anders als ganze Zahlen, Gleitkommazahlen und Boolesche Werte. Eine Zeichenkette ist eine **Folge** (*sequence*), d.h. eine geordnete Menge einzelner Werte. In diesem Kapitel lernen wir, wie wir die Zeichen zugreifen können, aus denen eine Zeichenkette besteht und wir lernen einige der Funktionen kennn, die für Zeichenketten bereitgestellt werden.\n",
    "\n",
    "### 8.1 Eine Zeichenkette ist eine Folge\n",
    "\n",
    "Eine Zeichenkette ist eine Folge von Zeichen. Wir können auf die einzelnen Zeichen mit Hilfe des Klammer-Operators zugreifen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruit = 'banana'\n",
    "letter = fruit[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die zweite Anweisung wählt das Zeichen mit Nummer 1 aus der Zeichenkette `fruit` und weist dieses der Variable `letter` zu.\n",
    "\n",
    "Der Ausdruck in eckigen Klammern wird **Index** genannt. Der Index gibt an, welches Zeichen der Folge wir haben möchten.\n",
    "\n",
    "Allerdings entspricht das Ergebnis vielleicht nicht ganz dem, was wir erwartet hätten: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "letter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Für die meisten Menschen ist der erste Buchstabe von `banana` das `b` und nicht das `a`. Aber in der Informatik wird oft beginnend mit der Null gezählt und somit hat das erste Zeichen einer Zeichenkette den Index 0:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "letter = fruit[0]\n",
    "letter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Somit ist `b` der 0. Buchstabe von `banana`, `a` ist der 1. Buchstabe und `n` ist der 2. Buchstabe.\n",
    "\n",
    "Als Index können wir einen Ausdruck verwenden, der Variablen und Operatoren enthält:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "i = 1\n",
    "fruit[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruit[i + 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aber der Wert des Index muss eine ganze Zahl sein. Ansonsten erhalten wir eine Fehlermeldung:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "letter = fruit[1.5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.2 `len`\n",
    "\n",
    "`len` ist eine eingebaute Funktion, die die Anzahl der Zeichen einer Zeichenkette zurückgibt:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruit = \"banana\"\n",
    "len(fruit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Um auf das letzte Zeichen einer Zeichenkette zuzugreifen, würden Sie vielleicht folgendes versuchen: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "length = len(fruit)\n",
    "last = fruit[length]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Grund für diesen `IndexError` ist, dass es in `banana` kein Zeichen mit dem Index 6 gibt. Da wir ja mit Null begonnen haben zu zählen, sind die sechs Zeichen mit den Zahlen 0 bis 5 numeriert. Um also das letzte Zeichen zu extrahierren, müssen wir 1 von `length` abziehen: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "last = fruit[length - 1]\n",
    "last"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Alternativ können wir einen negativen Index nutzen, der rückwärts vom Ende der Zeichenkette her zählt. Der Ausdruck `fruit[-1]` ergibt das letzte Zeichen, `fruit[-2]` das vorletzte Zeichen, usw.:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruit[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruit[-2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.3 Durchlauf mit einer `for`-Schleife\n",
    "\n",
    "In vielen Berechnungen müsen wir eine Zeichenkette Zeichen für Zeichen verarbeiten. Oftmals beginnen wir mit dem ersten Zeichen und wählen dann in jedem Schritt das nächste Zeichen aus, machen etwas damit und fahren fort bis zum Ende der Zeichenkette. Diese Art von Prozess wird **Durchlauf** (*traversal*) genannt. Eine Möglichkeit einen Durchlauf zu programmieren, ist mit Hilfe einer `while`-Schleife:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "index = 0\n",
    "while index < len(fruit):\n",
    "    letter = fruit[index]\n",
    "    print(letter)\n",
    "    index = index + 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese Schleife durchläuft die Zeichenkette und  gibt jedes Zeichen in einer eigenen Zeile aus. Die Schleifenbedingung ist `index < len(fruit)`, so dass, sobald `index` gleich der Länge der Zeichenkette ist, die Bedingung nicht mehr erfüllt ist und die Schleife abgebrochen wird. Das letzte Zeichen, auf das zugegriffen wird, ist das mit dem Index `len(fruit)-1`, welches auch das letzte Zeichen der Zeichenkette ist.\n",
    "\n",
    "Schreiben Sie als Übung eine Funktion `streawkceur`, die eine Zeichenkette als Argument erwartet und die Buchstaben rückwärts anzeigt, mit einem Buchstaben pro Zeile:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier die Funktion streawkceur\n",
    "\n",
    "\n",
    "# Testaufruf\n",
    "print(streawkceur(\"streawkceur\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine andere Möglichkeit einen Durchlauf zu schreiben ist mit Hilfe der `for`-Schleife:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for letter in fruit:\n",
    "    print(letter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jedes Mal, wenn die Schleife durchlaufen wird, wird das nächste Zeichen der Variablen `letter` zugewiesen. Die Schleife fährt fort, bis keine Zeichen mehr übrig sind.\n",
    "\n",
    "Im folgenden Beispiel sehen wir, wie die Zeichenkettenverknüpfung und eine `for`-Schleife verwendet werden, um eine ABC-Schützen-Folge (sortierte Folge) zu erzeugen. In Robert McCloskeys Buch \"Make Way for Ducklings\", sind die Namen der Entenkücken *Jack, Kack, Lack, Mack, Nack, Ouack, Pack* und *Quack*. Die Schleife gibt die Namen in dieser Reihenfolge aus: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prefixes = 'JKLMNOPQ'\n",
    "suffix = 'ack'\n",
    "\n",
    "for letter in prefixes:\n",
    "    print(letter + suffix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Natürlich ist das nicht ganz korrekt, denn \"Ouack\" und \"Quack\" sind flasch geschrieben. Verändern Sie das Programm, um diesen Fehler zu beheben."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.4 Zeichenketten-Segmente\n",
    "\n",
    "Ein Teil einer Zeichenkette wird **Segment** (*slice*) gennannt. Ein Segment können wir ähnlich wie ein einzelnes Zeichen auswählen:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 'Monty Python'\n",
    "s[0:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s[6:12]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Operator `[n:m]` gibt uns den Teil der Zeichenkette vom n-ten bis zum m-ten Zeichen zurück, einschließlich des n-ten aber ohne das m-te Zeichen. Dieses Verhalten ist nicht eingängig, daher hilft es vielleicht, sich vorzustellen, dass die Indexe *zwischen* die Zeichen zeigen, wie in der folgenden Abbildung dargestellt:\n",
    "\n",
    "![Zeichenketten-Segmente](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/string_indices.svg)\n",
    "\n",
    "Wenn wir den ersten Index (vor dem Doppelpunkt) weglassen, beginnt das Segment mit dem ersten Zeichen der Zeichenkette. Wenn wir den zweiten Index weglassen, endet das Segment mit dem letzten Zeichen der Zeichenkette:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruit = 'banana'\n",
    "fruit[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruit[3:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn der erste Index größer oder gleich dem zweiten ist, dann ist das Ergebnis die **leere Zeichenkette** (*empty string*), die durch zwei Anführungszeichen (mit nichts dazwischen) repräsentiert wird:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruit = 'banana'\n",
    "fruit[3:3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine leere Zeichenkette enthält keine Zeichen und hat die Länge 0. Ansonsten ist es aber eine ganz normale Zeichenkette.\n",
    "\n",
    "Um unser Beispiel fortzuführen: was meinen Sie, bedeutet `fruit[:]`? Probieren Sie es aus!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.6 Zeichenketten sind unveränderbar\n",
    "\n",
    "Es ist verlockend, den `[]`-Operator auf der linken Seite einer Zuweisung zu verwenden, um ein Zeichen innerhalb einer Zeichenkette zu verändern. Beispielsweise:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "greeting = 'hello World!'\n",
    "greeting[0] = 'H'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das \"object\" in diesem Beispiel ist die Zeichenkette und das \"item\" das Zeichen, welches wir zuweisen wollten. Momentan können wir uns unter einem Objekt das gleiche wie einen Wert vorstellen, aber wir werden später (in [Abschnitt 10.10](seminar10.ipynb#Objekte-und-Werte)) genauer kennenlernen, was Objekte sind.\n",
    "\n",
    "Der Grund für den Fehler ist, dass Zeichenketten **unveränderbar** (*immutable*) sind. Das heisst, wie können eine existierende Zeichenkette nicht verändern. Das beste, was wir machen können, ist eine neue Zeichenkette zu erzeugen, die eine Variante des Originals ist:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "greeting = \"hello World!\"\n",
    "new_greeting = \"H\" + greeting[1:]\n",
    "new_greeting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In diesem Beispiel wird ein neuer Anfangsbuchstabe mit einem Segment von `greeting` zusammengefügt. Die ursprüngliche Zeichenkette verändert sich dadurch nicht."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.6 Suche\n",
    "\n",
    "Was macht die folgende Funktion? Probieren Sie es aus!\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find(word, letter):\n",
    "    index = 0\n",
    "    while index < len(word):\n",
    "        if word[index] == letter:\n",
    "            return index\n",
    "        index = index + 1\n",
    "    return -1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Auf gewisse Weise ist `find` das Inverse des `[]`-Operators. Anstatt einn Index zu nehmen und das entsprechende Zeichen zu extrahieren nimmt es ein Zeichen und findet den Index, an dem dieses Zeichen auftaucht. Wenn das Zeichen nicht gefunden wird, dann gibt die Funktion `-1` zurück.\n",
    "\n",
    "Das ist das erste Mal, dass wir eine `return`-Anweisung innerhalb einer Schleife sehen! Wenn `word[index] == letter`, dann bricht die Funktion die Schleife ab und gibt direkt `index` zurück.\n",
    "\n",
    "Wenn das Zeichen `letter` nicht in der Zeichenkette auftaucht, dann wird die Schleife ganz normal verlassen und es wird `-1` zurückgegeben.\n",
    "\n",
    "Dieses Berechnungsmuster - eine Folge durchlaufen und zurückkehren, sobald wir gefunden haben, wonach wir suchen - wird **Suche** genannt.\n",
    "\n",
    "Verändern Sie `find` so, dass es einen dritten Parameter hat, der den Index in `word` angibt, ab dem gesucht werden soll. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier die veränderte Funktion find"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.7 Schleifen ausführen und zählen\n",
    "\n",
    "Das folgende Programm zählt wie häufig der Buchstabe `a` in einer Zeichenkette auftaucht:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "word = 'banana'\n",
    "count = 0\n",
    "for letter in word:\n",
    "    if letter == 'a':\n",
    "        count = count + 1\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Program demonstriert ein anderes Berechnungsmuster, das **Zähler** (*counter*) genannt wird. Die Variabe `count` wird mit 0 initialisiert und dann jedesmall erhöht, wenn ein `a` gefunden wird. Wenn die Schleife beendet ist, dann enthält `count` das Ergebnis - die Gesamtzahl an `a`s.\n",
    "\n",
    "Verkapseln Sie den Code in einer Funktion mit Namen `count` und verallgemeinern Sie die Funktion, so dass sie die Zeichenkette und das gesuchte Zeichen als Parameter akzeptiert."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier die Funktion count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Schreiben Sie die Funktion jetzt so um, dass sie die Version von `find` mit den drei Parametern aus dem vorherigen Abschnitt verwendet.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Speichern](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/floppy.png) Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). Klicken Sie dazu oben links auf das Disketten-Icon und nutzen Sie beispielsweise einen USB-Stick, E-Mail, Google Drive, Dropbox oder Ihre [HU-Box](https://box.hu-berlin.de/).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Smiley](https://upload.wikimedia.org/wikipedia/commons/3/30/Binette-typo.png)\n",
    "\n",
    "Herzlichen Glückwunsch! Sie haben das 8. Kapitel geschafft. Weiter geht es in [9: Wortspiele](seminar09.ipynb)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}