Rekursiv programmieren unter Java?

Question

Ich soll unter Java einen rekursiven Algorithmus entwickeln, welcher mir für beliebige Beträge unter 10Euro die Menge der Möglichkeiten ausgibt, wie man diesen Betrag mit allen zur Verfügung stehenden Münzen( also 1ct, 2ct,..., 2Euro) auszahlen kann. Ich probiere jetzt schon seit Tagen daran herum aber es kommt nichts Richtiges dabei raus, weil ich auch nicht weiß, wie der entsprechende Baum dazu aussehen müsste. Deswegen hoffe ich, dass mir hier vielleicht jemand einen Tip geben kann. Ich bin für jede Hilfe sehr dankbar.

Anonym · Accepted Answer

Erst die mathematische Formel/den Baum entwickeln, dann programmieren. Das hört sich so an als ob du es anders herum probiert hast.

Du brauchst also sämtliche in der Kombinatorik vorhandenen Möglichkeiten? Es wäre schonmal ratsam alles als Centbeträge zu betrachten, so jedenfalls mein gedanklicher Ansatz. Ich knobbel rum, wenn ich was finde schreib ich das nieder.

//

Okay, ein Stück weiter:

Da es unter 10 Euro sein soll, hast du bis zu 999 ct. Wenn du die 100terer Beträge in Münzen aufteilst, dann die zehner, dann die Einer-Stellen sollte das vom Ansatz her vorangehen. Ist nur eine Vorabüberlegung, bin mir dessen nicht sicher.

Beispiel 2€:

2€<=>200ct

<=>2*100ct (2*1€)

<=>4*50ct (4*0,50€)

<=>10*20ct (10*0,20€)

<=>20*10ct (20*0,10€)

<=>40*5ct (40*0,05€)

<=>100*2ct(100*0,02€)

<=>200*1ct(200*0,01€)

10zehner:

26 cent<=> 20 + 6 cent => 20 Cent

20 cent <=>1*20ct (0,20€)

<=> 2*10ct (0,20€)

<=>4*5ct (0,20€)

<=>10*2ct (0,20€)

<=>20*1ct (0,20€)

6 Cent (Problem tritt auf)<=> 3*2ct <=>6*1ct<=>5*1ct + 1ct extra.

Folglich muss man auf Restbeträge bei den Münzen achten:

0,06/0,05=1,2 nicht 1 (über 1 > 1 Münze: 5 cent, 0,05*(1,20-1)=0,01 = 1ct extra). Soweit zu meinem bisherigen Ansatz.

Etwas abweichend:

7,25€ <=> 7€ und 0,25€.

x1= 7€/2€(Münze)= 7€/2€ = 3,5.

|x1|=3.

3*2(Münzwert) = 6 Euro.

0,5*2(Münzwert) = 1 €

Ergibt drei 2 Euro Münzen plus 1 Euro Münze.

Aufteilen der zwei Euro/ein-Euro-Münzen separat ist irgendwie schlecht um die anderen Möglichkeiten zu bekommen - darum die Überlegung mit den Centbeträgen.

0,25€ <=> 1 Stelle nach dem Komma:

20 Ct

0,20ct/0,50 ct <=> 0,4 Absolutwert 0 (keine Münze, verwerfen, Ebene tiefer gehen)

0,20ct/0,20 ct = 1 (Treffer, 1 Münze)

0,05ct (wieder durch Münzwert teilen, Treffer >=1 : Münze, Rest ermitteln)

Keine Ahnung ob dir die Gedankengänge weiterhelfen...

Mario · Answer

Ich versuch mal die Idee zu skizzieren. Du nimmst den grÃ¶ÃtmÃ¶glichsten Wert, der in den Betrag reinpasst. Den ziehst du von dem Betrag ab und berechnest den Rest. Wie berechnest du den Rest? NatÃ¼rlcih genau so wie oben beschrieben - nehme den grÃ¶ÃtmÃ¶glichsten Wert. Die Abbruchbedingung lautet: Betrag = 0.

Das sollte klappen, denke ich. Hoffe ich konnte dir helfen.

Rekursiv programmieren unter Java?

2 Antworten