Aufgabe 6.4

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.

Aufgabe 6.4
Hu,

irgendjemand schon durch? Kleinen Denkansatz fuer die “moeglich_dp”? :wink:

Aber nicht zuviel verraten, nicht dass ich noch was vom WE hätte…

  • tobi

Ich hab nen tollen Denkansatz: Wart auf die Tafelübung, da wird das angesprochen und das Tolle ist, du hast noch was vom WE :wink:


dann müsst ich aber aufhören drüber nachzudenken und das geht jetzt nichtmehr :frowning:


ups, dp, den moeglich_rec kopieren, und jeden neu erstellten wert in eine tabelle schreiben, und gegebenfalls diesen anstelle der funktion benutzen


hm, wenns das schon war, danke für den tip. hast du mal spasseshalber die performanz getestet, was man spart?

jetzt fehlt nur noch die iteration von der es ja in der vorlesung hieß, sie ist nicht (leicht) umzusetzen Oo

  • tobi

edit: hm rein gefühlsmäßig braucht dp ca. 2x solang wie rec? ;> da stimmt was nich :confused:


also nur mal so ohne rücksicht auf meinen rechner…

um mir n 10er in handelsüblichen münzen rauszugeben braucht er rec: 8,2s und dp: 9,8s bis er weiß wieviel möglichkeiten er hat (btw 321335886 ?!)

wollte die zeit eigtl für 80€ stoppen, aber da hatte ich nach 5mins kein bock mehr zu warten.


Also ich hab hier 9,2 sec rec und 1 ms für dp
Und wens interresiert für 80€ mit handelsüblichen Münzen gibt es 245703657594081 Möglichkeiten (dp: 11ms rec: keiner Lust)


Hallo,

die Standardrekursion sollte schonmal fertig sein, für den Rest sollte ich erstmal lernen worum es sich überhaupt handelt :wink:

… hier einige Ausgaben mit handelsüblichen Münzen:

fuer 4: 3
fuer 5: 4
fuer 25: 68
fuer 125: 10564
fuer 250: 200187
fuer 456: 3863970
fuer 725: 49083860
fuer 1000: 321335886
fuer 1250: 1241743732

Zumindest für einen 10er stimmts ja schonmal mit holde überein :slight_smile:

Für den 10er knappe 9,1s … powered by 2,4GHz AMD. [edit: na ein paar [Ko:de]-Optimierungen komme ich auf 7,4s]
Für 1250 Cent braucht er schon knapp 38sek, und bei 2000 bricht die VM nach 10min ab :wink:

Damit ist wohl schonmal klar, was man durch diese Aufgabe lernen soll …

Für 80 versagt er in einem Schwall von Fehlermeldungen …

Wie kann man sich diese Werte ( Zeit ) eigentlich am leichtesten genau ausspucken lassen ?


also ich bekomme für die standard rekursion ab 1000 andere ausgaben wie du mit handelsüblichen muenzen (hast du die 10€ muenze dabei? ich glaub nich weil bei 1000 bekomme ich genau eine möglichkeit mehr).


Ich hab “handelsüblich” jetzt mal also ohne 10€ Münze verstanden. Mein Wert für 80€ ist ohne 10€ Münzen berechnet. mit sind es ein paar mehr (391766789799369 in 29ms)


uhm, dein dp ist n bissl schneller als meins :frowning: glaub ich hab wohl zu wenig tabelleneinträge…

edit: hmm ok, man sollte nich nur einser in [0][x] und [y][0] setzen Oo jetzt passts, nur die großen zahlen schmeißen noch fehler :confused:


nuja ich glaub meine iterative variante is noch nich so der hit. aber die großen zahlen in dp werfen bei mir genauso fehler, wenn ich über die 6000 gehe mit unserer münzstückelung dann kratzt alles ab


hm die _rec zickt bei mir ab 8425 und die _dp ab 6554, was ich auch nich so ganz nachvollziehen kann, weils ja quasi die selben methoden sind.

btw hassandor, wenn ich das array gleich im konstruktor aufbau und in der iterativen einfach das feld ausgeb merkt das euer Testdings? :wink:

public long moeglich_iter(final int betrag, final int muenzart) {
return matrix[muenzart][betrag];
}

sieht doch gut aus und is auch verdammt schnell :wink:


meine dp kackt genau bei 5361 ab (mit der 10€ muenze dabei).

ja so nen cheat hab ich bei iter auch:


public long moeglich_iter(final int betrag, final int muenzart) {
	
	for (int i = 0; i <= muenzart; i++) {
	    for (int j = 0; j <= betrag; j++) {
		tabelle[i][j] = moeglich_dp(j, i);
	    }
	}
	return tabelle[muenzart][betrag];
    }

:wink:


Ich weiß ja nicht was ihr macht, aber wenn ich meins mit int[] muenzen = {1,2,5,10,20,50,100,200,1000}; int betrag = MAXBETRAG; int muenzart = muenzen.length-1; laufen lasse, komme ich auf diese schöne zahl: 45183583593471216, und da kackt nichts ab ^^

ah, und zeitlich irgendwo im ms Bereich, soll heissen, ich klick auf run, und das erge bnis steht da (ohne rec)


Du sollst das iterativ lösen, nicht recursiv. wenn du die recursive version aufrust, ist das nimmer iterativ :wink:

holde: nein das script merkt das nicht, aber evtl der Tutor. :wink:

Absurd-Mind: thumpsup


Puffe hoch?


daumen hoch, deine Zahl gefällt mir


hehe, das war mir schon klar :wink:

Ich wollt nur auf diesen Umstand hinweisen:

thump = Puff
thumb = Daumen