Aus ProgrammingWiki

Autoren:
Markus Ullrich - simaullr@stud.hs-zigr.de
Norbert Baum   - sinobaum@stud.hs-zigr.de

Inhaltsverzeichnis 1 Lösungen zu Fibonacci 1.1 Fibonacci ohne Memoizing 1.2 Fibonacci mit Memoizing 1.3 Iterative Lösung von Fibonacci 1.4 Zusatz: mit fast konstantem Speicheraufwand (und ohne Stackoverflow) 2 Lösungen zur Matrizenkettenmultiplikation

Lösungen zu Fibonacci

Die ersten 2 Lösungen sind bereits aus dem Abschnitt Dynamisches_Programmieren 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); } }

System.out.println(""+fib(11));

ausführen

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

System.out.println(""+fibMemo(250));

ausführen

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

System.out.println(fibIterativ(200));

ausführen

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 ist diese ein Problem, da alle Aufrufe bis zur 'Berechnung' von 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 mit dem Schleifenzähler , die in 200er Schritten zählt und in jedem Durchlauf berechnet. Das geschieht bis größer werden würde als . Danach muss nur noch berechnet werden. Somit erreichen wir eine maximale Rekursionstiefe von 200 Aufrufen, weil der vorher berechnete Wert natürlich noch in der memoliste gespeichert ist und einfach nur noch abgerufen werden muss.

Zusätzlich können wir den Speicheraufwand (fast) konstant halten indem wir, wie bei der iterativen Variante nur und speichern. Das erreichen wir indem wir nach der Berechnung einfach wieder aus der memoliste entfernen.

Somit erhalten wir folgende 2 Methoden:

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

System.out.println(optimizedFib(50000));

ausführen

Lösungen zur Matrizenkettenmultiplikation

Wir verwenden wieder generateMatrix(int zeilen, int spalten) um uns Matrizen beliebiger Größe zu generieren und die bekannte memoListe zum speichern von Teillösungen. Danach bleibt uns nur noch die rekursive Vorschrift in eine rekursive Prozedur umzuformen, was sich als recht trivial erweißt. Lediglich die Abfrage, ob der berechnete Wert schon in der memoListe vorhanden ist, muss noch zusätzlich in die Prozedur eingebaut werden. Zusätzlich verwenden wir die kListe, in der die Stellen gespeichert werden, an denen sich die Kette bei der optimalen Klammerung zwischen und aufspaltet. Damit kann nach der Berechnung die optimale Klammerung mit einer einfachen Methode ausgegeben werden.

private void printMatrix(int[][] mat) { for(int i = 0; i < mat.length;i++) { String out = "("; for(int j = 0; j < mat[0].length;j++) { out+=mat[i][j]+" "; } System.out.println(out+")"); } } private int[][] generateMatrix(int rows, int columns, int numbersize) { java.util.Random random = new java.util.Random(); int[][] back = new int[rows][columns]; for(int i = 0 ; i < rows ; i++) { for(int j = 0; j < columns ; j++) { back[i][j] = random.nextInt(numbersize); } } return back; }

private java.util.List matrizen = new java.util.LinkedList(); private java.util.HashMap memoListe = new java.util.HashMap(); private java.util.HashMap kListe = new java.util.HashMap(); matrizen.add(generateMatrix(4,5,10)); matrizen.add(generateMatrix(5,2,10)); matrizen.add(generateMatrix(2,7,10)); matrizen.add(generateMatrix(7,3,10)); matrizen.add(generateMatrix(3,9,10)); //hier können weitere Matrizen hinzugefügt werden //dabei bitte auf Kompatibilität achten for(int i = 0; i < matrizen.size(); i++) { memoListe.put(i, new HashMap()); kListe.put(i, new HashMap()); for(int j = 0; j < matrizen.size();j++) { memoListe.get(i).put(j, Integer.MAX_VALUE);//initialisieren der memoListe mit sehr großen Werten } } rekursiveAufrufe = 0; private int minMult(int i,int j) { if(memoListe.get(i).get(j)<Integer.MAX_VALUE) { return memoListe.get(i).get(j); } rekursiveAufrufe++; if(i==j) { return 0; } else { int back = Integer.MAX_VALUE; for(int k = i ; k < j ; k++) { int temp = minMult(i,k) + minMult(k+1,j) + (matrizen.get(i).length * matrizen.get(j)[0].length * matrizen.get(k)[0].length); back = java.lang.Math.min(back, temp); if(back<memoListe.get(i).get(j)) { memoListe.get(i).remove(j); memoListe.get(i).put(j, back); kListe.get(i).put(j, k); } } return back; } } private String optimaleKlammerung(int i,int j)//Ausgabe der optimalen Klammerung als String { if(i==j) { return "A"+i; } else { return "(" + optimaleKlammerung(i,kListe.get(i).get(j)) + "x" + optimaleKlammerung(kListe.get(i).get(j)+1,j) + ")"; } }

System.out.println("Minimale Anzahl skalarer Operationen: " + minMult(0,matrizen.size()-1)); System.out.println(optimaleKlammerung(0,matrizen.size()-1));

ausführen