Wechselgeld 5 besten Kombinationen

Belli

Man wird nicht umhin kommen, ALLE Möglichkeiten zu berechnen, und sich dann die 5 mit den wenigsten Stücken rauszusuchen.
Wobei es dabei ja dann immer Abbruchkriterien gibt, die wurden ja auch schon genannt, zB. wenn ich fünf Lösungen habe, breche ich jede weitere Berechnung ab, sobald ich auf mehr Stücke als die fünftschlechtest komme, usw. ...

TGGC

Aber auch wenns vorberechet ist, setzt sich keiner von Hand hin für alle Kombos. Beim Bankautomat ist so eine Regel wie "gib mindestens/höchstens x Euro in grossen/kleinen Scheinen" und das x variert halt für die verschiedenen Optionen. Der User wählt dann ob er grosse oder kleine Scheine bevorzugt. Die letzte Option gibt dann z.B. ein Haufen 5er Scheine und nicht möglichst wenig Scheine.

Belli

Der Geldautomat könnte denke ich sogar alles berechnen:

gibt der nur Scheine aus, keine Münzen, es gibt also nur 6 verschiedene Sorten, und
die Beträge, die man da abheben kann, sind auch limitiert.

Belli

@codinglea:
Wieso darf es eigentlich nicht C++ sein? Das würde einige Kleinigkeiten (zB. ein dynamischer Container) etwas erleichtern ...

DocShoe

Vielleicht kennt der Bankautomat auch seinen Bestand an Scheinen und berücksichtigt den beim Vorschlag der Stückelungen.

@EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

es ist C++ und wahrscheinlich nicht leicht nach C übertragbar

sehe ich das richtig? man müsste erst einmal c++ lernen, um dein programm richtig zu verstehen und nach C umwandeln zu können, weil du eben kein C und damit auch kein vernünftiges beispiel kannst. oh mann!

TGGC

Automaten haben normal nur 4 Arten Scheine und rechnen teils auch den Bestand ein, geben z.B. auch eine Meldung aus, das nur Betrag x ausgezahlt werden kann, wenn z.b. 5er komplett aus sind.

@Wade1234 Quatsch, das Programm ist in 10 Min umgeschrieben, wenn man einfach feste Arrays allokiert.

wob

@codinglea

Ich würde vorschlagen, erstmal mit der einfacheren Aufgabe "Alle Lösung ausgeben" anzufangen.

Dazu braucht man nur 2 Arrays:

das mit den Scheinwerten
und ein genauso langes Array, wo man für jeden Schein speichert, wie oft man ihn gewählt hat, anfangs mit 0 initialisiert.

Schnell runtergeschrieben sieht das so aus:

#include <stdio.h>

void printSolutionResult(int scheine_size, const int *scheine, const int *auswahl) {
    int trennerBenoetigt = 0;
    for (int i = 0; i < scheine_size; ++i) {
        if (auswahl[i]) {
            if (trennerBenoetigt) printf(", "); else trennerBenoetigt = 1;
            printf("%d x %d EUR", auswahl[i], scheine[i]);
        }
    }
    puts("");
}

void findSolutions_impl(int restbetrag, int pos, int scheine_size,
                        const int* scheine, int *auswahl) {
    if (pos == scheine_size - 1) {
        if (restbetrag % scheine[pos] == 0) {
            auswahl[pos] = restbetrag / scheine[pos];
            printSolutionResult(scheine_size, scheine, auswahl);
        }
    } else {
        for (int nAktuellerSchein = restbetrag / scheine[pos];
             nAktuellerSchein >= 0; --nAktuellerSchein) {
            auswahl[pos] = nAktuellerSchein;
            findSolutions_impl(restbetrag - scheine[pos] * nAktuellerSchein,
                               pos + 1, scheine_size, scheine, auswahl);
        }
    }
}

void printSolutions(int betrag) {
    const int scheine[] = {200, 100, 50, 20, 10, 5};
    const int scheine_size = sizeof(scheine)/sizeof(scheine[0]);

    int auswahl[scheine_size];
    for (int i = 0; i < scheine_size; ++i) auswahl[i] = 0;

    findSolutions_impl(betrag, 0, scheine_size, scheine, auswahl);
}

int main(void) {
    printSolutions(150);
}

Du brauchst nur Zeile 32 zu ändern, wenn du andere Scheine hast.

Belli

@Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

@EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

es ist C++ und wahrscheinlich nicht leicht nach C übertragbar

sehe ich das richtig? man müsste erst einmal c++ lernen, um dein programm richtig zu verstehen und nach C umwandeln zu können, weil du eben kein C und damit auch kein vernünftiges beispiel kannst. oh mann!

Sehe ich das richtig? Du müsstest erst mal C++ lernen, um sein Programm richtig zu verstehen, weil Du eben kein C++ kannst?
Oh Mann ...

codinglea

Mein Ausbilder wünscht explizit, dass ich alles in C schreibe.

@TGGC
Ich weiß gar nicht, wo dein Problem liegt. Ich bin für neue Sachen offen, allerdings sollen alle Aufgaben sehr einfach gelöst werden.
Von dir kommen(für mich noch) immer komplizierte Lösungen.

SeppJ

@codinglea sagte in Wechselgeld 5 besten Kombinationen:

Mein Ausbilder wünscht explizit, dass ich alles in C schreibe.

Ignorier' einfach alles von EinNutzer0, der ist einfach nicht hilfreich.

@TGGC
Ich weiß gar nicht, wo dein Problem liegt. Ich bin für neue Sachen offen, allerdings sollen alle Aufgaben sehr einfach gelöst werden.
Von dir kommen(für mich noch) immer komplizierte Lösungen.

Das liegt letztlich an dem, was TGGC in seiner allerersten Antwort vor langer Zeit geschrieben hat. Die Aufgabe ist uneindeutig gestellt:

@TGGC sagte in Wechselgeld 5 besten Kombinationen:

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),

Nun ist die ganz allgemeine Lösung, die mit beliebigen Scheinstückelung und einer relativ beliebigen Definition von "gut" zurecht kommt, nun einmal nicht so ganz einfach. Das ist nun einmal so. Würde man sich hingegen auf die übliche Stückelung (1, 2, 5, 10, … ) beschränken, wäre es schon viel einfacher. Wenn man dann auch noch eine günstige Definition von "gut" wählt, ist es noch besser.

EinNutzer0

Dieser Beitrag wurde gelöscht!

@codinglea läuft es denn jetzt?

TGGC

@SeppJ sagte in Wechselgeld 5 besten Kombinationen:

Nun ist die ganz allgemeine Lösung, die mit beliebigen Scheinstückelung und einer relativ beliebigen Definition von "gut" zurecht kommt, nun einmal nicht so ganz einfach.

Man muss aber dazu sagen, das sie ist aber auch nicht so schwer ist. Man muss sich mit Arrays, Divide'n'Conqer und Sortieren auskennen - was alles komplette Grundlagen sind und jeder produktiv arbeitende Programmierer lange im Schlaf kann. Diese ganze Rumgekrebse um dies krampfhaft zu umgehen und eine "simplere" Lösung zusammenzufrickeln ist reine Zeitverschwendung mit der man am Ende 0 gewinnt. So lange wie der Thread läuft hätte man diese drei Prinzipien auch längst durchdringen können. Bis aufs letztendliche Sortieren wurden ja hier auch schon Lösungen gezeigt.

SeppJ

Das ist wahr.

Oft sind allgemeine Lösungen ja sogar einfacher zu programmieren, laufen bloß länger. Hier hat man halt den Sonderfall, dass bei einer 1-2-5-Stückelung der Algorithmus zum Finden der "besten" Lösung ein ganzes Stück einfacher ist als im allgemeinen Fall und man sich dann daran hochhangeln könnte. Wenn man denn könnte. Hier fehlt das intuitive Verständnis für die grundlegenden Sprachmittel, die von dir genannt wurden, die die Notwendigkeit sind, damit man ein intuitives Verständnis für Algorithmen entwickeln kann. Ich empfehle, ein paar einfachere Übungsaufgaben zu versuchen. Oder vor allem Übungsaufgaben, die irgendeinem didaktischen Plan folgen. Diesen Mangel hat man schon bei der vorherigen Fragestellung von codinglea gemerkt, die überhaupt nicht für C auf dem Level geeignet war. Und jetzt schon wieder so etwas. Ich möchte die Kompetenz der Lehrkraft bei der Wahl dieser Aufgaben anzweifeln (Oder es ist ein fortgeschrittener Kurs und codinglea ist ganz weit abgehängt, kann man als Außenstehender schließlich nicht beurteilen).

TGGC

Für die Beste - ja. Fürs Fünftbeste geht aber schon vorhersehbar die Frickelei los. So kann es vom Lehrenden nicht gedacht sein, entweder hat der sich wirklich gar nichts dabei gedacht (wie ich schon vermutete, das man so eine Ausbilding sich auch sparen kann) oder lea bekommt es 0 auf die Kette obwohl die Sachen schon soweit vermittelt wurden.

codinglea

Ich weiß nicht, wie oft ich das noch erwähnen muss...
Ich mache eine Ausbildung und muss mir ALLES selber beibringen, ich habe einfach nur Aufgaben erhalten, die ich abarbeiten muss. Mit den Voraussetzungen keine Wiederholung im Code und simpel gehalten und das war's.

Es nervt, dass ich das immer wieder erwähnen muss. Außerdem nervt das total, dass hier manche meinen, klugscheißen zu müssen und dann aber wiederum hier was in C++ reinzuschicken und es nicht mal schaffen zu lesen, welche Kategorie das ist...
Oder auch einfach nur so Müll reinschreiben und gar nicht weiterhelfen... die können gerne ihr Frust woanders auslassen.
Ich hätte gerne einfach nur von hilfsbereiten Leuten Hilfe, da ich erst seit ein paar Wochen C lerne.

codinglea

@TGGC
So ein Kommentar ist zum Beispiel total unnötig!
Hilft mir nicht weiter und ich habe erwähnt, dass ich die Aufgabe so bekommen habe, fertig.

SeppJ

Wir sehen jemanden, der auf diese Art und Weise garantiert nicht C lernen wird. Das merkst du doch wohl auch hoffentlich selber, dass du nicht klar kommst. Und wir konnten dir sogar ziemlich eindeutig sagen, woran das liegt. Dem Rat kannst du entweder folgen, oder auch nicht. Ist schließlich deine Sache, ob du damit Erfolg haben möchtest oder nicht. Aber deine persönliche Einstellung dazu verändert nicht, dass deine Lernmethode schlecht ist, und dich deswegen jeder, der dir wirklich helfen möchte, ständig darauf aufmerksam machen wird. Die sind nicht böse, die wollen dir helfen! Wenn wir dir hingegen einfach nur eine Lösung hinklatschen, hilft dir das gar nix.

titan99_

Dieser Beitrag wurde gelöscht!