GeldWechseln.java (Lösung)

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.

GeldWechseln.java (Lösung)
Hallo miteinander,

wäre es möglich wenn mir jemand seinen Code zu dieser Aufgabe schicken könnte? Wäre ihm/ihr sehr verbunden!
Falls dies Möglich ist, dann schicke mir einfach eine PN. Danke!


Wichtiger als irgendwelchen Code aus irgendwelchen Quellen, der mehr oder weniger korrekt und mehr oder weniger lesbar ist, wäre es besser, man diskutiert hier den Kern der Aufgabenstellung:

Die Eingabe [m]int m, int b[/m] lässt die „Problemgröße“ erkennen: „m.length x b“ (sei im Folgenden n := m.length die Anzahl der Münzarten)

Rekursion funktioniert dadurch, dass man das Problem „verkleinert“ und das/die verkleinerte(n) Problem(e) eben rekursiv löst.
Wie „verkleinert“ man „n x b“? Z.B. so:
Entweder man

  • verkleinert b, indem man von b die n-te Münze abzieht (also b teilweise mit der n-ten Münze „auszahlt“) => Rekursion mit (b - m[n-1], n) - macht aber mit allen Münzen weiter!
    oder
  • verkleinert n, indem man die n-te Münze „weglässt“ => Rekursion mit (b, n-1) - macht aber mit dem vollen Betrag weiter!
    („entweder/oder“ klingt hier exklusiv - natürlich muss man beide Optionen untersuchen => Backtracking!)

Rekursion benötigt auch immer Basisfälle - welche könnten hier auftreten?

  • b ist negativ (Betrag nicht auszahlbar) oder n ist nicht positiv (keine Münzarten mehr verfügbar) => keine Lösung => Abbruch/Rückkehr aus Rekursion
  • b ist 0 => Lösung gefunden => Lösung vermerken und Rückkehr aus Rekursion

Backtracking ist nur eine schöne Anwendung für Rekursion. I.d.R. benötigt sie noch Verwaltungsinformation über den bisher durchlaufenen Pfad.
=> Für GeldWechseln bedeutet das ein zusätzliches Feld, in dem nach und nach die verwendeten Münzen abgelegt (try) oder wieder entfernt (backtrack) werden. Sobald der erfolgreiche Basisfall eintritt, muss man die aufgesammelte Spur irgendwo ver"merke"n (sic!)…

Ich hoffe, das hilft…
Geht in die TÜen und RÜen und lasst euch das Induktions-/Rekursionsprinzip nochmal und auch an anderen Beispielen erläutern, bis das Prinzip offensichtlich wird! Danach werdet ihr Rekursion „lieben“! :wink:

1 Like

das habe ich übersehen :open_mouth:

VIELEN DANK ! Ich hatte nicht mit einer ausführlichen Antwort gerechnet, deswegen die Frage nach Quellcode.

:smiley: :wink:

Hat sehr geholfen.