seminar03.ipynb

    "    '''Ausgabe einer Kante'''\n",
    "    edge_part = \"+ \" + \"- \" * 4\n",
    "    print(edge_part * 4 + \"+\")\n",
    "\n",
    "    \n",
    "def print_gridRow():\n",
    "    '''Ausgabe einer Gitterzeile'''\n",
    "    print_edge_bigGrid()\n",
    "    do_four(print_innerSide_bigGrid)\n",
    "\n",
    "def print_row():\n",
    "    '''Ausgabe des vollständigen Gitters'''\n",
    "    do_four(print_gridRow)\n",
    "    print_edge_bigGrid()\n",
    "    \n",
    "print_row()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bonusaufgabe\n",
    "\n",
    " Finden Sie einen Algorithmus zur Lösung des folgenden Problems:\n",
    "   *Gegeben sei eine positive ganze Zahl `n`. Finden Sie eine Liste\n",
    "   von positiven ganzen Zahlen, so dass das Produkt der Zahlen am\n",
    "   größten unter allen positiven ganzen Zahlen ist, deren Summe\n",
    "   gleich `n` ist.*\n",
    "\n",
    "   Zum Beispiel: \n",
    "   - Für `n = 4` ist die gesuchte Liste `(2,2)`, denn `2 * 2` ist größer als `1 * 1 * 1 * 1`, `2 * 1 * 1` und `3 * 1`.\n",
    "   - Für `n = 5` ist die gesuchte Liste `(2,3)`.\n",
    "\n",
    "Erklären Sie, wie Sie \"einen Fuß in die Tür bekommen\" haben.\n",
    "\n",
    "Wie lautet die Liste für `n = 2001`?\n",
    "\n",
    "\n",
    "\n",
    "Versuchen Sie es zunächst ohne Hilfe. Wie kann Ihnen Python dabei helfen? \n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    "![Spoiler Alert](https://imgs.xkcd.com/comics/spoiler_alert.png)\n",
    "([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    "Mein \"Fuß in der Tür\" war, dass ich von Hand eine Tabelle mit den Ergebnissen für die ersten `n` Zahlen gebaut habe:\n",
    "\n",
    "|  n | Liste     | Produkt |\n",
    "|----|-----------|---------|\n",
    "|  2 | 1 1       |       1 | \n",
    "|  3 | 1 2       |       3 | \n",
    "|  4 | 2 2       |       4 |\n",
    "|  5 | 2 3       |       6 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ergänzen Sie diese Tabelle von Hand. Dabei kann Ihnen eine Funktion helfen, die für eine gegebene Liste an Zahlen das Produkt und die Summe berechnet:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prodsum(zahlen):\n",
    "    prod = 1\n",
    "    summ = 0\n",
    "    for zahl in zahlen:\n",
    "        prod = prod * zahl\n",
    "        summ = summ + zahl\n",
    "    print(\"Produkt =\", prod, \"Summe =\", summ)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine Liste von Zahlen können wir erzeugen, indem wir die Zahlen durch Komma getrennt zwischen zwei Klammern schreiben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(2,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir können also `prodsum` so aufrufen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prodsum((2,3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testen Sie für jedes `n` mehrere Listen, bis Sie sich jeweils sicher sind, die mit dem größten Produkt gefunden zu haben.\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    "Ich habe mit Hilfe der Funktion die Tabelle bis `n=15` ergänzt bis ich mir sicher war, dass ich das Prinzip verstanden hatte. \n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    ".\n",
    "\n",
    "Sehen Sie jetzt ein Muster in der Tabelle? Die Produkte bestehen nur aus 3en und ggf. noch 2en oder 4en. Genauer:\n",
    "\n",
    "Beobachtung: \n",
    "- Ein Produkt aus möglichst vielen 3en ergibt das beste Ergebnis.\n",
    "- Falls es nicht ganz aufgeht, mit 2 oder 4 auffüllen.\n",
    "\n",
    "Erklärung:\n",
    "- Ob wir eine 4 oder zwei 2en nehmen, ist egal, da `2+2 = 4 = 2*2`.\n",
    "- Da `2+3=5` aber `2*3=6`, lohnt es sich nicht, größere Zahlen zu nehmen\n",
    "  (ebenso: `3+3=6` aber `3*3=9`) - das Produkt der kleinen Zahlen ist stets größer als ihre Summe\n",
    "\n",
    "Algorithmus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def produkt_summe(n):\n",
    "    \"\"\"Berechnet für gegebenes n>2 das Produkt derjenigen Liste von\n",
    "    Zahlen, deren Summe n ergibt und gleichzeitig die größte Liste mit\n",
    "    dieser Eigenschaft ist.\n",
    "    \n",
    "    Vorgehen: wiederholt 3 von n abziehen, bis der Rest kleiner oder \n",
    "    gleich 4 ist. (letzter Schritt klappt, weil 2+2=4=2*2)\n",
    "\n",
    "    \"\"\"\n",
    "    rest = n\n",
    "    prod = 1\n",
    "    zahlen = []\n",
    "    while rest > 4:\n",
    "        rest = rest - 3\n",
    "        prod = prod * 3\n",
    "        zahlen.append(3)\n",
    "    prod = prod * rest\n",
    "    zahlen.append(rest)\n",
    "    \n",
    "    print(\"*\".join([str(z) for z in zahlen]), \"=\", prod)\n",
    "    print(\"+\".join([str(z) for z in zahlen]), \"=\", sum(zahlen))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testen wir es einmal aus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "produkt_summe(14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das sollte auch die Zahl sein, die Sie für `n=14` oben in Ihrer Tabelle stehen haben. \n",
    "\n",
    "Die Funktion verwendet zwar ein paar neue Dinge, um eine schöne Ausgabe zu erzeugen, aber die wesentliche Funktionalität in der `while`-Schleife zur Berechnung des Produkts besteht nur aus Konstrukten, die wir schon kennengelernt haben. \n",
    "\n",
    "\n",
    "![I wrote 20 short programs in Python yesterday.  It was wonderful.  Perl, I'm leaving you.\"](https://imgs.xkcd.com/comics/python.png)\n",
    "\n",
    "([Python](https://xkcd.com/353/), Randall Munroe)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Speichern](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/floppy.png) Speichern Sie dieses Notebook, sodass Ihre Änderungen nicht verloren gehen (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/).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Smiley](https://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Smiling_smiley_yellow_simple.svg/240px-Smiling_smiley_yellow_simple.svg.png)\n",
    "\n",
    "Herzlichen Glückwunsch! Sie haben das 3. Kapitel geschafft. Weiter geht es in [3 Extra: Reguläre Ausdrücke](seminar03extra.ipynb)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}