Wechselgeld 5 besten Kombinationen

SeppJ

@Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

naja du erzeugst da ein dynamisches array ("variable length array") und dynamisch ist eben fast immer doof. also was ich meine ist eben, dass du damit unnötig overhead produzierst, weil der speicher eben zur laufzeit angefordert wird und nicht während des copiliervorgangs.

VLAs funktionieren so nicht. Die verhalten sich wie automatische Variablen, und technisch gesehen liegen sie bei üblichen Implementierungen auf dem Stack.

Und bezüglich deiner davor gewagten Vermutung, dass es sie in C nicht geben würde: VLAs gibt es nur in C, genauer ab C99. Wobei sie ab C11 nur noch optional sind. In C++ gibt es sie nicht. Bloß der GCC bietet sie als optionale Spracherweiterung für C++ an, da er dafür einfach seine Implementierung von C99 1:1 übernehmen kann.

wob könnte seinen Code relativ einfach ohne VLAs auskommen lassen, indem er das sizeof-Resultat nicht zwischenspeichert, da das Ergebnis von sizeof eine Compilezeitkonstante ist. Da es aber praktisch keinen Unterschied macht, und das Vorkommen von VLAs in diesem Code nur aufgrund von Haarspalterei über unintuitive Eigenschaften der Sprache C kommt (const ist hier keine Compilerzeitkonstante....), finde ich das voll in Ordnung, das hier zugunsten der Lesbarkeit so zu machen. VLAs haben einen schlechten Ruf, aber der kommt von der anderen, falschen Anwendungsart her, die hier nicht benutzt wird.

@SeppJ sagte in Wechselgeld 5 besten Kombinationen:

Und bezüglich deiner davor gewagten Vermutung, dass es sie in C nicht geben würde: VLAs gibt es nur in C, genauer ab C99. Wobei sie ab C11 nur noch optional sind. In C++ gibt es sie nicht. Bloß der GCC bietet sie als optionale Spracherweiterung für C++ an, da er dafür einfach seine Implementierung von C99 1:1 übernehmen kann.

ich meinte damit, dass man unter c++ guten gewissens const int als längenangabe für ein array nehmen kann, unter c aber davon abstand nehmen sollte, sofern man keinen guten grund dafür hat.

SeppJ

@Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

@SeppJ sagte in Wechselgeld 5 besten Kombinationen:

Und bezüglich deiner davor gewagten Vermutung, dass es sie in C nicht geben würde: VLAs gibt es nur in C, genauer ab C99. Wobei sie ab C11 nur noch optional sind. In C++ gibt es sie nicht. Bloß der GCC bietet sie als optionale Spracherweiterung für C++ an, da er dafür einfach seine Implementierung von C99 1:1 übernehmen kann.

ich meinte damit, dass man unter c++ guten gewissens const int als längenangabe für ein array nehmen kann, unter c aber davon abstand nehmen sollte, sofern man keinen guten grund dafür hat.

Wieso? Es gibt keinen guten Grund für diese Behauptung, noch für deren Gegenteil. Die Sprache spielt überhaupt gar keine Rolle, bloß ob man Compilezeitkonstanten, VLAs, etc. verstanden hat. Aus deinen obigen Beiträgen zu VLAs zu urteilen fehlt dir mindestens dieser Teil.

EinNutzer0

@TGGC sagte in Wechselgeld 5 besten Kombinationen:

Ja, ist aber leider mal wieder falsch. 4) hat 6 Scheine und 5) hat nur 5 Scheine. Also deine max 5 Flickschusterei ist auch keine Lösung

Ja aber dann sind wir wieder bei der Frage, wie "richtig" definiert ist?

TGGC

Das steht im allerersten Post.
// bestes Ergebnis (geringste Anzahl an Scheinen und Muenzen)

EinNutzer0

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

SeppJ

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

EinNutzer0

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

SeppJ

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

wob

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

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.