Rekursives Problem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:37 Fr 18.05.2007 | | Autor: | Leader |
Hallo.
Wir sollen ein recht kniffliges Programm schreiben, das rekursiv arbeiten soll. Folgendes soll das Programm machen:
Gegeben ist eine gewisse Anzahl an Geldwerten (z. B. 1 Cent, 2 Cent, 5 Cent und 10 Cent) und von jeden dieser Geldwerte gibt es eine bestimmte Anzahl an Geldstücken (also es gibt z. B. 3 1-Cent-Münzen, 5 2-Cent-Münzen, 4 5-Cent-Münzen und eine 10-Cent-Münze).
Die Frage ist nun, ob ein bestimmter Wert mittels dieser Geldstücke gebildet werden kann. Das heißt, der Benutzer gibt in dem Programm zunächst die Münzen ein, die er besitzt und anschließend einen Geldbetrag. Das Programm ermittelt, ob dieser Betrag mit den Münzen gebildet werden kann oder nicht.
Um dies zu ermöglichen, und um alle möglichen Kombinationen, mit denen der Betrag gebildet werden kann, ausgeben zu können, muss also jede Kombination durchlaufen werden.
Nun ist aber das Problem, dass die genaue Anzahl der Geldtypen dynamisch ist. Das heißt, der Benutzer kann zum Beispiel beim Programmstart 1-Cent, 2-Cent und 5-Cent-Stücke festlegen, aber ebensogut auch 7-Cent, 12-Cent, 20-Cent und 50-Cent Stücke. Die genaue Anzahl an Geldwerten ist also unterschiedlich. Damit kann ich das Problem nicht mit geschachtelten For-Schleifen lösen, wie ich es sonst gemacht hätte.
Iterativ hätte ich das Problem wie folgt gelöst, wenn die Anzahl der Geldwerte immer gleich ist:
Beispiel (iterativ): Es gibt 1-Cent, 2-Cent und 5-Cent-Stücke, also 3 Gelttypen (und von jedem Geldtyp gibt es eine best. Anzahl).
For X = 0 To Anzahl_1Cent
For Y = 0 To Anzahl_2Cent
For Z = 0 To Anzahl_5Cent
Betrag = 1*x + 2*Y + 5*Z
If Betrag = Sollwert Then Print "Kombination gefunden" + X,Y,Z
Next
Next
Next
So wäre es iterativ. Ich suche nun einen rekursiven Algorithmus, der dieses Problem umsetzt. Das heißt, es soll ein Algorithmus sein, der äquivalent zu meinem iterativen Algorithmus mit den For-Schleifen ist, jedoch mit der Ausnahme, dass die Anzahl der Geldtypen jedes mal anders sein kann.
Kann mir da jemand helfen? Ich hab bisher keine brauchbaren Lösungen zu Stande bekommen, man hat mir aber mal gesagt, dass Rekursion u. a. auch dafür genutzt wird, wenn man über die Schleifentiefe nicht genau Bescheid weiß.
Freundliche Grüße,
Leader.
|
|
| |
|
Du hast a Geldstücke vom Wert A, b Geldstücke vom Wert B, c Geldstücke vom Wert C, d Geldstücke vom Wert D etc., und dein Zielwert ist X (der Betrag, der aus den Geldstücken gebildet werden soll)
Dann ist die Anzahl der Probier-Versuche maximal (a+1)*(b+1)*(c+1)*(d+1)...
Dann durchläufst du die Schleifen jeweils von Null bis a, b, c etc., so verschachtelt, wie du es ja schon gemacht hast, und prüfst, ob
X=a*A+b*B+c*C+d*D....
Um den Prozess zu beschleunigen, könntest du die Schleifen abbrechen, wenn
X<a*A+b*B+c*C+d*D....
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:09 Sa 19.05.2007 | | Autor: | Leader |
Hallo rabilein,
das Problem ist aber, dass nicht genau bekannt ist, wie viele Geldtypen es gibt, das heißt, wie viele For-Schleifen gebraucht werden. Das hängt davon ab, was der Benutzer für Geldstücke eingibt. Mal braucht man nur 2 For-Schleifen, mal 5 oder noch mehr.
Das ganze soll also rekursiv realisiert werden.
Vielleicht geht es mit nur eine For-Schleife, die sich immer wieder aufruft (Rekursion), solange, bis das letzte Geldstück erreicht ist. Irgendwie in der Art muss es wohl sein.
Ich finde es nur irgendwie schwer, sich in die ganze Rekursion hineinzudenken. Denn das mit den verschachtelten For-Schleifen find ich eine sehr gute Herangehensweise, nur wie man es rekursiv macht weiß ich nicht.
LG, Leader.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:49 Sa 19.05.2007 | | Autor: | piet.t |
Hallo,
so ganz spontan würde ich es etwa so angehen:
Man baut eine Funktion f(), die folgende Parameter entgegennimmt:
1.) den Geldbetrag b
2.) Eine Liste mit Art der Geldstücke g und deren jeweilige Anzahl z(g)
Der Rückgabewert soll anzeigen, ob der Betrag mit den Münzen gebildet werden kann (also wahr/falsch oder so).
Die Funktion könnte so arbeiten:
Man geht die Geldstück-Arten in einer Schleife durch. Wenn [mm] g_i=b [/mm] und [mm] z(g_i)>= [/mm] 1, dann kann man b ja mit einer [mm] g_i-Münze [/mm] bilden und gibt "wahr" zurück.
Ist [mm] g_i=0, [/mm] dann ruft man f() erneut auf, wobei die Parameter wie folgt abgeändert werden:
1.) Als Betrag verwendet man [mm] b-g_i
[/mm]
2.) In der Liste ersetzt man [mm] z(g_i) [/mm] durch [mm] z(g_i)-1
[/mm]
Kommt "wahr" zurück, dann weiss man wieder, dass der ursprüngliche Gesamtbetrag durch die gegebenen Münzen gebildet werden kann und gibt wiederum "wahr" zurück; erhält man "falsch", sokann man den gegebenen Betrag nicht unter Verwendung einer [mm] g_i-Münze [/mm] bilden und setzt die Schleife fort (vielleicht klappt es ja mit einer anderen Münze)
Ist die Schleife durchlaufen, ohne dass irgendwann "wahr" zurückgekommen wäre, dann kann der Betrag nicht mit den gegebenen Münzen gebildet werden und man gibt "falsch" zurück.
So, das war jetzt eine ganze Menge Text, ich hoffe ich konnte einigermaßen rüberbringen, was ich mir gedacht habe...
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:24 So 20.05.2007 | | Autor: | Leader |
Okay, danke für die Antwort.
Ich werde es mal probieren.
Grüße,
Leader.
|
|
|
| |
|
Hier ist mein Vorschlag:
g sei die Anzahl der unterschiedlichen Geldstücke
w(1), w(2) ... w(g) sei der jeweilige Wert der Geldstücke
a(1), a(2) ... a(g) sei die größtmögliche Anzahl der Geldstücke zu dem jeweiligen Wert
t(1), t(2) ... t(g) seien Teilmengen wobei t(1) [mm] \le [/mm] a(1) ... t(g) [mm] \le [/mm] a(g)
Z sei der Zielwert der mit den Geldstücken zusammengesetzt werden soll
Nun muss man ähnlich wie in unserem Dezimalsystem zahlen und zwar von
t(1)=0, t(2)=0 ... t(g)=0 bis
t(1)=a(1), t(2)=a(2) ... t(g)=a(g)
t(1) ist quasi der Einer und sobald t(1)=a(1) , wird t(1)=0 gesetzt und t(2) wird um Eins erhöht (wie beim zählen).
Und dann muss nach jedem Zählvorgang geprüft werden, ob
Z = w(1)*t(1) + w(2)*t(2) +... + w(g)*t(g)
g ist ja eine Variable, die irgendwo gespeichert ist. Also kann man für diese Rechenvorgang eine Additionsschleife g mal durchlaufen.
|
|
|
|
