Autor |
Beitrag |
Shan22 (Shan22)
Mitglied Benutzername: Shan22
Nummer des Beitrags: 47 Registriert: 12-2003
| Veröffentlicht am Mittwoch, den 20. April, 2005 - 13:04: |
|
hallo ihr informatiker;) ich steig bei folgender aufgabe nicht wirklich durch bzw. bin noch fleißig am überlegen.. Beim Münzwechselsproblem sind zahlen a_1, a_2,...,a_m Element N mit a_1=1 und ein Betrag n Element N gegeben. Die m Zahlen a_1,..,a_m geben die Werte der Münzen einer Währung an. Das Problem besteht darin, die minimale Anzahl von diesen Münzen zu bestimmen, die den Betrag n darstellen. Folgender Algorithmus löst das Problem: a) erzeuge ein array b[0],...,b[n]. b) setze b[0]:= 0 please help me.. |
Murray (Murray)
Erfahrenes Mitglied Benutzername: Murray
Nummer des Beitrags: 244 Registriert: 10-2001
| Veröffentlicht am Mittwoch, den 20. April, 2005 - 16:18: |
|
Hallo Shan, ich bring erstmal ein Beispiel um dir das zu erlaeutern: Seien a_1 = 1 Cent, a_2 = 2 Cent, a_3 = 5 Cent, a_4 = 10 Cent (also m = 4 - meint es gibt 4 verschiedene Muenzen). Die Betraege der Muenzen sollten der Groesse nach sortiert werden (steht nicht explizit in der Aufgabe). Sei n = 8 Cent: Iniuitiv wuerde ich sagen 1+2+5 ist die kleinste Muenzanzahl. Wie kommt man da drauf: 8 / a_4 = 8 / 10 = 0 Rest 8 = 0 * 10 Cent und 8 Cent uebrig 8 / a_3 = 8 / 5 = 1 Rest 3 = 1 * 5 Cent und 3 Cent uebrig 3 / a_2 = 3 / 2 = 1 Rest 1 = 1 * 2 Cent und 1 Cent uebrig 1 / a_1 = 1 / 1 = 1 Rest 0 = 1 * 1 Cent und fertig Ich hoffe Du siehst das Prinzip, immer den Rest aus der Rechnung davor in die naechste einsetzen und mit dem groessten Betrag anfangen. Beispiele zum selbst probieren: 9 = 5 + 2*2 10 = 10 11 = 10 + 1 u.s.w. Onkel Murray (Beitrag nachträglich am 20., April. 2005 von murray editiert) |
Shan22 (Shan22)
Fortgeschrittenes Mitglied Benutzername: Shan22
Nummer des Beitrags: 51 Registriert: 12-2003
| Veröffentlicht am Dienstag, den 26. April, 2005 - 13:22: |
|
Ja, danke schön. |
|