1D-Arrays und Überläufe
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.
Übungsblatt 5 - Aufgabe 1
Wenn ich mir bei der Implementierung der dynamischen Programmierung als Datenstruktur ein 2D-Array verwende, dann funktioniert der main-Testfall korrekt. Wenn ich aber das Ganze mit einem 1D-Array implementiere, dann scheitert mein Testfall für 15 und 26 an einem Überlauf. Wodurch entsteht dieser Überlauf ausgerechnet bei 1D-Arrays? Für alle anderen Testfälle ist die Berechnung absolut korrekt.
Das ist komisch. Die Anzahl der Dimensionen sollte kein Unterschied darstellen. Hast du in beiden Faellen den gleichen Datentyp verwendet?
Wenn du Memoization machst, und die rekursive Funktion hat x veraenderliche Parameter ist aber auch sinnvoll, dass die Tabelle x Dimensionen bekommt. Manchmal kann man eine (oder mehr) Dimensionen einsparen, wenn man Bottom-Up DP macht - das ist aber fuer den Moment nicht gefordert.
Ja, ich habe den gleichen Datentyp verwendet und eigentlich müsste die Aufgabe auch funktionieren (auch in 1D). Allerdings entsteht da das folgende Ergebnis:
anzahlWuerzMoeglichkeiten(1, 1) == 1, should be: 1
anzahlWuerzMoeglichkeiten(1, 3) == 1, should be: 1
anzahlWuerzMoeglichkeiten(2, 2) == 1, should be: 1
anzahlWuerzMoeglichkeiten(2, 3) == 3, should be: 3
anzahlWuerzMoeglichkeiten(2, 4) == 7, should be: 7
anzahlWuerzMoeglichkeiten(98, 99) == 4851, should be: 4851
anzahlWuerzMoeglichkeiten(15, 26) == -7468333765277204120, should be: 90449030191104000
Es wird wohl irgendwo ein Überlauf entstehen, aber beim 2D-Array entsteht alles so, wie es sein soll.
Erklaer mal, wie du aus dem 2D-Array ein eindimensionales machst, vielleicht faellt dann der Fehler auf.
Zunächst habe ich einfach die erste Reihe (mit zusätzlichen Nullen) genommen und dann habe ich rückwärts analog zum Pascalschen Dreieck die Koeffizienten so lange verändert, bis ich die nötige Reihe hatte.
OK, grundsaetzlich gibt es eine Loesungsvariante, die so aehnlich ist. Allerdings ist es wesentlich einfacher, die Loesung mit einem 2D-Array zu berechnen.
Wenn du moechtest, kann ich mir aber deinen 1D-Code nach der Abgabe mal ansehen und schauen, ob ich den Fehler sehe.
Ich habe die Abgabe per PN geschickt.
Was willst da eigenlich mit dem 1D Array erreichen? Ich hab nämlich immer das Gefühl, dass du beide Indizes brauchst, um bei dieser Rekursion voranzukommen (oder du schummelst mit Hashtables).
@ AnNyan:
Ich will mit einem 1D-Array weniger Speicherplatzverbrauch bei gleicher Laufzeit und Streutabellen sagen mir nichts.