Not logged in. · Lost password · Register

SpeedyGonzalez
Member since Jul 2017
103 posts
Subject: Lösungsvorschlag Klausur WS18/19: Aufgabe 2 (Dynamische Programmierung) Diskussion
Zur Diskussion der o.g. Aufgabe.

Der Lösungsvorschlag verlinkt hierhin :)

Lösungsvorschlag:
https://fsi.cs.fau.de/dw/pruefungen/bachelor/aud/loesungws18
This post was edited on 2019-06-12, 14:54 by SpeedyGonzalez.
VPROF
Member since Oct 2017
58 posts
Verstehe deine Lösung irgendwie nicht kannst du die mir mal erklären es ist ein bottom up beginnend bei der letzten Spalte und dann bist zur 1 Spalte vorarbeiten
VPROF
Member since Oct 2017
58 posts
So weit ich noch folgen kann ist mit dem iterstiven befüllen des Men durch die letzte Spalte aber danach hört es auf!
Wieso die ganzen if Bedingungen ?
SpeedyGonzalez
Member since Jul 2017
103 posts
In reply to post #2
Hab mal Kommentare in den Code geschrieben.

Die if-statements sind dazu da den grössten der angrenzenden Nachbarn in der Spalte rechts daneben zu finden.
Wenn man in der obersten Reihe ist, dann darf man aber nicht die darüber abchecken bzw. wenn man in der
untersten Reihe ist nicht die darunter, sonst hat man einen ArrayIndexOutOfBounds
VPROF
Member since Oct 2017
58 posts
Wieso betrachtet man nicht auch die Spalten ob die auserhalb sind?
Warum fängt man mit der letzten Zeile an anstatt mit der ersten
Warum vergleicht ,man das mit best ?
und das mit mem?


Finde die sehr komplex im vergleich der von letzten Jahren
z.b was bedeutet in der Aufgabenstellung die Pfeile ?
SpeedyGonzalez
Member since Jul 2017
103 posts
Die Spalten können nicht außerhalb sein, da das for-loop ja bei n-2 anfängt und bis 0 runterzählt. Dadurch ist der Bereich ja schon aufs Array beschränkt.

Du kannst auch bei der ersten Zeile anfangen und dann hochzählen.

Die Pfeile sind die der Grund warum man die Vergleiche anstellt. Wenn du dir die Angabe ansiehst und z.B. bei der 5 in der ersten Spalte anfängst, darfst du in der zweiten Spalte nur zur 2 (Pfeil nach oben), zur 0 (Pfeil nach rechts) oder zur 6 (Pfeil nach unten) springen. Also NICHT zur 3, da die Zelle sozusagen nicht mehr benachbart ist.
Du möchtest ja einen zusammenhängenden Pfad so wie in der Angabe schwarz eingefärbt, sonst müsste man ja in jeder Spalte nur das Maximum suchen und diese aufaddieren.

Wo wird im Code mit best verglichen?
Und was meinst du mit "und das mit mem?"?
VPROF
Member since Oct 2017
58 posts
meinte am Ende bei der for schleife
noch was was mich verwirrt was macht dort die for-Scheife?

Die Pfeile sind die der Grund warum man die Vergleiche anstellt. Wenn du dir die Angabe ansiehst und z.B. bei der 5 in der ersten Spalte anfängst, darfst du in der zweiten Spalte nur zur 2 (Pfeil nach oben), zur 0 (Pfeil nach rechts) oder zur 6 (Pfeil nach unten) springen. Also NICHT zur 3, da die Zelle sozusagen nicht mehr benachbart ist.
Du möchtest ja einen zusammenhängenden Pfad so wie in der Angabe schwarz eingefärbt, sonst müsste man ja in jeder Spalte nur das Maximum suchen und diese aufaddieren.

Ahh hab die Aufgabe so halb verstanden in der Klausur :/ aber jetzt :D muss mich wohl mehr mit dem Text auseinandersetzten
so kann man dann auch die a lösen also vom Prinzip also das mit draufaddieren

da das for-loop ja bei n-2 anfängt
da wir schon oben die letzte Spalte im mem gespeichert haben nimmt man den Vorgänger sozusagen
This post was edited on 2019-06-15, 00:47 by VPROF.
gabriel2029
Member since Nov 2018
50 posts
Noch kleine Sache, die mir zufällig aufgefallen ist: Vor der Schleife for(int r = row-1; r <= row+1; r++) { musst du b neu auf 0 initialisieren, ansonsten kann es vorkommen, wenn alle in dieser Schleife betrachteten Werte kleiner als dieses b sind, ein entsprechendes b aus einer anderen Spalte übernommen wird.

PS: Außerdem könntest du den Code bisschen schöner formatieren. Wenn die Tabulatoren einen Schritt durch die Rechnung machen, nehme lieber vier Leerzeichen statt eines Tabulator, ich finde das zumindest ästhetischer. Die meisten IDEs setzen inzwischen die Breite von Tabulatoren gleich vier Leerzeichen gleich, nur komische Editoren wie Nano machen 8 Leerzeichen daraus, was irgendwie merkwürdig aussieht, vor allem, wenn man Leerzeichen mit Tabulatoren vermischt. ;)
This post was edited on 2019-06-16, 15:20 by gabriel2029.
SpeedyGonzalez
Member since Jul 2017
103 posts
Danke, guter Punkt!
Bearbeitest du die Stelle gleich?
Es zeigt mir an, dass du die Seite gerade gesperrt hast.

Wie kann ich Tab im Texteingabefeld verwenden? Bei mir springt das sonst nur zum nächsten Eingabefenster.

In Eclipse verwende ich tab, aber wenn ich den Code copy & paste, zerschiesst es das Format und ich muss manuell mit der Leertaste nachhelfen
TOKAMAK
Member since Oct 2014
125 posts
Ich schlage folgendes als Alternative für die dynamische Programmierung vor:

for(int i = n-1; i >= 0; i--) {
    for(int j = 0; j < n; j++) {
        int max = 0;
        for(int r = j-1; j <= j+1; r++) {
            if(r < n && r >=0 && i+1 < n) {
               max = Math.max(max,  mem[r][i+1]);
            }
        }
        mem[j][i] = a[j][i] + max;
        best = Math.max(best, mem[j][i]);
    }
}
This post was edited 2 times, last on 2019-06-25, 21:15 by TOKAMAK.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen