Lösungen Dynamisches Programmieren

Aus ProgrammingWiki

Archivierte Version vom 2009-05-25T11:27:31+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);
            return (fib1.add(fib2));
        }
    }

<eval> System.out.println(""+fibMemo(250)); </eval>

Iterative Lösung von Fibonacci

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>

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

Suche