Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- q1:java-rekursion [2017/07/11 09:19] – [Realisierung von Quicksort] admin03
+++ q1:java-rekursion [2017/12/04 08:51] (aktuell) – admin03
@@ Zeile 1: / Zeile 1: @@
 In Kapitel 9 wurde die Berechnung der Fakultät als Beispiel für die Einführung von Methoden benutzt. Die eigentliche Berechnung erfolgte damals mit Hilfe einer Schleife. Die Berechnung der Fakultät lässt sich jedoch auch anders auffassen: Fakultät von 20 ist nichts anderes als 20- mal Fakultät von 19, Fakultät von 19 ist 19-mal Fakultät von 18, usw. Eine solche Definition setzt allerdings voraus, dass man mindestens einen konkreten Wert der Fakultät kennt (z.B. ist 1!=1). Zusammengefasst mit der Abkürzung fak für Fakultät gilt also
+$$fak(n)=n\cdot fak(n-1)$$ und $$fak(1)=1.$$
-$$fak(n)=n\cdot fak(n-1) und fak(1)=1.$$
 Eine solche Definition einer Funktion bezeichnet man als rekursiv („rückbezüglich“). Viele Programmiersprachen erlauben die unmittelbare Umsetzung einer solchen Funktionsdefinition. Bei speziellen Sprachen wie PROLOG gibt es überhaupt keine Schleifen, diese müssen dann immer durch rekursive Funktionen nachgebildet werden.
@@ Zeile 47: / Zeile 46: @@
-{{ :q1:fakultaetablauf.jpg?direct&400 |}}
+{{ :q1:fakultaetablauf.jpg?direct&300 |}}
 Als komplexeres Problem sollen die sog. „Kinderkreise“ betrachtet werden. Jeder Kreis hat dabei links und rechts zwei Kinder, diese haben wiederum Kinder, usw. Wenn eine gewisse Größe unterschritten wird, gibt es keine Kinder mehr:
-{{ :q1:kinderkreise.png?direct&400 |}}
+{{ :q1:kinderkreise.png?direct&600 |}}
 Diese Grafik soll mit einer rekursiven Methode erstellt werden.
@@ Zeile 143: / Zeile 142: @@
 {{ :q1:sortiere123.png?direct&800 |}}
+====== Aufgabe ======
+===== Aufgabe 1=====
+Löse das Problem der Summe der Zahlen von 1 bis 100 („Strafarbeit des kleinen Gauss“, vgl. Kapitel 3) rekursiv.
+===== Aufgabe 2=====
+Eine Folge von Kommazahlen ist folgendermaßen rekursiv definiert:
+a1 = 1 und  . Bestimme zunächst per Hand a2, a3 und a4.
+Schreibe ein Java-Programm mit einer Methode, die die n-te Zahl in dieser Folge rekursiv berechnet. Das Hauptprogramm soll dann a100 ausgeben.
+===== Aufgabe 3=====
+Die Fibonacci-Folge, deren Elemente auch Fibonacci-Zahlen genannt werden, beginnt mit den Werten1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,    Jede Zahl ist die Summe der beiden Vorgänger. Leonardo von Pisa, genannt Fibonacci, stellte in seinem 1202 erschienen Buch Il liber abbaci die berühmte Kaninchenaufgabe, die in heutiger Formulierung so lautet: Wir nehmen an:
+  * Jedes Kaninchenpaar wird im Alter von 2 Monaten gebärfähig.
+  * Jedes Kaninchenpaar bringt (ab dem 3. Monat) jeden Monat ein neues Paar zu Welt und
+  * alle Kaninchen leben ewig (oder wenigstens lange genug).
+Beginnen wir nun mit einem frisch geborenen Kaninchenpaar. Wie viele Kaninchenpaare, die von diesem einen Paar abstammen, leben im n-ten Monat? Wie man leicht nachprüft, ergeben sich hierbei die Fibonacci-Zahlen.
+Erstelle ein Java-Programm, das die n-te Fibonaccizahl rekursiv berechnet. Schreibe zur Übung auch ein Programm, das klassisch mit einer Schleife rechnet. Ein interessanter Test zeigt, dass schon fibo(50), rekursiv berechnet, eine sehr lange Rechenzeit braucht, während dieselbe Zahl iterativ berechnet praktisch sofort erscheint. Erkläre dieses Phänomen!
+===== Aufgabe 4=====
+Erkläre die Funktionsweise des folgenden Konsolen-Programms:
+<code JAVA>
+public class test
+{
+  static void p(int x)
+  {
+    if(x>0)
+      p(x-1);
+    System.out.println(x);
+  }
+  public static void main(String[] args) {
+    p(4);
+  }
+}
+</code>
+===== Aufgabe 5 =====
+Welche Ausgabe erzeugt folgende Methode, wenn man sie mit p(5) aufruft?
+<code JAVA>
+static int p(int x)
+  {
+    if(x==0)
+      return 1;
+    else
+    {
+      int y = p(x-1);
+      System.out.println(x+y);
+      return y + 1;
+    }
+  }
+</code>
+===== Aufgabe 6 =====
+Der Turm von Hanoi ist ein Denkspiel, das aus drei Stäben und einem Turm besteht. Der Turm ist aus n Scheiben aufgebaut, die zu Beginn auf dem ersten Stab aufgefädelt sind, so dass die Scheibengröße von unten nach oben abnimmt:Ziel des Spiels ist es, den Turm vom ersten auf den zweiten Stab zu bewegen, wobei immer nur eine Scheibe auf einmal bewegt werden und nie eine größere auf eine kleinere gelegt werden darf.
+{{ :q1:tuermevonhanoi.png?direct&400 |}}
+Für einen Turm der Höhe 3 könnte eine Lösung wie folgt aussehen:
+Veranschauliche diese Lösung zunächst zeichnerisch!
+{{ :q1:ausgabe12.png?direct&400 |}}
+Finde Lösungen für Türme der Höhe 4 und 5 und notiere sie wie in a). Wie viele Züge sind jeweils nötig? Was hat dieses Problem mit Rekursion zu tun?
+Schreibe ein rekursives Java-Programm, das eine Lösung für einen Turm der Höhe n ausgeben kann!
+===== Aufgabe 7 =====
+Es gibt viele weitere grafische Beispiele zur Rekursion. Ein  anspruchsvolles Beispiel ist der Baum des Pythagoras (Bundeswettbewerb Informatik 1986). Finde heraus, wie er erzeugt wird, und programmiere ihn mit Java!
+{{ :q1:fraktal.jpg?direct&400 |}}