Lösungen Dynamisches Programmieren

Aus ProgrammingWiki

Archivierte Version vom 2009-05-25T11:45:19+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Lösungen zu Fibonacci

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

public int fib(int n)
{
    if(n<2)
    {
        return 1;
    }
    else
    {
        return fib(n-1)+fib(n-2);
    }
}

<eval> System.out.println(""+fib(11)); </eval>

Fibonacci mit Memoizing

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));
        }
    }

<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 fib(n) nur fib(n-1) und fib(n-2) 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:

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;
}

<eval> System.out.println(fibIterativ(200)); </eval>

Zusatz: mit fast konstantem Speicheraufwand (und ohne Stackoverflow)

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=1+200)
    {
        erg = fibMemo2(i);
    }
    erg = fibMemo2(n);
    return erg;
}

<eval> System.out.println(optimizedFib(50000)); </eval>

Lösungen Dynamisches Programmieren

Inhaltsverzeichnis

Lösungen zu Fibonacci

Fibonacci ohne Memoizing

Fibonacci mit Memoizing

Iterative Lösung von Fibonacci

Zusatz: mit fast konstantem Speicheraufwand (und ohne Stackoverflow)

Suche