Ja, das verwunderliche ist nur das bei mir die Methode dp bis ca 65000 (fünfundsechzigtausend) also rund 10 mal soweit wie bei anderen!
Der einzige unterschied de rmir spontan einfällt ist, dass ich das array andersherum speicher: als array[betrag][münzart] ← kann aber kaum glauben das es daran liegen soll!
werd mir heut mal den Optimierungstip von meim Kumpel angucken, der hatte es ja erst genauso wie ich (array im Konstruktor mit unknown 
), dann hat er was kleines geändert jetz läufts bei ihm auch OBWOHL die tabelle im konstruktor erstellt wird, dann lass ichs uns wissen worans lag
nuja hab jetz intelligenterweise mein urprogramm im cip getestet (also tabellenaufbau im konstruktor, alle felder auf UNKNOWN gesetzt), herrlicherweise gehts da bis 15000 und gibt den schönen 4xxxxxxxxxxxxxx wert aus. yeah muss ich also nur noch die iterative kacke schreiben, dann wär praxis ma fertig.
erkenntnis 2:
Wenn man in moeglich_dp die beiden summanden im rekursiven Aufruf vertauscht gehts auch 
(der ultimative tip) jetz funzts auch bei mir bis in diese höhen von 65k hinauf.
jo witzigerweise gehn dann sowohl _rec als auch _dp auf jedenfall bis MAXBETRAG. danke für den tip 
- tobi
Das geht wirklich.
Will mir einer sagen warum?
Hallo,
vielen Dank für die Antwort; ich hab das ganze jetzt mit einer API von Java realisiert:
System.nanoTime.
Damit komme ich dann auf folgendes:
Muenzwerte: 200 100 50 20 10 5 2 1
Anzahl Wechselmoeglichkeiten mit moeglich_rec:
fuer 1000: 321335886
Anzahl Wechselmoeglichkeiten mit moeglich_iter:
fuer 1000: 321335886
Zeit fuer 1000Cent die # der Moeglichkeiten _rec auszurechnen:
7331350492ns
Zeit fuer 1000Cent die # der Moeglichkeiten _iter auszurechnen:
3235607nsDas heißt von 7.3sek bei normaler Rekursion, auf unter 1s mit iter.
Und auch der maxbetrag funktioniert bei meiner Iteration … wahsinnig schnell.
Ich muss sagen, eine sehr schöne Aufgabe. Macht Spaß zu sehen was effizient ist, und nicht nur effektiv
Gut, jetzt noch mein _dp … hm
eigentlich lags auf der hand, bei dp wird die aufrufstiefe dadurch wesentlich geringer gehalten. Und das andere Problem wird sein, dass die Stackgröße OSabhängig unterschiedlich groß ist.
BTW: Iter hab ich jetz auch fertig und somit die komplette Praxis 
fehlt nur noch die 1c und der andere kackbeweis -.-
Mal ne Frage zur Iteration… Also mir käme da nur die Idee, die Tabelle von unten nach oben zu befüllen bis man an dem Feld angekommen ist, das eigentlich ausgewertet werden soll. Klingt aber nicht so optimal. Hat jemand nen kleinen Denkanstoß?
In der Aufgabenstellung steht dass wir in der Vorlesung gelernt haben wie man dynamische Rekursive Methoden in iterative umwandelt. Ehrlich? Ich hab nichts in den Folien gefunden.
Danke schonmal ^^
Herzlichen Glückwunsch du hast dir deinen eigenen Denkanstoß gegeben… iterativ: von unten aufbauen bis zum feld wo man hin will
So siehts mit 1000 und MAXBETRAG bei mir aus…
— Tests für die Münzen 1, 2, 5, 10, 50, 100, 200 —
Starte Rekursion (Betrag: 1000)…
Fertig: 12025 ms
(Moeglichkeiten: 321335886)
Starte dynamische Rekursion (Betrag: 1000)…
Fertig: 1 ms
(Moeglichkeiten: 321335886)
Starte dynamische Iteration (Betrag: 1000)…
Fertig: 2 ms
(Moeglichkeiten: 321335886)
Starte dynamische Rekursion (Betrag: 15000)…
Fertig: 1 ms
(Moeglichkeiten: 18538303277268276)
Starte dynamische Iteration (Betrag: 15000)…
Fertig: 4 ms
(Moeglichkeiten: 18538303277268276)
Edit: Mit der 10€ Münze und MAXBETRAG: 45183583593471216
Mit 10€ Münze und 1000 genau eine Möglichkeit mehr…
Noch ne kurze Frage: Im übergebenem Münzen-int-Array darf keine 1 drin sein oder?
Steht nicht in der Aufgabenstellung, dass muenzen[0] auf jedenfall 1 Cent sein muss?
- tobi
Da steht dass die Funktion muenzwert(int muenzart) bei muenzart==0 immer 1 zurückgeben muss…
So hab ich mir das gedacht:
public int muenzwert(final int muenzart) {
if (muenzart < 0) {
return 0;
} else if(muenzart > coins.length) {
return MAXBETRAG + 1;
} else if (muenzart == 0) {
return 1;
} else {
return coins[muenzart - 1];
}
}coins ist das übergebene Münz-Array… ist bei mir z.B. {2, 5, 10, 20, 50, 100, 200}
Hi ihr, zur algemienen aufklärung der Verwirrung:
in dem Feld sollte an erster stelle eine 1 stehen, also z.b. {1, 2, 5, 10, 20, …}
wenn das Feld so aussihet {4711, 2, 5, 10, 20, …} soll es wie das oberere behandelt werden.
ja musste mein code extra nochmal umschreiben weil mein kumpel meinte das hast du ihm so gemailt, ich hatte es davor so gelöst, dass ich die übergebenen münzen packe um eins nach rechts verschieb und ne 1 davorklemm
Wenn ich das mit nur mit 2 Münzen testen (z.B. 1 und 2) dann krieg ich mit hohen Beträgen immernoch nen StackOverflow… inwieweit müssen wir denn darauf achten?
ich denke wenns nen overflow gibt bevor long überläuft is net so gut
EDIT: habs bei mir auch mal getestet, gibt bei mir auch Overflow in dem Fall denk ich, dass auch hier wieder die Aufruftiefe zu tief wird, es geht halt nicht alles, aber ich denk standardmünzen bis 15k basst scho
also der herr hassandor meinte zu mir, dass die stackoverflows egal sind.
und somit (auch wenns durchs vertauschen besser wurde) sind sie es mir auch
- tobi
ob irgendwann mal ne angabe kommt, in der man nicht 10 mal extra nachfragen muss zur praxis ^^