Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

münzwechselproblem

ZahlReich - Mathematik Hausaufgabenhilfe » Universitäts-Niveau » Mathematik für Informatiker » münzwechselproblem « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Shan22 (Shan22)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Mitglied
Benutzername: Shan22

Nummer des Beitrags: 47
Registriert: 12-2003
Veröffentlicht am Mittwoch, den 20. April, 2005 - 13:04:   Beitrag drucken

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..
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Murray (Murray)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Murray

Nummer des Beitrags: 244
Registriert: 10-2001
Veröffentlicht am Mittwoch, den 20. April, 2005 - 16:18:   Beitrag drucken

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)
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Shan22 (Shan22)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Fortgeschrittenes Mitglied
Benutzername: Shan22

Nummer des Beitrags: 51
Registriert: 12-2003
Veröffentlicht am Dienstag, den 26. April, 2005 - 13:22:   Beitrag drucken

Ja, danke schön.

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page