Wechselgeld 5 besten Kombinationen

EinNutzer0

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.

TGGC

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.

@codinglea fertig?

EinNutzer0

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.

SeppJ

@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.

EinNutzer0

@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.

TGGC

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.

SeppJ

@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.

titan99_

Dieser Beitrag wurde gelöscht!

Th69

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

@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?

EinNutzer0

@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).

@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.

EinNutzer0

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

TGGC

@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.

Belli

@Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

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

Nur, dass die Lösungen 2 bis 4 von EinNutzer mit 5 Scheinen auskommen, während Du schon ab Lösung 3 6 Scheine benötigst ...

EinNutzer0

Du bist aber nicht Lehrer. Ich wäre auch gern US-Präsident oder Astronaut, kann mir aber vermutlich beides abhaken. Werd erstmal erwachsen.

Belli

@EinNutzer0
Ich glaube, Du kannst ganz froh sein ... wenn Du Dich als Astronaut auch so unbelehrbar starrsinnig an Ideen klammern würdest, würdest Du vermutlich nicht alt werden ...

EinNutzer0

Naja, aber als Präsident den halben Tag twittern kann ich.

Ich mag diese Großspurigkeit von @TGGC einfach nicht.

@Belli sagte in Wechselgeld 5 besten Kombinationen:

@Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

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

Nur, dass die Lösungen 2 bis 4 von EinNutzer mit 5 Scheinen auskommen, während Du schon ab Lösung 3 6 Scheine benötigst ...

dafür bestehen meine lösungen nicht meistens aus 500€-scheinen. also mein mathelehrer hat angeblich mal mittels differentialrechnung die "optimalen" maße für bierdosen ausgerechnet und dann an holsten geschrieben, dass sie mit diesen maßen ja soundso viel material einsparen würden. antwort: dann kann die dose von 80% der kunden nicht mehr vernünftig angefasst werden.