4. Wechselgeld 5 besten Kombinationen

Wechselgeld 5 besten Kombinationen

  • E
    Gesperrt

    @TGGC ja ich würd die maximale Anzahl gleicher Scheine beibehalten und dann ein Selectionsort auf dem Array machen. Etwas anderes/besseres fällt mir gerade nicht ein.

    0
  • Mod

    @EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

    @Th69 sagte in Wechselgeld 5 besten Kombinationen:

    Warum übergibst du n als Zeiger?

    Weil ich nicht auf eine globale Variable ausweichen möchte...

    Vielleicht gibt es ja andere, schönere Arten, Information zwischen Rekursionsebenen zu transportieren? Man könnte auch umgekehrt sagen: Ein Problem mit deiner Idee ist, dass du das so brauchst. Du solltest keinen Informationstransport zwischen verschiedenen Ästen der Rekursion brauchen, die Information sollte umgekehrt fließen. Die Äste können nämlich sowieso nicht sauber miteinander koordinieren. Das sieht man an dem Problem der Ordnung deiner Lösungen.

    @Th69 sagte in Wechselgeld 5 besten Kombinationen:

    Und warum ist max_nums 5?

    Weil es (bei mir) maximal 5mal dieselbe Scheinart geben soll.

    Und das leitet sich wie aus der Aufgabenstellung her? Mit dieser ungerechtfertigten Annahme erreichst du doch nur, dass man trivial Gegenbeispiele konstruieren kann, bei denen dein Code nicht aufgeht. Indirekt ist das auch dafür verantwortlich für das Problem, auf das dich TGGC schon aufmerksam gemacht wird, bezüglich der Ordnung deiner Lösungen. Man kann es leider nicht so einfach korrigieren, weil dieses max_num ziemlich tief in deine Lösungsidee eingebaut ist.

    Es ist im Rahmen deiner eigenen Annahmen ein ganz guter Versuch (und viel lesbarer als einiger Code den du sonst so hast), aber an diesem letzten Punkt hakt es, da du dort eben eine eigene Annahme gemacht hast, die nicht stimmt. Es wurden schon andere, korrekte Lösungen gezeigt, und das Problem zu Tode diskutiert, daher spare ich mir konkrete Verbesserungsvorschläge.

    0
  • E
    Gesperrt

    Ich lehne mich mal etwas aus dem Fenster und behaupte, dass es ohne weitere Beschränkungen viel zu viele Lösungen für das Problem gebe und das Problem nicht mehr praktikabel wäre...

    0
    W
     2 Antworten
  • Mod

    @EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

    Ich lehne mich mal etwas aus dem Fenster und behaupte, dass es ohne weitere Beschränkungen viel zu viele Lösungen für das Problem gebe und das Problem nicht mehr praktikabel wäre...

    So furchtbar schwer ist das ganz allgemeine Problem nicht. Die Idee ist schließlich einfach: Systematisch alle möglichen Kombinationen erzeugen (das sind endlich viele und der Lösungsraum ist beschränkt durch die Anforderung an die Gesamtsumme, und durch die Existenz eines kleinsten Scheins), und dann die N besten Lösungen auswählen. Mit naheliegenden Verbesserungen die in diesem Thread höchstwahrscheinlich schon zu genüge diskutiert wurden, aber er ist mir zu lang, als dass ich ihn vollständig lesen wollte.

    PS: Ahh, wahrscheinlich hast du deine Aussage anders gemeint. Falls ja, dann siehe wobs Antwort unter mir.

    0
  • W

    @EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

    Ich lehne mich mal etwas aus dem Fenster und behaupte, dass es ohne weitere Beschränkungen viel zu viele Lösungen für das Problem gebe

    Naja, man wird aber, wenn man die großen Scheine zuerst probiert, in realistischen Fällen (es gibt ein Geldstück mit dem Wert 1 bzw. die weiteren Geldwerte sind alles Vielfache des kleinsten) schon gleich im ersten Versuch eine halbwegs ordentliche Lösung finden. Man muss sich dann nur die Anzahl der Scheine speichern und kann fortan die Rekursion abbrechen, wenn man mehr Scheine als in der besten Lösung hat. Bzw. man speichert sich die 5 besten Längen und schneidet bei der längsten der 5 ab, wenn man 5 Lösungen sucht.

    0
  • E
    Gesperrt

    Ok, eure Argumentationen scheinen mir schlüssig.

    Man würd dann vielleicht nicht eine maximale Anzahl pro Schein wählen, sondern eine maximale Anzahl insgesamt. Und dann würd man die aktuelle Anzahl insgesamt entweder zählen oder speichern. Aber dann wäre man auch wieder beim Sortieren.

    Also ich würd die Schwierigkeit der zweiten Teilaufgabe auf einer Skala von 1 bis 10 bei 7,5 einordnen.

    0

  • Du kannst schon eine Maximalanzahl wählen, nämlich Betrag durch kleinste Stücklung. Dein Problem ist, das du versuchst die Scheinanzahl so zu wählen, das es für irgendeinen Geldbetrag zufällig die richtige Reihenfolge an Lösungen rausschmeisst. Das ist aber keine allgemeingültige Lösung. Es ist allgemein unmöglich auf einer höheren Ebene der Rekursion zu entscheiden, wohin man zu erst absteigen sollte, um die gewünschte Lösung zu erhalten - sonst bräuchte man auch gar nicht erst weiterrechnen, wenn das schon bekannt wäre.

    Man kann die Lösungen aber auch so generieren, das sie in der richtigen Reihenfolge erzeugt werden. Das ist aber nicht trivial und nur eine Lösung für diese spezielle Aufgabe, weshalb ich darauf gar nicht eingehen möchte weil es eben für einen Anfänger wesentlich sinnvoller ist das Sortieren zu verstehen, da dadurch jegliche Aufgabe dieser Art lösbar wird.

    0
  • ?

    @codinglea fertig?

    0
  • E
    Gesperrt

    Ok, das ist jetzt etwas unschön (aber immernoch ANSI-C).

    Res1 speichert eine Kombination und hat ggf einen Pointer auf die nächste Kombination.

    calc_a berechnet alle Kombinationen, wobei jede Kombination <= n Scheine besitzt.

    calc_b gibt mindestens die n besten Kombinationen für einen Betrag x aus.

    Beispiel: Es sollen mindestens die 20 besten Kombinationen für den Betrag 59 ausgegeben werden (tatsächlich sind es insgesamt 26 Kombinationen):

    #include <stdio.h>
#include <stdlib.h>

#define nums 9

const int numbers1[nums] = {1, 2, 5, 10, 20, 50, 100, 200, 500};

struct Res1
{
    int a[nums];
    struct Res1 *b;
};

void calc_a(int n, int idx, int sum, int *numbers2, struct Res1 **r1)
{
    int i;
    if (idx >= nums)
    {
        if (sum == 0)
        {
            for (i = 0; i < nums; i++)
            {
                (*r1)->a[i] = numbers2[i];
            }
            (*r1)->b = malloc(sizeof(struct Res1));
            *r1 = (*r1)->b;
            (*r1)->b = NULL;
        }
        return;
    }
    for (i = 0; sum - (numbers1[idx] * i) >= 0 && (n - i) >= 0; i++)
    {
        numbers2[idx] = i;
        calc_a(n - i, idx + 1, sum - (numbers1[idx] * i), numbers2, r1);
        numbers2[idx] = 0;
    }
}

void calc_b(int x, int n)
{
    int i, j;
    int numbers2[nums] = {0};
    struct Res1 *a = NULL;
    struct Res1 *b = NULL;
    for (i = 1, j = 0; j < n; i++)
    {
        while (a)
        {
            b = a->b;
            free(a);
            a = b;
        }
        a = malloc(sizeof(struct Res1));
        a->b = NULL;
        b = a;
        calc_a(i, 0, x, numbers2, &a);
        a = b;
        for (j = 0; b->b; j++, b = b->b)
            ;
        b = a;
    }
    while (b->b)
    {
        for (i = 0; i < nums; i++)
        {
            if (b->a[i])
            {
                printf("%dx%d ", b->a[i], numbers1[i]);
            }
        }
        printf("\n");
        b = b->b;
    }
    while (a)
    {
        b = a->b;
        free(a);
        a = b;
    }
}

int main()
{
    calc_b(59, 20);
    return 0;
}

    Problem: Es muss immernoch sortiert werden, deswegen ist calc_a vielleicht immernoch falsch.

    0 1 Antwort
  • Mod

    @EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

    Problem: Es muss immernoch sortiert werden, deswegen ist calc_a vielleicht immernoch falsch.

    Ich weiß nicht, ob du das gleiche meinst wie ich, aber da sind ja immer noch ganz oft Kombinationen in der falschen Reihenfolge.

    Du fängst auch wieder an, komische, unübliche Programmierstrukturen und Namensgebungen zu benutzen, wodurch das Programm als Vorbild wenig taugt, und nur schwer zu korrigieren ist. Schlimmstes Verbrechen ist wohl Zeile 58, aber so einiges anderes kommt da auch nahe dran. In einem anderen Thread wurde dir mal ein ganz ausgezeichneter Vortrag über Namenskonventionen verlinkt, schade, dass du dir das nicht angesehen hast.

    0
  • E
    Gesperrt

    @SeppJ Also unabhängig von dem (zugegebenermaßen) Pointer-DingDong hab ich das Problem, dass man die mindestens n besten Kombinationen nicht in der richtigen Reihenfolge berechnen kann.

    Oder ich bin dafür nicht schlau genug.

    0 1 Antwort

  • Für "beste" Kombination == "wenige Geldstücke" geht das schon. Ist sogar ziemlich simpel und braucht keine Rekursion. Wie aber schon mehrfach gesagt sehe ich darin wenig Sinn.

    0
  • Mod

    @EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

    @SeppJ Also unabhängig von dem (zugegebenermaßen) Pointer-DingDong hab ich das Problem, dass man die mindestens n besten Kombinationen nicht in der richtigen Reihenfolge berechnen kann.

    Dann musst du dir entweder eine andere Methode ausdenken (siehe TGGC) oder aber eine andere Möglichkeit, wie man so etwas in die richtige Reihenfolge bringen kann. Dinge in die richtige Reihenfolge zu bringen, ist ein häufiges Problem. Da muss man als Programmierer ein paar Standardansätze in der Hand habe, über die man nicht groß nachdenken braucht. Dafür ja auch diese Übungsaufgaben. Ebenso: Die Top N aus einer unbekannten Menge bestimmen, ohne alles zu sortieren; und beim Berechnen von "Wegen" früh feststellen, dass man sich verlaufen hat.

    0
  • T
    Gesperrt

    Dieser Beitrag wurde gelöscht!
    0
    ?
     1 Antwort

  • So, darauf habe ich gewartet: der 200. Eintrag hier. 😉

    0
  • ?

    @titan99_ sagte in Wechselgeld 5 besten Kombinationen:

    Es ist mit 198 Beiträgen auch sehr übersichtlich. Da ist die Grenze noch lange nicht erreicht 🤭

    Langsam braucht es ein Inhaltsverzeichnis 😄

    was willst du da denn rein schreiben? präpubertäres, am thema vorbeigehendes, rumgetrolle seite 1ff?

    0
  • E
    Gesperrt

    @TGGC versteht mich einfach nicht. Schade. 😞

    1x5 1x50 1x500  (3)
1x5 1x10 2x20 1x500     (5)
1x1 2x2 1x50 1x500      (5)
1x5 1x50 1x100 2x200    (5)
1x5 1x50 3x100 1x200    (6)
1x5 3x50 2x200  (6)
1x5 3x10 1x20 1x500     (6)
3x5 2x20 1x500  (6)
3x1 1x2 1x50 1x500      (6)

    Wäre das jetzt die genau richtige Reihenfolge und die genau 9 besten Kombinationen für den Betrag 555? Dann hätte ich nämlich eine Lösung gefunden, mit einer selbst gebastelten PrioQueue. 🤣 (Viel zu viel Umstand für diese Aufgabe).

    0
    ?
     2 Antworten
  • ?

    @EinNutzer0

    500e: 1
200e: 0
100e: 0
50e: 1
20e: 0
10e: 0
5e: 1
2e: 0
1e:0
50ct: 0
20ct: 0
10ct: 0
5ct: 0
2ct: 0
1ct: 0

500e: 0
200e: 2
100e: 1
50e: 1
20e: 0
10e: 0
5e: 1
2e: 0
1e:0
50ct: 0
20ct: 0
10ct: 0
5ct: 0
2ct: 0
1ct: 0

500e: 0
200e: 1
100e: 3
50e: 1
20e: 0
10e: 0
5e: 1
2e: 0
1e:0
50ct: 0
20ct: 0
10ct: 0
5ct: 0
2ct: 0
1ct: 0

500e: 0
200e: 0
100e: 5
50e: 1
20e: 0
10e: 0
5e: 1
2e: 0
1e:0
50ct: 0
20ct: 0
10ct: 0
5ct: 0
2ct: 0
1ct: 0

500e: 0
200e: 2
100e: 0
50e: 3
20e: 0
10e: 0
5e: 1
2e: 0
1e:0
50ct: 0
20ct: 0
10ct: 0
5ct: 0
2ct: 0
1ct: 0

500e: 0
200e: 1
100e: 2
50e: 3
20e: 0
10e: 0
5e: 1
2e: 0
1e:0
50ct: 0
20ct: 0
10ct: 0
5ct: 0
2ct: 0
1ct: 0

500e: 0
200e: 0
100e: 4
50e: 3
20e: 0
10e: 0
5e: 1
2e: 0
1e:0
50ct: 0
20ct: 0
10ct: 0
5ct: 0
2ct: 0
1ct: 0

500e: 0
200e: 1
100e: 1
50e: 5
20e: 0
10e: 0
5e: 1
2e: 0
1e:0
50ct: 0
20ct: 0
10ct: 0
5ct: 0
2ct: 0
1ct: 0

500e: 0
200e: 0
100e: 3
50e: 5
20e: 0
10e: 0
5e: 1
2e: 0
1e:0
50ct: 0
20ct: 0
10ct: 0
5ct: 0
2ct: 0
1ct: 0

    wäre das, was mein programm ausgibt. ehrlich gesagt gefallen mir die kombinationen da irgendwie besser.

    0
    B
     1 Antwort
  • E
    Gesperrt

    @codinglea
    Bringe einfach irgendwie in Erfahrung, ob das prüfungsrelevant ist - und, FALLS NICHT, vergiss das komplette Thema einfach. 😃

    0

  • @EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

    Wäre das jetzt die genau richtige Reihenfolge und die genau 9 besten Kombinationen für den Betrag 555? Dann hätte ich nämlich eine Lösung gefunden, mit einer selbst gebastelten PrioQueue. 🤣 (Viel zu viel Umstand für diese Aufgabe).

    Das ist genau das Problem, es gibt keine genau richtige Reihenfolge. Man könnte innerhalb der Blöcke beliebig tauschen und es wäre trotzdem richtig. Obs wirklich richtig ist und nichts fehlt ist aber schwer aus dem Stand zu überblicken.

    Aber viel wichtiger, ein Beweis ist das eh nicht. Ich würde als Lehrender nicht mal akzeptieren, wenn du das für alle Zahlen 1 bis INT_MAX laufen lässt. Du sollst gedanklich nachvollziehen können, warum dein Programm in jedem Fall die richtigen Lösungen raussucht. Und nicht CodeZeilen rumschieben, bis es bei 555 mal was ausspuckt, was irgendwie richtig aussieht. Darum macht es eben auch Sinn fertige Sachen wie qsort aufzurufen, weil man dann das Ergebnis der Sortierung nicht mehr diskutieren muss.

    0
array 25 kombinationen 3 schleifen 3
Anmelden zum Antworten