Wechselgeld 5 besten Kombinationen
-
@codinglea Wie sieht dein Code bis jetzt aus?
-
#include <stdio.h> #include <stdlib.h> int main() { int betrag; int o, n, m, l, k, j, i, h, g, f, e, d, c, b, a; int o_wert= 1, n_wert = 2, m_wert = 5, l_wert = 10, k_wert = 20, j_wert = 50, i_wert = 100, h_wert = 200, g_wert = 500, f_wert = 1000, e_wert = 2000, d_wert = 5000, c_wert = 10000, b_wert = 20000, a_wert = 50000; int max_o, max_n, max_m, max_l, max_k, max_j, max_i, max_h, max_g, max_f, max_e, max_d, max_c, max_b, max_a; int ergo, ergn, ergm, ergl, ergk, ergj, ergi, ergh, ergg, ergf, erge, ergd, ergc, ergb, erga; max_o = betrag / o_wert; max_n = betrag / n_wert; max_m = betrag / m_wert; max_l = betrag / l_wert; max_k = betrag / k_wert; max_j = betrag / j_wert; max_i = betrag / i_wert; max_h = betrag / h_wert; max_g = betrag / g_wert; max_f = betrag / f_wert; max_e = betrag / e_wert; max_d = betrag / d_wert; max_c = betrag / c_wert; max_b = betrag / b_wert; max_a = betrag / a_wert; for(o = 0; o <= max_o; o++) { for(n = 0; n <= max_n; n++) { for(m = 0; m <= max_m; m++) { for(l = 0; l <= max_l; l++) { for(k = 0; m <= max_k; k++) { for(j = 0; j <= max_j; j++) { for(i = 0; i <= max_i; i++) { for(h = 0; h <= max_h; h++) { for(g = 0; g <= max_g; g++) { for(f = 0; f <= max_f; f++) { for(e = 0; e <= max_e; e++) { for(d = 0; d <= max_d; d++) { for(c = 0; c <= max_c; c++) { for(b = 0; b <= max_b; b++) { for(a = 0; a <= max_a; a++) { if(o*o_wert + n*n_wert + m*m_wert + l*l_wert + k*k_wert + j*j_wert + i*i_wert + h*h_wert + g*g_wert + f*f_wert + e*e_wert + d*d_wert + c*c_wert + b*b_wert + a*a_wert > betrag) { } if(o*o_wert + n*n_wert + m*m_wert + l*l_wert + k*k_wert + j*j_wert + i*i_wert + h*h_wert + g*g_wert + f*f_wert + e*e_wert + d*d_wert + c*c_wert + b*b_wert + a*a_wert == betrag) { ergo = o*o_wert; ergn = n*n_wert; ergm = m*m_wert; ergl = l*l_wert; ergk = k*k_wert; ergj = j*j_wert; ergi = i*i_wert; ergh = h*h_wert; ergg = g*g_wert; ergf = f*f_wert; erge = e*e_wert; ergd = d*d_wert; ergc = c*c_wert; ergb = b*b_wert; erga = a*a_wert; //getchar(); //for(i=0; i<5; i++) //{ printf("%i \n%i \n%i \n%i \n%i \n%i \n%i \n%i \n%i \n%i \n%i \n%i \n%i \n%i \n%i \n", ergo, ergn, ergm, ergl, ergk, ergj, ergi, ergh, ergg, ergf, erge, ergd, ergc, ergb, erga); getchar(); //} } } } } } } } } } } } } } } } } return 0; }
-
lol
-
???
-
Hast Du es schon mal mit einem Buch versucht?
-
@codinglea
Wau! Einen Algorithmus mit der Komplexität von O(n^12) habe ich schon lange nicht mehr gesehen. Ist dein Betrag 50000, so berechnest du 50000*(50000/2)(50000/5)... = 50000^12/(1 * 2 * 5 * 10...) = 2.441410^21 = 2441406000000000000000 mal die Summe a * a_wert + .... Das ist etwas zuviel für jeden Rechner.Es heißt doch in der Aufgabe "Gib , wie beim Geldautomaten, eine Liste der 5 besten Kombinationen aus". Ei alla hopp, ich würde das als "Es gibt keinen 500€, 200€, 100€, 50€" Schein interpretieren. Und schon kannst du deinen Eingangscode wiederverwenden. Hauptsache du fängst bei der Berechnung immer mit dem größtmöglichen Schein/Geldstück an.
PS:
Hast du eine Ahnung wie grausam eine Verschachtelungstiefe von mehr als 5 ist, wenn man keinen Editor mit Syntax-Highlighting hat? Da sind Fehler vorprogrammiert.
-
@codinglea sagte in Wechselgeld 5 besten Kombinationen:
???
Das ist ja schlimmer, als ich annahm, meinte er damit.
Ich meld mich später, muss jetzt erst weg, du kannst mir auch eine PN schreiben.
-
@codinglea sagte in Wechselgeld 5 besten Kombinationen:
???
Naja das ist - ganz abgesehen davon dass es vermutlich relativ langsam sein wird - ein Paradebeispiel dafür was ich hier die ganze Zeit predige. Also nicht dafür wie man es machen sollte sondern wie man es nicht machen sollte.
ps: Aber es geht natürlich noch viel schlimmer. Also dein Code ist nicht "maximal schlimm" - nur "sehr schlimm"
-
Hauptsache du fängst bei der Berechnung immer mit dem größtmöglichen Schein/Geldstück an.
Naja, der Teil sollte schon hinhauen. Sie rechnet ja das Limit für alle möglichen Scheine getrennt aus. Aber es werden trotzdem viel zu viele Möglichkeiten gecheckt die man mit einem anderen Algorithmus früher ausschliessen könnte.
Dafür produziert der Algorithmus zumindest keine Duplikate.
-
@codinglea also
betragmuss einen wert zugewiesen bekommen- die breaks müssen wieder eingeführt werden, um unnötige berechnungen zu vermeiden, in der a-schleife befindet sich noch so eine überprüfung, die du an den anfang jeder schleife kopieren und dann um alle unnötigen berechnungen bereinigen kannst. also es geht darum, zu überprüfen, ob die summe aller bisherigen werte den betrag überschreitet und wenn dem so ist, braucht ja nicht weiter gerechnet zu werden. also wenn der betrag 15 sein soll, muss ja z.b. nicht überprüft werden, ob eine lösung mit 500er scheinen vorkommen könnte
- die anzahl der gefundenen lösungen muss gezählt werden und wenn die gewünschte anzahl der lösungen erreicht ist, muss die funktion beendet werden. das kannst du entweder erreichen, indem du direkt mit return aus der funktion aussteigst, oder indem du mittels sprunganweisung (goto, mach es ruhig mal) hinter die äußerste schleife springst.
- das getchar() muss raus
und dann sollte das erstmal funktionieren und du kannst dich damit beschäftigen, das programm zu verbessern.
-
@EinNutzer0
Was soll ich dir denn schreiben?
Und ich glaube, dass ich das noch gar nicht kann, weil ich zu neu bin.@hustbaer
"nur sehr schlimm" klingt auch schon blöd...
Wieso schickst du denn nicht mal ein Vorschlag, wie man es rekursiv macht?@Wade1234
Alles klar, ich bastel dann noch mal ein bisschen.
-
Wüsste sonst jemand, wie ich eine Funktion dafür aufstelle?
Mir ist klar, dass ich immer von der größtmöglichen Geldeinheit(z.B. bei 50€ der 50er Schein) -1 abziehen muss, sodass 2x20€ und 1x10€ usw entstehen. Das beste Ergebnis habe ich ja auch schon geschafft.
Ich brauche keine rekursive Lösung. Es würde mir reichen, wenn ich wenigstens wüsste, wie die Funktion aufgebaut wäre. Die Rekursion würde ich mir dann selber zurecht basteln.
mit dem Brute Force funktioniert es ja nur halbwegs...
Da gibt es anscheinend auch 4€ und 3€ Münzen.
-
Naja den jetzigen Code, ich hätte dann geholfen. Aber ich merke gerade, das ich auch keine PN schreiben kann.
schade.
-
@EinNutzer0
Ja, das ist echt schade...
-
@codinglea sagte in Wechselgeld 5 besten Kombinationen:
@EinNutzer0
Ja, das ist echt schade...Probier es jetzt einmal
-
@EinNutzer0
Geht leider immer noch nicht...
-
@codinglea sagte in Wechselgeld 5 besten Kombinationen:
@EinNutzer0
Geht leider immer noch nicht...Es gibt da eine Option unter Einstellungen, ich glaube Chat Nachrichten erlauben.
-
Geht leider trotzdem nicht.
-
Das ist ja auch nicht der Sinn dieses Forums, dass man per PN Lösungen versendet. Der Nächste, der dieses Problem hat, kann nicht von der Lösung profitieren, weil er sie nicht sieht.
Normalerweise sieht das so aus, dass TE die Aufgabenstellung mit seinem bisherigen Ansatz postet und Fragen dazu stellt. Daraufhin gibt es Denkanstösse oder Hinweise, wie man zur Lösung kommen kann oder die bisherige Lösung verbessern kann. Beides erfordert auf jeden Fall Arbeit des TE und soll TE dazu bringen, die Lösung selbst zu finden. Der Lerneffekt ist dann deutlich höher als bei einer fertigen Lösung, und TE ist danach hoffentlich in der Lage, ähnliche Probleme selbst zu lösen.Warum EinNutzer0 seine Lösung per PN schicken möchte könnte damit zusammenhängen, das seine bisherigen Vorschläge zerpflückt worden sind, aber das ist nur nur eine Vermutung
-
Dieser Beitrag wurde gelöscht!
