Wechselgeld 5 besten Kombinationen



  • Guten Tag!

    Meine Aufgabe lautet:
    Wechselgeld.
    Fange beim Anwender eine Summe 0,01 < X < 100.000,00 ab.
    A.) Gebe EIN Ergebnis wieder, welche mit der geringsten Anzahl an Münzen und Scheinen auskommt.
    B.) Gib , wie beim Geldautomaten, eine Liste der 5 besten Kombinationen aus.

    Aufgabe A habe ich fertig. Und bei Aufgabe B komme ich leider nicht weiter...

    Mein Denkansatz ist wie folgt: Vom Ding her würde ich von dem höchstmöglichen Geldwert 1 abziehen und dies 4 Mal insgesamt tun, um 5 Möglichkeiten zu haben.
    Beispiel: Bei 100€ als Betrag, wäre die 1. Möglichkeit 2x 50€(was ich schon programmiert habe) und die 2. Möglichkeit = 1. Möglichkeit Geldwert-1, sodass das Programm nur 1x 50€ nimmt und 3. Möglichkeit = Beginn ab dem 20€ Schein, da der die letzte höchstmögliche Einheit wegfällt...

    Könnte mir da jemand helfen, wie ich diese Idee umsetzen kann?

    Vielen Dank schon einmal im Voraus! 🙂

    #include <stdio.h>
    #include <stdlib.h>
    
    
    int main()
    {
        int geldwert[15] = {50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1};
        int i;
        int j;
        int betrag;
        int rest;
        float gbetrag;
        int geldbetrag[15];
    
        printf("Geben Sie einen Betrag zwischen 0.01 & 100000.00 ein: ");                                   // Abfrage Geldbetrag
        scanf("%f", &gbetrag);
    
    
        betrag = gbetrag*100.0001;                                                                         // Geldbetrag anpassen an das Array (Geldwert)
    
    
        // bestes Ergebnis (geringste Anzahl an Scheinen und Muenzen)
    
        printf("Die beste Kombination lautet: ");
    
            geldbetrag[0] = betrag / geldwert[0];
            rest = betrag % geldwert[0];
    
            printf("%i Mal %i \n", geldbetrag[0], geldwert[0]);
    
    
        for(i=1; i<15; i++)
        {
            geldbetrag[i] = rest / geldwert[i];
            rest = rest % geldwert[i];
    
            printf("%i Mal %i \n", geldbetrag[i], geldwert[i]);                                             // Ausgabe wie viele Scheine oder Muenzen von dem jeweiligen Muenzwert benoetigt werden
        }
        printf("\n");
    
    
    
    
        // 4 weitere Kombinationen mit der geringsten Anzahl
    
        printf("Die 4 weiteren besten Kombinationen lauten: ");
    
        for(j=0; j<4; j++)
        {
                geldbetrag[0] = betrag / geldwert[0];
                rest = betrag % geldwert[0];
    
                printf("%i Mal %i \n", geldbetrag[0], geldwert[0]);
    
    
            for(i=1; i<15; i++)
            {
                geldbetrag[i] = rest / geldwert[i];
                rest = rest % geldwert[i];
    
                printf("%i Mal %i \n", geldbetrag[i], geldwert[i]);
            }
            printf("\n");
        }
    
    
        return 0;
    }
    


  • @codinglea sagte in Wechselgeld 5 besten Kombinationen:

    Beispiel: Bei 100€ als Betrag, wäre die 1. Möglichkeit 2x 50€(was ich schon programmiert habe)

    Nicht 1 x 100€?



  • @Belli
    Ohh! Huch, da hast du recht! Den Schein habe ich wohl aus Versehen verdrängt.. 😀
    Genau, 1. Möglichkeit = 100€, 2. M = 2x 50€, 3. M = 1x 50€, 2x 20€ und 1x 10€ etc....



  • Die Aufgabe ist unterdefiniert, weil es im Allgemeinen keine genau 5 besten Kombinationen gibt. Auch geben Geldautomaten meist nicht die "besten" Kombinationen aus, sondern einige mit wenigen grossen und einige mit viele kleinen Scheinen aus.

    Die Lösung wäre eigentlich zu definieren, wie "gut" eine Kombination ist und dann einfach alle zu erzeugen in einem vector, darauf sort und dann n Einträge dieses Vectors ausgeben. Wenn Güte hier einfach die Anzahl der Scheine ist, sind einige Anordnungen rein zufällig (bzw. implementationsabhängig),



  • @TGGC
    Ja, ich finde die Aufgabe auch sehr unglücklich definiert...
    Also mit Vektoren habe ich mich tatsächlich noch gar nicht beschäftigt und ich glaube, dass das auch nicht von mir in dieser Aufgabe erwartet wird.



  • @codinglea
    Ich sehe das genau so wie du und @TGGC: die Aufgabe ist schlecht definiert.

    Anyway...
    Geh einfach mal davon aus dass du zur Lösung sämtliche Möglichen Kombinationen ermitteln sollst. Das ist eine schöne Übung z.T. Rekursion.

    Davon ausgehend dann etwas zu basteln das die 5 "besten" (wie auch immer definiert) Kombinationen ermittelt und ausgibt, ist in C (ohne ++) leider alles andere als schön. Aber zu schaffen sollte es sein. Dazu muss man auch nicht notwendigerweise alle Lösungen speichern oder etwas sortieren.



  • Ja, es reicht im Prinzip die besten n Lösungen zu speichern. Nur ohne irgendeine Art Container (array, vector, list etc.) ist das ziemlich kacke zu programmieren. Man braucht es nicht, aber 5 einzelne Variabeln zu nutzen gibt sicher Spaghetticode und wird niemand erweitern oder warten wollen und ist daher in der Praxis keine Lösung.

    Eine Idee wäre einfach die Zahl nach oben Abschätzen und mit new ein festes Array zu machen, das die gesamte Lösung halten kann. Dann sollte es ein qsort zum sortieren geben. Alternativ halt n + x und wenn das voll istm qsort und die letzen x wieder überschreiben mit den nächsten x Lösungen.



  • @codinglea sagte in Wechselgeld 5 besten Kombinationen:

    Mein Denkansatz ist wie folgt: Vom Ding her würde ich von dem höchstmöglichen Geldwert 1 abziehen und dies 4 Mal insgesamt tun, um 5 Möglichkeiten zu haben.

    nimm halt wie erwähnt rekursion (da rufst du die funktion innerhalb der funktion mit dem restwert auf) oder du erstellst dir für jeden geldschein eine schleife über die anzahl der maximal möglichen scheine und prüfst dann, ob in der summe der betrag erreicht ist und brichst das ganze dann ab, wenn 5 möglichkeiten erfüllt wurden. da brauchst du dann auch nichts in vektoren (die es in c gar nicht gibt) speichern und kannst das dann direkt ausgeben.



  • Danke für eure Antworten!
    @hustbaer & @Wade1234 Rekursion ist natürlich eine gute Idee, würde ich aber gerne umgehen! 😅

    @TGGC qsort habe ich noch nie gemacht, würde ich daher auch gerne erstmal weglassen, trotzdem danke für dein Vorschlag!!!

    @Wade1234 dein 2. Vorschlag hört sich an wie Brute Force... wäre eine super Idee!
    Und zu Not nehme ich dann die Rekursion! 😜



  • Achsooo... wüsste jemand, wie ich geldwert[i] durch 100 teilen könnte in der Ausgabe?
    Mich stört es ein bisschen, dass ich bei der Ausgabe für 100€ stehen habe: 1 Mal 10000



  • printf("%i", geldwert[i] / 100)

    Aber du hast den Divisionsoperator bestimmt noch nie genutzt und willst daher sicher auch weiter auf den verzichten. Am Ende würde man noch was lernen 🙄



  • This post is deleted!


  • @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    printf("%i", geldwert[i] / 100)

    Das habe ich schon versucht... geht leider nicht, ab dem geldwert=50 entsteht eine 0 bei der Ausgabe...

    Aber du hast den Divisionsoperator bestimmt noch nie genutzt und willst daher sicher auch weiter auf den verzichten. Am Ende würde man noch was lernen 🙄

    So war das gar nicht gemeint, dass ich nicht was dazu lernen will...



  • @codinglea sagte in Wechselgeld 5 besten Kombinationen:

    Danke für eure Antworten!
    @hustbaer & @Wade1234 Rekursion ist natürlich eine gute Idee, würde ich aber gerne umgehen! 😅

    Darfst du gerne. Es ist bloss in diesem Fall vermutlich einfacher.



  • @hustbaer
    Definitiv. Habe mich auch dazu entschieden, es rekursiv zu erstellen. Allerdings habe ich damit noch nicht so viel gearbeitet und tue mich damit etwas schwer.



  • @codinglea sagte in Wechselgeld 5 besten Kombinationen:

    @Wade1234 dein 2. Vorschlag hört sich an wie Brute Force... wäre eine super Idee!
    Und zu Not nehme ich dann die Rekursion! 😜

    es ist auch brute-force. wie du unter https://www.c-plusplus.net/forum/topic/350091/1-bis-100-centbeträge-möglichkeiten-kombinationen-algorithmus/32 sehen kannst, funktioniert es aber deutlich schneller als rekursion. 3 min wartezeit gehen sicherlich noch, aber manchmal lohnt sich eben auch der aufwand, es nicht rekursiv zu programmieren.

    @codinglea sagte in Wechselgeld 5 besten Kombinationen:

    @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    printf("%i", geldwert[i] / 100)

    Das habe ich schon versucht... geht leider nicht, ab dem geldwert=50 entsteht eine 0 bei der Ausgabe...

    logisch. 50 / 100 ist ja auch 0 Rest 50, was du bedeutet, dass im geldbetrag 50 eben keine 100 vorkommen.



  • @Wade1234
    Okay, dann werde ich den Aufwand betreiben. Ist für mich vom Ding her auch einfacher, weil ich nicht wüsste, wie ich das rekursiv darstellen soll.

    Hättest du einen Vorschlag, wie ich die Geldwerte besser darstellen könnte?



  • Du kennst doch schon den Modulo-Operator % (den du bei der Variablen rest benutzt):

    printf("%d€ %d Cent", wert / 100, wert % 100);
    


  • @Th69
    Stimmt, danke. Stand auf dem Schlauch... manchmal sieht man den Wald vor lauter Bäumen nicht.



  • @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    @codinglea sagte in Wechselgeld 5 besten Kombinationen:

    @Wade1234 dein 2. Vorschlag hört sich an wie Brute Force... wäre eine super Idee!
    Und zu Not nehme ich dann die Rekursion! 😜

    es ist auch brute-force. wie du unter https://www.c-plusplus.net/forum/topic/350091/1-bis-100-centbeträge-möglichkeiten-kombinationen-algorithmus/32 sehen kannst, funktioniert es aber deutlich schneller als rekursion. 3 min wartezeit gehen sicherlich noch, aber manchmal lohnt sich eben auch der aufwand, es nicht rekursiv zu programmieren.

    Ist es echt nötig hier jemanden der Lernen möchte einen extrem schlechten Code zu verlinken? Vor allem wo der nachweislich bei etwas Nachdenken in 3 Zeilen rekursiv und performanter programmierbar war?