seminar06.ipynb

    "\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`? "
   ]
  },
  {
   "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",
    "1. Wie muss die Grundstruktur der Funktion aussehen, was ist der Kopf, was sind die Parameter?\n",
    "2. Wie ist die Funktion aufgebaut, wie viele Zweige hat sie? Schreiben Sie die leeren Zweige mit `return`-Anweisungen auf.\n",
    "3. Was sind die Bedingungen für die einzelnen Zweige, übergeben Sie diese den verschiedenen `if`-Anweisungen. \n",
    "4. Was wird im Basisfall $m=0$ zurückgegeben? Schreiben Sie die `return`-Anweisung für diesen Zweig.\n",
    "5. Was passiert wenn n gleich null ist? Mit welchen Werten wird ack aufgerufen? Geben Sie den neuen Aufruf hinter der `return`-Anweisung ein.\n",
    "6. Was passiert im letzten Zweig? Hier wird es ein wenig kompliziert, aber im Prinzip müssen sie den Ausdruck aus der Formel oben nur hinter der `return`-Anweisung abschreiben\n",
    "7. Vielleicht wollen Sie jetzt noch Wächter einbauen oder eine `Doc-String` schreiben, die dem Nutzer klar sagt, für welche Zahlen `ack` definiert ist. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ack(m,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 [Kapitel 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?\n",
    "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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Testen Sie hier die Funktionen first, last und middle "
   ]
  },
  {
   "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",
    "\n",
    "1. Verwenden Sie die Funktionen first, last und middle.\n",
    "2. Überlegen Sie wann ein Palindrom ein Palindrom ist und wie sie das einfach testen können.\n",
    "3. Wenn Sie von außen nach innen immer Zeichenpaare vergleichen und diese Stimmen miteinander überein, dann haben Sie ein Palindrom.\n",
    "4. Wir wollen das ganze rekursiv implementieren, was ist dabei der Basisfall? \n",
    "5. Eine Zeichenkette mit einem oder keinem Zeichen ist immer ein Palindrom und damit der Basisfall und einer der Zweige in denen die Funktion abbricht und einen Wert-  nämlich `True`zurückgibt. Wir können die Länge der Zeichenkette mit der `len` Funktion testen.\n",
    "6. Wann sonst bricht die Funktion ab, gibt aber `False` zurück?\n",
    "7. Wenn das erste und letzte Zeichen, der momentanen Zeichenkette nicht übereinstimmen\n",
    "8. Wir rufen `ist_palindrom` rekursiv mit `middle` auf um die Zeichenkette ohne den ersten und letzten Buchstaben zu erhalten, damit wird die Zeichenkette immer kürzer und bricht entweder ab, weil sie zu kurz ist- dann ist es ein Palindrom- oder weil das erste und letzte Zeichen nicht übereinstimmen - dann ist es kein Palindrom \n",
    "\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://imagesvc.timeincapp.com/v3/mm/image?url=https%3A%2F%2Ftimedotcom.files.wordpress.com%2F2015%2F04%2Fgo-hang-a-salami.jpg&w=800&q=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`). Hinweis: Überlegen Sie sich, was der Basisfall ist und wie Sie diesen behandeln."
   ]
  },
  {
   "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)\n",
    "\n",
    "1. Schreiben Sie erst den Kopf der Funktion inklusive Parametern\n",
    "2. Bevor Sie den Rest der Funktion implementieren, müssen Sie sich den Basisfall überlegen.\n",
    "3. Der Basisfall ist b=1 -- und darausfolgend auch a=b\n",
    "4. Was ist die Ausgabe, wenn der Basisfall erreicht wird?\n",
    "5. Was müssen Sie überprüfen um herauszufinden ob $a$ eine Potenz von $b$ ist?\n",
    "6. Wenn $a$ nicht restlos durch $b$ teilbar ist, kann $a$ keine Potenz von $b$ sein. Implementieren Sie diese Aussage\n",
    "7. Wie und wo muss die Funktion sich selber aufrufen?\n",
    "8. Die Funktion muss sich !mit `return`-Anweisung! selber aufrufen wenn a%b==0 gilt\n",
    "9. Dabei wird $a/b$ für $a$ übergeben."
   ]
  },
  {
   "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier die Funktion ggt\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<a data-flickr-embed=\"true\"  href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
    "\n",
    "(Quelle: Jason Eppink, Flickr)\n",
    "\n",
    "1. Wie muss der Kopf der Funktion aussehen, welche Parameter werden übergeben?\n",
    "2. Was müssen wir für den Basisfall überprüfen? Schreiben Sie die passende `if`-Bedingung\n",
    "3. Was wird im Basisfall zurück gegeben? Schreiben Sie die `return`-Anweisung\n",
    "4. Wie können Sie den Rest der Division von $a/b$ berechnen?\n",
    "5. Rufen Sie die Funktion rekursiv auf, übergeben Sie dabei die passenden Varibablen und vergessen  Sie die `return`-Anweisung dabei nicht."
   ]
  },
  {
   "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)\n",
    "    \n"
   ]
  },
  {
   "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
}