Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
ef_informatik:sorting_csharp [2022-03-14 17:55] – [Aufgabe 1: Fibonacci nicht dynamisch] scaef_informatik:sorting_csharp [2022-03-14 20:26] (aktuell) – sca
Zeile 671: Zeile 671:
  
 ==== Aufgabe 1: Fibonacci nicht dynamisch ==== ==== Aufgabe 1: Fibonacci nicht dynamisch ====
 +
 +=== Teil I ===
  
 In einer früheren Aufgabe hast du bereits die Glieder Fibonacci-Folge //rekursiv// berechnet. Öffne das entsprechende Projekt und bestimme, das höchste Folgenglied, welches du (resp. dein Computer) in vernünftiger Zeit berechnen kann. In einer früheren Aufgabe hast du bereits die Glieder Fibonacci-Folge //rekursiv// berechnet. Öffne das entsprechende Projekt und bestimme, das höchste Folgenglied, welches du (resp. dein Computer) in vernünftiger Zeit berechnen kann.
Zeile 687: Zeile 689:
 ++++ ++++
 </nodisp> </nodisp>
 +
 +=== Teil II ===
  
 Erweitere deinen Code so um, dass dieser dir für die vorgegebene Zahl $n$ bestimmt, wie viele rekursive Funktionsaufrufe Erweitere deinen Code so um, dass dieser dir für die vorgegebene Zahl $n$ bestimmt, wie viele rekursive Funktionsaufrufe
Zeile 693: Zeile 697:
  
 `Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = (Fibonacci(1) + Fibonacci(0)) + Fibonacci(1)` `Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = (Fibonacci(1) + Fibonacci(0)) + Fibonacci(1)`
 +
 +<nodisp 1>
 +++++Tipps|
 +Definiere einen Counter als eine Art globale Variable, also eine Variable, die //ausserhalb// der Main-Methode definiert wird. Jedesmal, wenn die Fibonacci-Funktion aufgerufen wird, kann dann dieser Counter um 1 erhöht werden.
 +++++
 +</nodisp>
 +
 +Bestimme für alle Werte $n$ von $1$ bis zum maximalen Wert, wie viele Funktionsaufrufe es jeweils gibt. Wie genau entwickelt sich diese Anzahl Funktionsaufrufe mit steigendem $n$?
 +
 +<nodisp 2>
 +++++Lösung|
 +<code csharp>
 +public static long fibonacciCounter = 0;
 +
 +public static int FibonacciWithCounter(int n)
 +{
 +    fibonacciCounter++;
 +    if (n <= 1) { return 1; }
 +    return FibonacciWithCounter(n - 1) + FibonacciWithCounter(n - 2);
 +}
 +
 +public static long[] FibonacciWithCounterWrapper(int n)
 +{
 +    fibonacciCounter = 0;
 +    int fib = FibonacciWithCounter(n);
 +    return new long[] { (long)fib, fibonacciCounter };
 +}
 +
 +public static void Main(string[] args)
 +{
 +    List<long> fibonacciCountList = new List<long>();
 +
 +    for (int n = 0; n < 30; n++)
 +    {
 +        long[] result = FibonacciWithCounterWrapper(n);
 +        fibonacciCountList.Add(result[1]);
 +        Console.WriteLine("n = " + n + ", count: " + result[1]);
 +    }
 +
 +    for (int i = 0; i < fibonacciCountList.Count-1; i++)
 +    {
 +        Console.WriteLine((double)fibonacciCountList[i + 1] / fibonacciCountList[i]);
 +    }
 +}
 +</code>
 +Findet, dass Verhältnis von $\frac{a_{n+1}}{a_n}$ immer etwa 1.6 ist. D.h. **exponentielles Wachstum**.
 +++++
 +</nodisp>
 +
 +=== Teil 3 ===
 +
 +Erkläre nun genau, warum diese maximale Folgenglied so tief ist. Wo genau liegt das Problem? Hast du Ideen, wie man dieses umgehen könnte?
 +
 +<nodisp 2>
 +++++Lösung|
 +Siehe //Theorie// in der nächsten Aufgabe.
 +++++
 +</nodisp>
 +
 +
 +==== Aufgabe 2: Fibonacci dynamisch ====
 +
 +<nodisp 1>
 +++++Theorie|
 +Das Problem im Code der vorherigen Aufgabe ist, dass die Anzahl Funktionsaufrufe exponentiell steigt. Dadurch ist die Anzahl rekursiver Funktionsaufrufe bereits für Zahlen wie $n=42$ sehr hoch (und zwar $433'494'437$). Dies liegt daran, dass die Fibonacci-Funktion immer wieder für die gleiche Zahl aufgerufen wird. Zum Beispiel wird in der Berechnung für `Fibonacci(42)` insgesamt $102'334'155$ `Fibonacci(3)` berechnet. Das ist nicht sehr effizient!
 +
 +Lösung: Verhindere, dass die ein Folgenglied mehrfach berechnet wird. Dazu müssen die bereits berechneten Folgenglieder in einer Liste gespeichert werden. Anstelle, dass ein Folgenglied erneut berechnet wird, liest man den Wert aus der Liste aus.
 +
 +Diese Art der Programmierung wird **dynamische Programmierung** genannt. Das Speichern der Zwischenresultate wird **Memoisation** genannt.
 +++++
 +</nodisp>
 +
 +=== Teil I ===
 +
 +Implementiere nun die rekursive Fibonacci Funktion dynamisch. Das heisst, die Zwischenresultate sollen in einer Liste oder einem Array gespeichert und wieder verwendet werden (Memoisation). Wie weit kannst du nun Folgenglieder der Fibonacci-Folge berechnen?
 +
 +=== Teil II ===
 +
 +Bestimme nun wieder, wie viele rekursive Funktionsaufrufe nötig sind. Vergleiche die dynamische mit der vorherigen, nicht dynamischen Implementierung.
 +
 +<nodisp 2>
 +++++Lösung|
 +Anzahl rekursive Funktionsaufrufe ist nun **linear** in $n$, genauer: $2n - 1$. Für $n=42$ sind es damit $83$ (dynamisch). Stellt man es den über 400 Millionen Funktionsaufrufe vom nicht dynamischen Code gegenüber, so sieht man, dass dies eine enorme Steigerung der Effizient ist! 
 +++++
 +</nodisp>
  
  • ef_informatik/sorting_csharp.1647280559.txt.gz
  • Zuletzt geändert: 2022-03-14 17:55
  • von sca