05_theorie.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "dd6e07d1",
   "metadata": {},
   "source": [
    "# Schleifen und Rekursion\n",
    "\n",
    "#### Patrick Schnider, Marcel Lüthi</br>Departement Mathematik und Informatik, Universität Basel"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42f08f48",
   "metadata": {},
   "source": [
    "In diesem Notebook brauchen wir erneut Turtlegrafik.\n",
    "Führen Sie bitte die folgenden zwei Zeilen aus, damit Sie die Turtlegrafik-Kommandos zur Verfügung haben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e086a64",
   "metadata": {},
   "outputs": [],
   "source": [
    "%mavenRepo shapemodelling-repo https://shapemodelling.cs.unibas.ch/repo/\n",
    "%maven ch.unibas.informatik:jturtle:0.7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "033713da",
   "metadata": {},
   "outputs": [],
   "source": [
    "import static ch.unibas.informatik.jturtle.TurtleCommands.*;\n",
    "import java.awt.Color;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b422fb6",
   "metadata": {},
   "source": [
    "### Teil 1: Schleifen\n",
    "\n",
    "In dieser Woche haben wir Schleifen als Alternative zu Rekursion kennengelernt. \n",
    "Im ersten Teil dieses Notebooks werden wir die verschiedenen Varianten von Schleifen anschauen und diskutieren, welche Schleifenart wir für welche Anwendung einsetzen. Zuerst greifen wir auf die Aufgabe von letzter Woche zurück, nämlich das Zeichnen eines n-Ecks.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "32b32000",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Drawing {\n",
    "    \n",
    "    // Rekursive Lösung von letzter Woche\n",
    "    public static void drawPolygon(int n, int length) {\n",
    "       drawSideAndTurn(n, 360.0 / n, length);\n",
    "    }\n",
    "    \n",
    "    // Hilfsmethode für die rekursive Lösung von letzter Woche\n",
    "    public static void drawSideAndTurn(int n, double angle, double length) {\n",
    "        if (n == 0) {\n",
    "            // do nothing\n",
    "        } else {\n",
    "            forward(length);\n",
    "            turnLeft(angle);\n",
    "            drawSideAndTurn(n -1, angle, length);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    public static void drawPolygonForLoop(int n, double length) {\n",
    "        \n",
    "        // Implementation missing\n",
    "    }\n",
    "\n",
    "    public static void drawPolygonWhileLoop(int n, double length) {\n",
    "        \n",
    "        // Implementation missing\n",
    "    }\n",
    "\n",
    "    public static void drawPolygonDoWhileLoop(int n, double length) {\n",
    "        \n",
    "        // Implementation missing\n",
    "    }\n",
    "\n",
    "    \n",
    "    public static void main(String[] args) {\n",
    "        home();\n",
    "        reset();\n",
    "        clear();\n",
    "        penDown();\n",
    "        drawPolygon(5, 10);\n",
    "        display(drawing());\n",
    "    }\n",
    "}\n",
    "\n",
    "Drawing.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc5ce8ac",
   "metadata": {},
   "source": [
    "#### Miniübungen\n",
    "\n",
    "* Implementieren Sie die Funktionalität zum Zeichnen eines n-Ecks, indem Sie einmal eine `for`-Schleife, einmal eine `while`-Schleife und einmal eine `do-while`-Schleife nutzen.\n",
    "* Welche Lösung würden Sie bevorzugen?\n",
    "* Sind alle Lösungen korrekt?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00b387da",
   "metadata": {},
   "source": [
    "#### Spirale\n",
    "\n",
    "Als nächstes möchten wir eine Spirale zeichnen. Dies machen wir, indem wir uns in einer Schleife jeweils um denselben Winkel drehen und dann ein Stück vorwärts gehen. Das Stück, welches wir vorwärts gehen, wird in jedem Schritt etwas grösser. Wir beginnen mit einer initialen Schrittlänge, und brechen ab, wenn wir eine gewisse Schrittlänge erreicht haben. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7f3e753f",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Drawing {\n",
    "    \n",
    "    public static void drawSpiral(double initialLength, double finalLength) {\n",
    "        penDown();\n",
    "       \n",
    "        // Implementation missing\n",
    "    }\n",
    "    \n",
    "   \n",
    "    public static void drawSpiralRec(double currentLength, double finalLength) {\n",
    "        penDown();\n",
    "       \n",
    "        // Für Schnelle\n",
    "    }\n",
    "    \n",
    "    public static void main(String[] args) {\n",
    "        home();\n",
    "        reset();\n",
    "        penSize(1);\n",
    "        clear();\n",
    "        penDown();\n",
    "        \n",
    "        drawSpiralRec(1, 50);\n",
    "        display(drawing());\n",
    "    }\n",
    "}\n",
    "\n",
    "Drawing.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be35c90f",
   "metadata": {},
   "source": [
    "#### Miniübung \n",
    "\n",
    "* Welche Schleife nehmen Sie hier bevorzugt?\n",
    "* Implementieren Sie die Methode `drawSpiral`.\n",
    "* Für ganz Schnelle: Können Sie die Methode auch rekursiv schreiben?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55d872a6",
   "metadata": {},
   "source": [
    "### Eingabe mittels Scanner"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5dda90db",
   "metadata": {},
   "source": [
    "Zum Schluss zeigen wir noch ein Beispiel, bei dem die do-While Schleife die bevorzugte Wahl ist. \n",
    "Diese Schleife ist immer dann nützlich, wenn wir eine Aktion mindestens einmal durchführen müssen, bevor wir Entscheiden können, ob ein weiterer Durchlauf gemacht werden soll. Das typische Beispiel dafür ist das Lesen von Daten aus einer Datei oder der Tastatur. Dies wird in folgendem Beispiel gezeigt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1cdfdd04",
   "metadata": {},
   "outputs": [],
   "source": [
    "import java.util.Scanner;  // Import the Scanner class\n",
    "\n",
    "class Input {\n",
    "    \n",
    "    public static String askForUsername() {\n",
    "        Scanner myObj = new Scanner(System.in);  // Create a Scanner object\n",
    "        System.out.println(\"Enter your name\");\n",
    "        String input = myObj.nextLine(); // programm stops until the key [Enter] is pressed\n",
    "        return input;\n",
    "    }\n",
    "\n",
    "    public static void main(String[] args) {\n",
    "        String userName;\n",
    "        do {\n",
    "            userName = askForUsername();\n",
    "        } while (userName.equals(\"\"));\n",
    "        System.out.println(\"Username is: \" + userName);\n",
    "    }\n",
    "}\n",
    "\n",
    "Input.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d0d08ec",
   "metadata": {},
   "source": [
    "#### Miniübung \n",
    "\n",
    "* Schreiben Sie dieses Beispiel so um, dass eine while-Schleife verwendet wird. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f13fce8-d955-46f8-a333-e43cdc2e6a00",
   "metadata": {},
   "outputs": [],
   "source": [
    "import java.util.Scanner;  // Import the Scanner class\n",
    "\n",
    "class Input {\n",
    "    \n",
    "    public static String askForUsername() {\n",
    "        Scanner myObj = new Scanner(System.in);  // Create a Scanner object\n",
    "        System.out.println(\"Enter your name\");\n",
    "        String input = myObj.nextLine(); // programm stops until the key [Enter] is pressed\n",
    "        return input;\n",
    "    }\n",
    "\n",
    "    public static void main(String[] args) {\n",
    "        \n",
    "        // Implementation missing\n",
    "    }\n",
    "}\n",
    "\n",
    "Input.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dde8b4e7",
   "metadata": {},
   "source": [
    "### Teil 2: Rekursion\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8b84735",
   "metadata": {},
   "source": [
    "Angenommen Sie wollen eine Methode schreiben, die die Zahlen von $m$ bis $n$ aufsummiert und das Resultat zurückgibt. Mit einer `for`-Schleife ist diese Aufgabe sehr einfach zu lösen (siehe Methode `sumNumbers` in Zelle unten). Dasselbe können wir aber auch mittels Rekursion machen. Der Schlüssel zur Lösung gibt die folgende Einsicht\n",
    "\n",
    "- Die Summe der Zahlen von $m$ bis $n$ ist gleich $m$ plus der Summe von $m+1$ bis $n$, oder in Formeln\n",
    "$ \\sum_{i=m}^n i = m + \\sum_{i=m+1}^n i$\n",
    "\n",
    "#### Miniübung\n",
    "\n",
    "* Was wäre das Abbruchkriterium für die Rekursion?\n",
    "* Implementieren Sie diese Strategie."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f8739755",
   "metadata": {},
   "outputs": [],
   "source": [
    "class SumExample {\n",
    "\n",
    "    public static int sumNumbersLoop(int from, int to) {\n",
    "        \n",
    "        // Implementation missing\n",
    "    }\n",
    "\n",
    "    public static int sumNumbersRec(int from, int to) {\n",
    "        \n",
    "        // Implementation missing\n",
    "    }\n",
    "\n",
    "\n",
    "    public static void main(String[] args) {\n",
    "        int sum = sumNumbersRec(0, 100);\n",
    "        System.out.println(\"sum of the numbers 0 to 100: \" +sum);\n",
    "    }\n",
    "}\n",
    "SumExample.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8fbea15c",
   "metadata": {},
   "source": [
    "### Die Ästhetik der Informatik"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "baf44624",
   "metadata": {},
   "source": [
    "Inzwischen können Sie auch schon die Zeichnung des Baums verstehen, welche wir Ihnen am Anfang der Vorlesung gezeigt haben. Diese nutzt einfach die Idee, dass ein Baum wieder aus kleinen Teilbäumen besteht. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "57fe37dd",
   "metadata": {},
   "outputs": [],
   "source": [
    "import java.util.Random;\n",
    "class RandomTree {\n",
    "    \n",
    "    static Random random = new Random();\n",
    "    \n",
    "    static void randomTree(double length, double minLength, int thickness, int minThickness, double minAngle, double maxAngle, double minShrink, double maxShrink) {\n",
    "        if (length < minLength || thickness < minThickness) {\n",
    "            return;\n",
    "        } else {\n",
    "             double angle1 = minAngle + random.nextDouble() * (maxAngle - minAngle);\n",
    "             double angle2 = minAngle + random.nextDouble() * (maxAngle - minAngle);\n",
    "             double shrink1 = minShrink + random.nextDouble() * (maxShrink - minShrink);\n",
    "             double shrink2 = minShrink + random.nextDouble() * (maxShrink - minShrink);\n",
    "             penSize(thickness);\n",
    "             forward(length);\n",
    "             turnRight(angle1);\n",
    "             randomTree(length*shrink1, minLength, (int) (thickness * shrink1),  minThickness, minAngle, maxAngle, minShrink, maxShrink);\n",
    "             turnLeft(angle1 + angle2);         \n",
    "             randomTree(length*shrink2, minLength, (int) (thickness * shrink2), minThickness, minAngle, maxAngle, minShrink, maxShrink);\n",
    "             turnRight(angle2);\n",
    "             penSize(thickness);\n",
    "             backward(length);\n",
    "  \n",
    "        }\n",
    "    }\n",
    "    \n",
    "    static void drawTree(double length, double minLength, int thickness, int minThickness, double minAngle, double maxAngle, double minShrink, double maxShrink) {\n",
    "        clear();\n",
    "        reset();\n",
    "        penUp();\n",
    "        turnRight(180);\n",
    "        forward(100);\n",
    "        turnRight(180);\n",
    "        penColor(java.awt.Color.BLACK);\n",
    "        penDown();\n",
    "        RandomTree.randomTree(length, minLength, thickness, minThickness, minAngle, maxAngle, minShrink, maxShrink);\n",
    "        display(drawing());\n",
    "    }\n",
    "    \n",
    "    \n",
    "     public static void main(String[] args) {\n",
    "        RandomTree.drawTree(20, 2, 12, 1, 10, 30, 0.75, 1.0);\n",
    "    }\n",
    "};\n",
    "RandomTree.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0df21288",
   "metadata": {},
   "source": [
    "#### Miniübungen\n",
    "\n",
    "Versuchen Sie folgendes herauszufinden\n",
    "* Was macht `random.nextDouble`?\n",
    "    * Was passiert, wenn Sie stattdessen jeweils 0.5 einsetzen?\n",
    "* Was ist das Abbruchkriterium?\n",
    "* Wie sieht ein Teilbaum aus?\n",
    "* Wieviele und welche rekursive Aufrufe werden jeweils gemacht?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c7651785",
   "metadata": {},
   "outputs": [],
   "source": [
    "import java.util.Random;\n",
    "new Random().nextDouble()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f0724f4",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java [conda env:ijava]",
   "language": "java",
   "name": "conda-env-ijava-java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "17.0.3-internal+0-adhoc..src"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}