Musterloesung Klausur WS 2014 Aufgabe 5b Dynamische Programmierung

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Musterloesung Klausur WS 2014 Aufgabe 5b Dynamische Programmierung
Kann diese Loesung stimmen? im letzten else wird ja wieder rekursion verwendet im letzten? Oder steh ich grad aufn schlauch… komm da irgendwie nicht weiter, hat einer ne Idee?
am ende wurde er ja wieder bei jedem rekursionsschirtt ne neue tabelle anlegen…

Edit: Also mein ansatz waere das man i=j=0 startet, und die formel vom angang irgendwie in eine iterative version umbauen muss, aber da haeng ich fest, vllt hat eine rne idee? oder ist der untere Code tatsaechlich die Loesung?

Musterloesung:

long bDP(int n, int m) {
    long[][] mem = new long[n + 1][m + 1];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if((n<m) || (m == 0 && n != 0)) {
                mem[i][j] = 0;
            } else if(n == m) {
                mem[i][j] = 1;
            } else {
                mem[i][j] = (3*(n-1)*b(n-1,m) + m*b(n-1,m-1))/n;
            }
        }
    }
    return mem[n][m];
}
3

aber nach diese rekursive Aufruf , sie rufen kein bDP auf hier … sie rufen b … und das wahrscheinlich auch nicht stimmt …

ja die Lösung ist nicht richtig , das ist garantiert , weil keine Abfrage gibt , ob ein Wert schon berechnet ist .

muss immer abgefragt wird , ob den Wert schon mal berechnet , und wenn ja , dann den gespeicherte zurückgeben …

wenn nicht dann neu berechnen .

wenn jemand die Lösung korrigiert wird ganz nett :D:D …

4

Die Lösung ist fast richtig, man müsste nur an 2 Stellen ne Kleinigkeit abändern…

5

ich versuch mal mein Glück…


long bDP(int n, int m) {
    long[][] mem = new long[n + 1][m + 1];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(mem[i][j] < 1){
                if((n<m) || (m == 0 && n != 0)) {
                    mem[i][j] = 0;
                } else if(n == m) {
                    mem[i][j] = 1;
                } else {
                    mem[i][j] = (3*(n-1)*bDP(n-1,m) + m*bDP(n-1,m-1))/n;
                }
            }
        }
    }
    return mem[n][m];
}

Wobei ich wegen der Rekursion immer noch skeptisch bin, in so gut wie allen anderen aufgaben wird die Tabelle zum zwischenspeichern, VOR der MEthode angelegt, so können alles rekursiven aufrufe auf diese zugreifen, in diesem Code, wäre beim nächsten rekursiven aufrufen von dPD() ja das zwischenergebniss weg… oder seh ich das falsch`???

6

Das siehst du alles absolut richtig, das Problem ist, dass deine Lösung nach wie vor nicht iterativ ist.
Überleg mal, in welcher Reihenfolge die (Zwischen-)Ergebnisse b(i,j) bzw. mem[i][j] berechnet werden.

Das hier

if(mem[i][j] < 1){

sollte überflüssig sein, da jedes Paar (i,j) nur einmal pro Methodenaufruf auftaucht und die Tabelle Methoden-lokal ist.
Die zweite Stelle ist also wo anders;)

7

so? also n und m durch i j getauscht. Zaehlen wuerd ich von unten nach oben, da ja immer die vorgaenger benoetigt werden und die ersten Vorgaenger ja durch n = m = 1 gesetzt werden.

long bDP(int n, int m) {
    long[][] mem = new long[n + 1][m + 1];
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
                if((i<j) || (j == 0 && i != 0)) {
                    mem[i][j] = 0;
                } else if(i == j) {
                    mem[i][j] = 1;
                } else {
                    mem[i][j] = (3*(i-1)*mem[i-1],[j] + j*mem[i-1][j-1])/i;
                }
        
        }
    }
    return mem[n][m];
}
8

Sieht richtig aus.