Gierige Methoden (Wechselgeld 2)
|
|||
|
|
|
|
Wir beschreiben die gieirige Straegie nun algorithmisch. Wir gehen davon aus, dass
n Münzwerte w(i), i=1,...,n, vorhanden sind, die absteigend geordnet sind ( w(1) > w(2) ... > w(n-1) > w(n) ), und dass ein Betrag von b auszuzahlen ist.
|
|
Gieriger Algorithmus für das Rückgeldproblem |
für i=1 bis n bestimme die Zahl z(i) so, dass z(i)*w(i) <= b, aber (z(i)+1)*w(i) > b {gierig: nimm Münze i so oft es geht} setze b = b-z(i)*w(i) {neuer Wechselbetrag} |
 |
Führt diese gierige Strategie immer zum Ziel?
Hier sind zwei eher exotische Münzsätze. Der eine war in Deutschland 1932 tatsächlich so im Umlauf, der andere (  Utopia) ist theoretisch interessant.
|
 |
|
gierig ist nicht immer einfach |
Die Beispiele haben gezeigt: Es ist nicht selbstverständlich, dass eine gierige Strategie immer funktioniert. Wenn sie funktioniert, muss man begründen, warum.
Für die Wechselgeldaufgabe findest du hier die (doch erstaunlich komplexe) |
| Seite 4/10 |