Lösungen Dynamisches Programmieren

Wiki-Quelltext dieser Seite.

<language>Java</language>
=Lösungen zu Fibonacci=

Die ersten 2 Lösungen sind bereits aus der Vorlesung bekannt, werden hier aber der Vollständigkeit wegen nochmal aufgeführt.

==Fibonacci ohne Memoizing==

<code>
public int fib(int n)
{
    if(n<2)
    {
        return 1;
    }
    else
    {
        return fib(n-1)+fib(n-2);
    }
}
</code>
<eval>
System.out.println(""+fib(11));
</eval>

==Fibonacci mit Memoizing==

<code>
private java.util.HashMap memoliste = new java.util.HashMap();
 memoliste.put(0, java.math.BigInteger.ONE);
 memoliste.put(1, java.math.BigInteger.ONE);

    private java.math.BigInteger fibMemo(Integer n)
    {
        if(memoliste.containsKey(n))
        {
            return memoliste.get(n);
        }
        else
        {
            java.math.BigInteger fib1 = fibMemo(n - 1);
            memoliste.put(n-1, fib1);
            java.math.BigInteger fib2 = fibMemo(n - 2);
            memoliste.put(n-2,fib2);
            return (fib1.add(fib2));
        }
    }
</code>
<eval>
System.out.println(""+fibMemo(250));
</eval>

==Iterative Lösung von Fibonacci==

Wie bereits erwähnt, ist ein wenig Denkaufwand erforderlich um auf die iterative Lösung zu kommen. Dabei wird der Wert Top-Down mit Hilfe einer for-Schleife berechnet. Da zum berechnen von <math>fib(n)</math> nur <math>fib(n-1)</math> und <math>fib(n-2)</math> benötigt wird, müssen auch nur diese Werte zwischen gespeichert werden. Der aufmerksame Leser wird sich an das Rucksackproblem erinnern in dem wir genauso verfahren sind.

Mithilfe dieser Informationen kommt man nun auf folgendes Ergebnis:

<code>
java.math.BigInteger fibIterativ(int n)
{
    java.math.BigInteger erg = java.math.BigInteger.ONE;
    java.math.BigInteger save1 = java.math.BigInteger.ZERO;
    java.math.BigInteger save2 = java.math.BigInteger.ZERO;
    for(int i = 0; i < n; i++)
    {
        save2 = new java.math.BigInteger(save1.toString());//es müssen neue Werte erzeugt werden, sonst wird nur Referenz übergeben
        save1 = new java.math.BigInteger(erg.toString());
        erg = save1.add(save2);
    }
    return erg;
}
</code>
<eval>
System.out.println(fibIterativ(200));
</eval>

==Zusatz: mit fast konstantem Speicheraufwand (und ohne Stackoverflow)==

Bei der Berechnung sehr großer Fibonacci-Zahlen wird von Java ziemlich schnell ein StackOverflowError geworfen. Das liegt natürlich an der Rekursonstiefe. Bei sehr großen <math>n</math> ist diese natürlich ein Problem, da alle Aufrufe bis zur 'Berechnung' von <math>fib(0)</math> im Stack verbleiben müssen, damit diese terminieren können.

Umgehen können wir dieses Problem, indem wir nur eine bestimmte Rekursionstiefe zulassen. Das erreichen wir mit Hilfe einer for-Schleife, die in 200er Schritten zählt und in jedem Durchlauf wird <math>fibMemo(i)</math> (i ist der Schleifenzähler) berechnet. Das geschieht bis <math>i</math> größer werden würde als <math>n</math>. Danach muss nur noch <math>fibMemo(n)</math> berechnet werden. Somit erreichen wir eine maximale Rekursionstiefe von 200 Aufrufen, weil der vorher berechnet Wert natürlich noch in der memoliste gespeichert ist.

Zusätzlich können wir den Speicheraufwand (fast) konstant halten indem wir, wie bei der iterativen Variante nur <math>fib(n-1)</math> und <math>fib(n-2)</math> speichern. Das erreichen wir indem wir nach der Berechnung einfach <math>fib(n-3)</math> wieder aus der memoliste entfernen.

Somit erhalten wir folgende 2 Methoden:

<code>
private java.math.BigInteger fibMemo2(Integer n)
    {
        if(memoliste.containsKey(n))
        {
            return memoliste.get(n);
        }
        else
        {
            java.math.BigInteger fib1 = fibMemo2(n - 1);
            memoliste.put(n-1, fib1);
            java.math.BigInteger fib2 = fibMemo2(n - 2);
            memoliste.put(n-2,fib2);
            memoliste.remove(n-3);
            return (fib1.add(fib2));
        }
    }
private java.math.BigInteger optimizedFib(int n)
{
    java.math.BigInteger erg = java.math.BigInteger.ZERO;
    for(int i = 1;i < n;i=i+200)
    {
        erg = fibMemo2(i);
    }
    erg = fibMemo2(n);
    return erg;
}
</code>
<eval>
System.out.println(optimizedFib(50000));
</eval>