Seite 1 von 4 1234 LetzteLetzte
Ergebnis 1 bis 15 von 55

Thema: [PDW 9] Geldwechsel

  1. #1
    Moderator
    Registriert seit
    Jun 2001
    Beiträge
    1.327
    Renommee
    846

    [PDW 9] Geldwechsel

    Problem der Doppelwoche Nr. 9: Geldwechsel

    Im täglichen Leben müssen wir immer wieder Geldbeträge durch Münzen darstellen. Damit das Portemonaie nicht zu voll wird, sollten dies immer möglichst wenig Münzen sein. Es soll ein Algorithmus entworfen werden, der eine solche Stückelung berechnet.

    Gegeben sind n verschiedene Münzwerte a_i mit ganzzahligen Werten sowie ein Geldbetrag C.
    Es ist a_1 = 1 und a_i < a_(i+1) für alle 1 <= i < n.
    Berechne, welche Münzen wie oft ausgewählt werden müssen, um den Betrag mit möglichst wenig Münzen darzustellen.


    Lösungen und Lösungsansätze dürfen ab Montag, dem 21. Juni 2004 gepostet werden. Beachtet bitte auch die Richtlinien zum Problem der Doppelwoche.

    Viel Spass beim Programmieren.
    Geändert von DarkTom (02.11.2008 um 17:29 Uhr) Grund: Tippfehler verbessert

  2. #2
    Moderator
    Registriert seit
    Jun 2001
    Beiträge
    1.327
    Renommee
    846

    Beispiel

    Zur Veranschaulichung noch ein Beispiel:

    Eingabe:
    Münzwerte: 1, 5, 10, 20
    Betrag: 108

    Ausgabe:
    Anzahl Münzen: 9
    Zerlegung: 3, 1, 0, 5

    denn 108 = 3*1 + 1*5 + 0*10 + 5*20 und diese Stückelung ist optimal.
    Aktuelle Probleme der Doppelwoche:
    [29 Logik] Fahnenjagd

  3. #3
    Moderator
    Registriert seit
    Jul 2000
    Beiträge
    3.763
    Renommee
    1214

    Re: Beispiel

    Ich habe mir schon 2 Sachen mal ueberlegt gehabt, (immer nur die groessten Muenzen ausgeben, Rucksackproblem) aber das erste war falsch (Muenzen 1,9,10, betrag 18) und es sei effizienter zu loesen/implementieren als das Rucksackproblem.
    Die relativ logische Folgerung war ja, dass ich die Muenzen als "Konstanten eines Polynoms" auffasse, und die Koeffizienten durchrattere, aber a) muss ich damit nicht unbedingt die kleinste Anzahl der Muenzen treffen, und b) wie schalte ich weiter?
    Bei a) waere es natuerlich sinnvoll, zuerst die grossen Muenzen aufzuaddieren, und bei Uebertrag wieder abzuziehen. aber dann fragt sich deshalb bei b) wie ich bei einer unbekannten anzahl an Muenzen gut "weiterschalte"
    ich haeng da, und muss mich jetzt auf was anderes konzentrieren, deshalb musste ich das jetzt loswerden :>
    Wenn jemand ideen hat =)
    kuchen ist dumm, weil er nur labert und nicht wirklich lernen oder verstehen will.

  4. #4
    Registered User
    Registriert seit
    Jun 2001
    Beiträge
    1.178
    Renommee
    80

    Re: Beispiel

    Entweder ich die Aufgabe ist zu einfach oder ich bin zu blöd und verstehe das ganze falsch....

    Tipp: Rechnen modulo

  5. #5
    Violinengott
    Registriert seit
    May 2000
    Beiträge
    705
    Renommee
    158

    Re: Beispiel

    @unex das mit dem modulo geht nicht. nehmen wir deknos' beispiel:
    muenzen: 1, 9, 10
    wert: 18
    18 / 10 --> 1
    18 % 10 --> 8
    8 / 9 --> 0
    8/1 --> 8
    mit diesem system wuerde man fuer den wert 18 eine 10er-muenze und 8 1er-muenzen anstelle von 2 9er-muenzen bekommen.

    tatsache ist aber, dass das muenzensystem so aufgebaut ist dass dies eben nicht passieren kann (zumindest in der schweiz, euro weiss ich nicht):
    5, 10, 20, 50, 100, 200, 500 //werte koennen nicht kleiner als 5 werden
    mit diesem muenzen wuerde das modulo-verfahren gehen, da das muenzensystem so aufgebaut ist dass es eben so geht.

    [edit]
    http://board.buha.info/showthread.php?t=43598
    [/edit]

    If war is the answer, the question must be fucking stupid!

  6. #6
    Registered User
    Registriert seit
    Jun 2001
    Beiträge
    1.178
    Renommee
    80

    Re: Beispiel

    Zitat Zitat von MurderDeathKill
    mit diesem system wuerde man fuer den wert 18 eine 10er-muenze und 8 1er-muenzen anstelle von 2 9er-muenzen bekommen.
    Jip ich dachte so wars gemeint, ich habe das mit der minimalen Anzahl an Münzen übersehen. Sorry.

  7. #7
    Moderator
    Registriert seit
    Jul 2000
    Beiträge
    3.763
    Renommee
    1214

    Re: Beispiel

    @Unex: Ist mir auch am Anfang passiert.
    @Mdk: Ja, das ist beim Euro auch so.
    kuchen ist dumm, weil er nur labert und nicht wirklich lernen oder verstehen will.

  8. #8
    Moderator
    Registriert seit
    Jan 2001
    Beiträge
    1.253
    Renommee
    421

    Re: Beispiel

    Wenn du dir bei modulo erstmal den Rest anschaust...
    Wir denken nur, wenn wir mit einem Problem konfrontiert werden. John Dewey

  9. #9
    Registered User
    Registriert seit
    Apr 2001
    Beiträge
    495
    Renommee
    33

    Re: [PDW 9] Geldwechsel

    scheinbar wird hier ja schon vor dem 21. ordenlich gepostet. dann will ich auch mal meine senf dazu geben:

    damit ich mit dem code jetzt nicht das ganze board zumülle, hab ich ihn auf meinen webspace geuppt:
    Nenene, mit Code warten wir schon bis zum 21. Diskussion ist ok, solange man nicht zu sehr in Richtung einer echten Lösung kommt. Btw, dein Code löst das Problem nicht. DT

    ich denke, durch die kommentare ist es einfach zu verstehen...


    Zitat Zitat von unex
    Entweder ich die Aufgabe ist zu einfach oder ich bin zu blöd und verstehe das ganze falsch....
    seh ich auch so. für den code wie er jetzt da steht (inkl. kommentieren) hab ich 30 min gebraucht.

    who knows...
    Geändert von DarkTom (18.06.2004 um 17:58 Uhr)

  10. #10
    Moderator
    Registriert seit
    Jul 2000
    Beiträge
    3.763
    Renommee
    1214

    Re: [PDW 9] Geldwechsel

    diskutieren ja, code eigentlich vor dem 21 nicht.
    so habe ich jedenfalls darktom verstanden :>
    bzgl. Nicht verstanden. Versuch doch mal, ob du für die münzen 1,9,10
    und den betrag 18 rausbekommst, dass du genau 2 münzen brauchst.
    und im Prinzip, ist ein algorithmus gefragt, der folgende Eigenschaften hat
    finde die kleinste anzahl an muenzen, wenn du beliebige viele(verschiedene) Münzarten, und
    beliebig viele Münzgrössen hast.
    Geändert von Smartie (18.06.2004 um 16:25 Uhr)
    kuchen ist dumm, weil er nur labert und nicht wirklich lernen oder verstehen will.

  11. #11
    Registered User
    Registriert seit
    Apr 2001
    Beiträge
    495
    Renommee
    33

    Re: [PDW 9] Geldwechsel

    Lösungen und Lösungsansätze dürfen ab Montag, dem 21. Juni 2004 gepostet werden.
    hmm. wie definiert man "Lösungsansätze"?

    ach, kein plan. ich denke, jeder, der interesse an dem prob hätte, hats bisher schon gesehen und daher sind diskussionen legitim.

  12. #12
    Moderator
    Registriert seit
    Jul 2000
    Beiträge
    3.763
    Renommee
    1214

    Re: [PDW 9] Geldwechsel

    blub, hab da oben grad nen edit reingehauen
    kuchen ist dumm, weil er nur labert und nicht wirklich lernen oder verstehen will.

  13. #13
    Mastermind in Training
    Registriert seit
    Mar 2001
    Beiträge
    1.552
    Renommee
    727

    Re: Beispiel

    Zitat Zitat von MurderDeathKill
    beispiel:
    muenzen: 1, 9, 10
    wert: 18
    18 / 10 --> 1
    18 % 10 --> 8
    8 / 9 --> 0
    8/1 --> 8
    mit diesem system wuerde man fuer den wert 18 eine 10er-muenze und 8 1er-muenzen anstelle von 2 9er-muenzen bekommen.
    Mist, dass hab ich gar nicht beachtet. Bei dem ersten Beispiel wurd mir das nicht so deutlich.
    Mein Algo würde jetzt 1x10 und 8x1 nehmen. Mist!
    Jetzt muss ich das ganze umprogrammieren. Und ich hab doch keine Zeit

    neon
    Eine Zeitung wirbt mit "Bild dir deine Meinung". Mir wäre es lieber, wenn die Menschen weniger Meinung und dafür mehr Ahnung hätten.

  14. #14
    Moderator
    Registriert seit
    Jun 2001
    Beiträge
    1.327
    Renommee
    846

    Re: [PDW 9] Geldwechsel

    Deknos hat mich schon richtig verstanden. Konkrete Ansätze müssen warten; eine allgemeine Diskussion, die nicht zu nahe in Richtung einer Lösung kommt, ist durchaus erlaubt. Dazu gehören auch Äusserungen darüber, was nicht funktioniert.

    @MurderrDeathKill:
    Ich frage mich, was du uns mit dem Link auf den Bin-Packing-Thread sagen willst. Das ist eigentlich ein anderes Problem.
    Aktuelle Probleme der Doppelwoche:
    [29 Logik] Fahnenjagd

  15. #15
    Violinengott
    Registriert seit
    May 2000
    Beiträge
    705
    Renommee
    158

    Re: [PDW 9] Geldwechsel

    @MurderrDeathKill:
    Ich frage mich, was du uns mit dem Link auf den Bin-Packing-Thread sagen willst. Das ist eigentlich ein anderes Problem.
    ja, hast recht, ich habe da etwas durcheinandergebracht...

    If war is the answer, the question must be fucking stupid!

Aktive Benutzer

Aktive Benutzer

Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)

Ähnliche Themen

  1. Antworten: 4
    Letzter Beitrag: 31.05.2013, 23:00

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •