q1:java-rekursion

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Nächste Überarbeitung		 Vorhergehende Überarbeitung
q1:java-rekursion [2017/07/11 09:22] – [Aufgabe 3] admin03q1: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 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. 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: 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.  Diese Grafik soll mit einer rekursiven Methode erstellt werden. 
Zeile 157: Zeile 156:
 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. 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! 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 |}}
 +
  • /var/www/infowiki/data/attic/q1/java-rekursion.1499764945.txt.gz
  • Zuletzt geändert: 2017/07/11 09:22
  • von admin03