seminar06.ipynb

   "source": [
    "## Glossar\n",
    "\n",
    "Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 6 gelernt haben:\n",
    "\n",
    "- temporäre Variable:\n",
    "- toter Code:\n",
    "- schrittweise Entwicklung\n",
    "- Hilfscode:\n",
    "- Wächter: Auch *guardian* genannt, beschützt der \"Wächter\" darauf folgenden Code vor Eingaben, die zu Fehlern führen können.\n",
    "\n",
    "Ergänzen Sie die Liste in eigenen Worten. Das ist eine gute Erinnerungs- und Übungsmöglichkeit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Übung\n",
    "\n",
    "### Aufgabe 1\n",
    "\n",
    "Zeichnen Sie (mit Bleistift und Papier) ein Stapeldiagramm für das folgende Programm wenn bei der Ausführung die Zeile `x = x + 1` in der Funktion `a` erreicht wurde. Was gibt das Programm aus?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def b(z):\n",
    "    prod = a(z, z)\n",
    "    print(z, prod)\n",
    "    return prod\n",
    "\n",
    "def a(x, y):\n",
    "    x = x + 1\n",
    "    return x * y\n",
    "\n",
    "def c(x, y, z):\n",
    "    total = x + y + z\n",
    "    square = b(total)**2\n",
    "    return square\n",
    "\n",
    "x = 1\n",
    "y = x + 1\n",
    "print(c(x, y+3, x+y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 2\n",
    "\n",
    "Die [Ackermannfunktion](https://de.wikipedia.org/wiki/Ackermannfunktion), $A(m, n)$ ist folgendermaßen definiert:\n",
    "\n",
    "\\begin{equation}\n",
    "A(m,n) = \n",
    "\\begin{cases}\n",
    "n+1       & \\ \\ \\text{falls}\\ m=0\\\\\n",
    "A(m-1, 1) & \\ \\ \\text{falls}\\ m > 0\\ \\text{und}\\ n = 0\\\\\n",
    "A(m-1, A(m, n-1)) & \\ \\ \\text{falls}\\ m > 0\\ \\text{und}\\ n > 0\n",
    "\\end{cases}\n",
    "\\end{equation}\n",
    "\n",
    "Schreiben Sie eine Funktion `ack` die die Ackermannfunktion berechnet. Berechnen Sie mit ihrer Funktion `ack(3,4)`, was 125 ergeben sollte. Was passiert für größere Werte von `m` und `n`?\n",
    "\n",
    "In den folgenden Hinweisen werden wir die Funktion schrittweise entwickeln. Versuchen Sie, die Aufgabe in Partnerarbeit zu lösen und verwenden Sie so wenige Hinweise wie möglich.\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Schreiben Sie zuerst den Kopf der Funktion und überlegen Sie sich, wieviele Zweige Ihre Funktion benötigt. Schreiben Sie die entsprechende Anzahl an `if`-Bedingungen (bzw. `elif`-Bedingungen) und `return`-Anweisungen. Keine Sorge, Sie müssen sich an dieser Stelle noch keine Gedanken machen, wie die `if`-Bedingungen aussehen werden.\n",
    "  </div>       \n",
    "</details>   \n",
    "   \n",
    "  \n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Im nächsten Schritt werden wir die korrekten `if`-Bedinungen schreiben. Die geschweifte Klammer in der mathematischen Notation unterscheidet die unterschiedlichen Fälle, die bei bestimmten Bedingungen eintreten. Die Bedingungen stehen hinter dem Schlüsselwort \"falls\". Übersetzen Sie diese Formel in Python. Fügen Sie in jedem Zweig eine `print`-Anweisung ein, die den Zweig eindeutig identifiziert. Wir werden diese Hilfsanweisung später löschen. Testen Sie jetzt, ob Ihre Funktion für verschiedene Eingabewerte den korrekten Zweig ansteuert. Testen Sie auch die Möglichkeiten `m=0` und `n=0`. Im nächsten Hinweis (2.5) finden Sie die verschiedenen `if`-Bedingungen.\n",
    "  </div>       \n",
    "</details>  \n",
    "  \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">2.5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Die `if`-Bedingungen sind: `if m==0:`für den Basisfall, `elif n==0 and m>0:` und `elif m>0 and n>0:`\n",
    "      \n",
    "  </div>       \n",
    "</details>   \n",
    "  \n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Im nächsten Schritt werden wir den korrekten Rückgabewert für den Basisfall eingeben. Anschließend testen Sie Ihre Funktion mit einem Aufruf des Basisfalls. Schauen Sie sich an, wie die Anweisung für die Berechnung des Basisfalls lauten muss. Sie können die korrekte Anweisung in Hinweis 3.5 nachlesen, wenn Sie sich unsicher sind oder Ihr Code nicht korrekt funktioniert.\n",
    "      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3.5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Die Rückgabe im Basisfall muss `return n+1` lauten. \n",
    "      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "     \n",
    "Anschließened beschäftigen wir mit der Bedingung `n==0`. Schauen Sie sich auch hier wieder die Formel an und versuchen Sie herauszufinden, welche Werte Sie beim rekursiven Aufruf übergeben müssen. In 4.5 können Sie den korrekten Aufruf nachlesen, wenn Sie dabei Hilfe brauchen.  \n",
    "      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4.5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "     \n",
    "Die korrekte Anweisung lautet: `return ack (m-1,1)`     \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Der letzte Zweig wird aufgerufen, wenn sowohl m als auch n größer als Null sind. Schauen Sie sich genau an, wie die Funktion dabei definiert ist. Dabei fällt auf, dass die Funktion sich selbst im Funktionsaufruf rekursiv aufruft. Schreiben Sie diesen Funktionsaufruf und achten Sie auf die richtige Klammersetzung. Wenn Sie Hilfe brauchen, können Sie sich den korrekten Aufruf in 5.5 anschauen, versuchen Sie es aber zunächst einmal selber und testen Sie, ob bei Ihrem Aufruf das korrekte Ergebnis erscheint.  \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5.5 Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Die korrekte `return`-Anweisung lautet: `return ack (m-1, ack(m, n-1))`    \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Jetzt funktioniert Ihr Code wie gewünscht. An dieser Stelle ist es sinnvoll, Wächter und einen Doc-String einzubauen. Überlegen Sie dabei, für welche Zahlenbereiche die Funktion definiert ist und stellen Sie sicher, dass ihr Code das zu Beginn überprüft. Schreiben Sie auch einen Doc-String, der beschreibt, welche Eingaben die Funktion akzeptiert und was Sie als Ergebnis ausgibt.\n",
    "  </div>       \n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier die Ackermannfunktion\n",
    "\n",
    "\n",
    "# Testaufruf\n",
    "ack(3,4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a data-flickr-embed=\"true\"  href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
    "\n",
    "(Quelle: Jason Eppink, Flickr)\n",
    "\n",
    "Es folgt der Code, der Mithilfe der Hinweise entwickelt wurde. Wenn Ihr Code etwas anders aussieht, ist das selbstverständlich okay, solange er das korrekte Ergebnis berechnet.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ack(m,n):\n",
    "    \n",
    "    '''Die Funktion erwartet 2 positive ganze Zahlen m und n und berechnet daraus die Ackermannfunktion.\n",
    "    Werden ungültige Werte eingegeben, ist der Rückgabewert None und ein Fehler wird ausgegeben, anderfalls wird\n",
    "    das Ergebnis zurückgegeben.'''\n",
    "    \n",
    "    if m<0 or n<0:\n",
    "        print(\"Funktion nicht definiert\")\n",
    "        return None\n",
    "    if not isinstance (n, int) or not isinstance (m, int):\n",
    "        print (\"Funktion nicht definiert\")\n",
    "        return None\n",
    "    if m==0:\n",
    "        return n+1\n",
    "    if n==0 and m>0:\n",
    "        return ack (m-1,1)\n",
    "    if m>0 and n>0:\n",
    "        return ack (m-1, ack(m, n-1))\n",
    "    \n",
    "    \n",
    "ack(3,4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 3\n",
    "\n",
    "Ein [Palindrom](https://de.wikipedia.org/wiki/Palindrom) ist ein Wort, welches vorwärts und rückwärts gelesen gleich ist. Beispielsweise \"neben\" oder \"hangnah\" (wenn wir Großschreibung ignorieren, gibt es auch Substantive, z.B. \"Reliefpfeiler\" oder \"Anna\"). Rekursiv definiert, ist ein Wort ein Palindrom, wenn der erste und letzte Buchstabe identisch sind und der Mittelteil ein Palindrom ist.\n",
    "\n",
    "Die folgenden Funktionen erwarten eine Zeichenkette als Argument und geben die ersten, letzten und mittleren Buchstaben zurück:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def first(word):\n",
    "    return word[0]\n",
    "\n",
    "def last(word):\n",
    "    return word[-1]\n",
    "\n",
    "def middle(word):\n",
    "    return word[1:-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir werden in [Seminar 8](seminar08.ipynb) sehen, wie sie funktionieren.\n",
    "\n",
    "1. Testen Sie diese Funktionen. Was passiert, wenn Sie `middle` mit einer Zeichenkette mit nur zwei Zeichen aufrufen? Oder mit nur einem Zeichen? Was passiert mit der leeren Zeichenkette, geschrieben `''`, die keine Zeichen enthält?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Testen Sie hier die Funktionen first, last und middle "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Schreiben Sie eine Funktion `ist_palindrom`, die eine Zeichenkette als Argument erwartet und `True` zurückliefert, wenn die Zeichenkette ein Palindrom ist und ansonsten `False`. (Erinnern Sie sich daran, dass Sie mit der eingebauten Funktion `len` die Länge einer Zeichenkette ermitteln können.) \n",
    "\n",
    "Wie gehabt, folgen jetzt einige Hinweise, versuchen Sie zunächst die Aufgaben in Partnerarbeit zu lösen und verwenden Sie so wenige von den Hinweisen wie möglich, das ist die beste Übung:\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Wir werden uns die Funktionen `first, last` und `middle` zu nutze machen um die Funktion zu schreiben.\n",
    "      \n",
    "  </div>       \n",
    "</details>   \n",
    "   \n",
    "  \n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Schreiben Sie zunächst den Kopf der Funktion. welche Zustände muss die Funktion zurückgeben? Schreiben Sie auch die entsprechenden Rückgabeeingaben, machen Sie sich (noch) keinen Kopf darüber, wie sie entscheiden, welcher Wert zurückgegeben wird. Wenn Sie die Funktion jetzt testen wird immer der erste Rückgabewert, den Sie eingegeben haben zurückgegeben. \n",
    "  </div>       \n",
    "</details>  \n",
    "  \n",
    "   \n",
    "  \n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Wenn wir automatisch ein Palindrom testen wollen, vergleichen wir immer den ersten mit dem letzen Buchstaben, diese müssen gleich sein. Das bedeutet, das der hier geschriebene Test bei Palindromen mit unterschiedlich gesetzen Leerzeichen kein Palindrom findet.      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    " Wir werden die Funktion rekursiv implementieren, wir müssen uns also den Basisfall eines Palindroms überlegen. Wie könnte dieser Basisfall aussehen? \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "     \n",
    "Der Basisfall für ein Palindrom ist eine Zeichenkette mit nur einem oder keinem Zeichen ist immer ein Palindrom. Für diesen Wert gibt die Funktion den Wert `True` zurück. Verwenden Sie die Funktion `len` um die Länge der Zeichenkette zu testen und schreiben Sie die entsprechende `if`-Bedingung.\n",
    "      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "     \n",
    "Was muss die Abbruchbedingung sein, wenn die Funktion `False` zurückgeben soll?\n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Verwenden Sie einen Test auf Ungleichheit. Da in einem Palindrom der erste und letzte Buchstabe gleich sein müssen, geben Sie `False` zurück, wenn der Rückgabewert von `first` und `last` nicht gleich ist.      \n",
    "    \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">8. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Abschließend müssen die noch den Rekursiven Funktionsaufruf schreiben. Überlegen Sie, wie Sie die Funktion mit dem zweiten bis vorletzten Buchstaben aufrufen können. \n",
    "      \n",
    "    </div>       \n",
    "</details>\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">9. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Der rekursive Funktionsaufruf muss `ist_palindrom(middle(s))` lauten\n",
    "  </div>       \n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie die Funktion ist_palindrom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<a data-flickr-embed=\"true\"  href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
    "\n",
    "(Quelle: Jason Eppink, Flickr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ist_palindrom(s):\n",
    "    if len(s)<=1:\n",
    "        return True\n",
    "    elif first(s)!=last(s): \n",
    "        return False\n",
    "    return ist_palindrom(middle(s))\n",
    "    \n",
    "ist_palindrom(\"gohangasalamiimalasagnahog\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Palindrom](https://api.time.com/wp-content/uploads/2015/04/go-hang-a-salami.jpg?w=800&quality=85) \n",
    "\n",
    "([Farrar, Straus and Giroux](http://time.com/3771063/mark-saltveit-world-palindrome-championship/))\n",
    "\n",
    "### Aufgabe 4\n",
    "\n",
    "Eine Zahl $a$ ist eine Potenz von $b$, wenn $a$ durch $b$ teilbar ist und $a/b$ eine Potenz von $b$ ist. (Beispielsweise ist 27 eine Potenz von 3, denn 27 ist durch 3 teilbar und 9 ist eine Potenz von 3.) Schreiben Sie eine Funktion `ist_potenz` die Parameter `a` und `b` erwartet und `True` zurückgibt, wenn `a` eine Potenz von `b` ist (ansonsten `False`). \n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-info\">Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Überlegen Sie sich, was der Basisfall ist und wie Sie diesen behandeln.\n",
    "      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "Es folgen wie immer Hinweise zum Lösen der Aufgabe. Versuchen Sie zunächst, die Aufgabe in Partnerarbeit zu lösen, so lernen Sie immer am besten. \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Schreiben Sie zunächst wie üblich den Kopf der Funktion inklusive der Parameter und schreiben Sie auch bereits die `return`-Anweisungen für die möglichen Ergebnisse der Funktion. Wir kümmern uns anschließend darum, wie diese Werte jeweils erreicht werden.\n",
    "      \n",
    "  </div>       \n",
    "</details>   \n",
    "   \n",
    "  \n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Wir müssen uns die beiden Basisfälle überlegen. Diese sind die Fälle, bei denen die Funktion `True` zurückgibt. Die Basisfälle sind `a==b` und `b==1`. Machen Sie sich klar, warum diese Fälle die Basisfälle sind.\n",
    "  </div>       \n",
    "</details>  \n",
    "  \n",
    "   \n",
    "  \n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Überlegen Sie nun, wie Sie testen können, ob eine Zahl die Potenz einer anderen Zahl ist. Verwenden Sie den `modulo` Operator.\n",
    "\n",
    "    \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Damit eine Zahl eine Potenz einer anderen Zahl sein kann, muss Sie restlos durch die andere Zahl teilbar sein. Implementieren Sie die Verzweigung und schreiben Sie den Zweig, der `False` zurück gibt. Das ist der Zweig, der ausgeführt wird, wenn alle anderen Bedingungen nicht erfüllt werden.\n",
    "\n",
    "   </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "     \n",
    "Wenn sich $a$ restlos durch $b$ teilen lässt, muss sich in diesem Zweig die Funktion mit einer `return`-Anweisung rekursiv aufrufen. Überlegen Sie sich, welche Werte für $a$ und $b$ übergeben werden müssen.\n",
    "      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "     \n",
    "Für $a$ müssen Sie $a/b$ übergeben, da Sie ja prüfen müssen, ob $a/b$ auch restlos durch $b$ teilbar ist. Für $b$ müssen Sie daher wieder $b$ übergeben.\n",
    "\n",
    "   </div>       \n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier die Funktion ist_potenz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<a data-flickr-embed=\"true\"  href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
    "\n",
    "(Quelle: Jason Eppink, Flickr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ist_potenz(a,b):\n",
    "     if b==1 or a==b:\n",
    "        return True\n",
    "     if a%b==0:\n",
    "        return ist_potenz (a/b, b) \n",
    "     else:\n",
    "        return False\n",
    "ist_potenz(12,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 5\n",
    "\n",
    "Der [größte gemeinsame Teiler](https://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler) (ggT) von $a$ und $b$ ist die größte Zahl die beide Zahlen ($a$ und $b$) ohne Rest teilt.\n",
    "\n",
    "Eine Möglichkeit den ggT zweier Zahlen zu berechnen, beruht auf der Beobachtung, dass, wenn $r$ der Rest der Division von $a$ durch $b$ ist, dann $ggT(a,b) = ggT(b,r)$ gilt. Als Basisfall können wir $ggT(a,0)=a$ nutzen.\n",
    "\n",
    "Schreiben Sie eine Funktion `ggt`, die zwei Parameter `a` und `b` erwartet und den größten gemeinsamen Teiler zurückgibt. Bedenken Sie, dass wir für die Berechnung anders vorgehen als bei der Verwendung des Euklidischen Algorithmus. Nutzen Sie die Hinweise, wenn Sie Hilfe benötigen. \n",
    "\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Schreiben Sie zunächst den Kopf der Funktion und die `return`-Anweisung. Lassen Sie die Funktion zuerst einen Platzhalter zurückgeben, wir werden uns in späteren Schritten damit beschäftigen, das korrekte Ergebnis auszugeben.\n",
    "      \n",
    "  </div>       \n",
    "</details>   \n",
    "   \n",
    "  \n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Wie lautet der Basisfall? Schreiben Sie die `if`-Anweisung, die prüft, ob der Basisfall wahr ist. Passen Sie die `return`-Anweisung so an, dass das für den Basisfall passende Ergebnis zurückgegeben wird. Testen Sie, ob dies funktioniert, indem Sie die Funktion mit dem Basisfall aufrufen und sich das Ergebnis anschauen.\n",
    "\n",
    "  </div>       \n",
    "</details>  \n",
    "  \n",
    "   \n",
    "  \n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Da wir eine rekursive Funktion implementieren wollen, müssen wir uns überlegen, wie wir den rekursiven Aufruf gestalten können. Schauen Sie sich die Aufgabenstellung an und überlegen Sie, welche Argumente Sie dem Aufruf übergeben. \n",
    "\n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "\n",
    "Wir wollen für b den Rest aus der Divison von a und b übergeben. Berechnen Sie den Wert. Sie können direkt die Berechnung übergeben oder das Ergebnis in einer Variablen speichern und diese Variable übergeben. Für a übergeben wir b aus diesem Funktionsaufruf.\n",
    "      \n",
    "  </div>       \n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier die Funktion ggt\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a data-flickr-embed=\"true\"  href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
    "\n",
    "(Quelle: Jason Eppink, Flickr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ggt (a,b):\n",
    "    if b==0:\n",
    "        return a\n",
    "    r=a%b\n",
    "    return ggt(b,r)\n",
    "    \n",
    "    \n",
    "ggt (175,25)"
   ]
  },
  {
   "cell_type": "markdown",
   "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/7/70/Face-devil-grin.svg)\n",
    "\n",
    "Herzlichen Glückwunsch! Sie haben das 6. Kapitel geschafft. Weiter geht es in [7: Iteration](seminar07.ipynb)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}