1 Euro Rätsel
-
Hallo Leute,
ich habe vor ein paar Tagen ein Rätsel im Radio gehört: auf wieviel Arten kann man 1 Euro auszahlen? Zugelassen sind: 1, 2, 5, 10, 20, 50, 100 Cent Stücke.
Ich habe es per Bruteforce geknackt. An der Zahl bin ich also nicht unbedingt interessiert. Gibt es vielleicht einen etwas mehr mathematischen Lösungsweg?
-
Euristiker schrieb:
Ich habe es per Bruteforce geknackt. An der Zahl bin ich also nicht unbedingt interessiert. Gibt es vielleicht einen etwas mehr mathematischen Lösungsweg?
bruteforce IST zu 100% mathematisch. was soll die frage?
-
Bruteforce ist nur das Dumpfe ausprobieren von 100*50*20*10*5*2*1 Möglichkeiten. Eine mathematische Lösung wäre ein schematischer Lösungsanzatz.
Hab eben mal ein bischen gegoogelt. Ist es das Rucksackprobelm? http://de.wikipedia.org/wiki/Rucksackproblem
100 1 Cent Stücke, 50 2 Cent, ...
-
Ich würds mit einer rekursiven Funktion machen, die die Möglichkeiten, n Cents zu unterteilen, berechnet. Sie zieht nacheinander alle Münzwerte ab (solange es passt natürlich nur) und berechnet jeweils wieder alle Möglichkeiten, die Differenz -- unter Benutzung höchstens genauso großer Münzen wie bereits abgezogen wurden -- zu partitionieren. 0 kann nicht weiter unterteilt werden und entspricht daher einer Zerlegungsmöglichkeit (als Optimierung könnte man auch bei 1 aufhören, weil 1 das kleinste Stück ist). Dann rechnet man alles zusammen und fertig.
Ist natürlich auch ne Art Brute Force, aber nicht ganz so Dumm wie 100*50*20*10*5*2*1 Möglichkeiten durchzuprobieren
-
Euristiker schrieb:
Bruteforce ist nur das Dumpfe ausprobieren von 100*50*20*10*5*2*1 Möglichkeiten. Eine mathematische Lösung wäre ein schematischer Lösungsanzatz.
dumpfes probieren ist kein schematischer ansatz?
ihr sprecht in rätseln, mein freund.und 100*50*... halte ich für gewagt.
101*51*21*11*6*3*2 halte ich für viel durchdachter.ich vermute, man kann es auf einem A4-blatt ohne rechner (afaik aka computer, imho wollte Ruhollah das mal readen, ack?) berechnen.
-
Hallo Bashar: Du würdest also die Funktion mit 100 Cent aufrufen und dann 1 Cent abziehen und dann rekursiv aufrufen. Nachdem die Rekursion beendet ist 2 Cent abziehen und wieder rekursieren... so ganz habe ich es nicht verstanden. Aber so wie ich es oben beschrieben habe wäre es etwas anderes wenn ich zuerst 98 1Cent Stücke auszahle und dann ein 2Cent Stück auszahle oder andersrum. Da der Radiomoderator natürlich kein Mathematiker war hat er dazu nichts gesagt.
Zählt aber vermutlich als eine Möglichkeit.@Volkard: Du meinst weil man auch 0 1Cent Stücke auszahlen kann. Hast Recht;-)
-
Euristiker schrieb:
Hallo Bashar: Du würdest also die Funktion mit 100 Cent aufrufen und dann 1 Cent abziehen und dann rekursiv aufrufen. Nachdem die Rekursion beendet ist 2 Cent abziehen und wieder rekursieren... so ganz habe ich es nicht verstanden.
Ja, in der Basisversion schon. Man könnte aber auch hier als Optimierung feststellen, dass es für n Cent in Einern aufgeteilt nur eine Zerlegung gibt und einfach 1 zurückgeben. Das ändert aber am Ergebnis nichts, und ich wollte es erstmal einfach halten.
Aber so wie ich es oben beschrieben habe wäre es etwas anderes wenn ich zuerst 98 1Cent Stücke auszahle und dann ein 2Cent Stück auszahle oder andersrum. Da der Radiomoderator natürlich kein Mathematiker war hat er dazu nichts gesagt.
Zählt aber vermutlich als eine Möglichkeit.Ich versteh nicht ganz, worauf du hinauswillst. In meiner Lösung spielt Reihenfolge keine Rolle, was mir auch als das sinnvollste erscheint.
Edit:
Man sollte vielleicht Zwischenergebnisse abspeichern, damit man nicht 10000mal wieder berechnen muss, wie man 20 in 5ern, 2ern und 1ern zerlegt.
-
Bashar schrieb:
Edit:
Man sollte vielleicht Zwischenergebnisse abspeichern, damit man nicht 10000mal wieder berechnen muss, wie man 20 in 5ern, 2ern und 1ern zerlegt.jo.
und vielleicht be 1-cent anfangen.
für 1-cent alle 101 möglichkeiten.
von denen nur die mit 2-cent dazu, wenn die summe durch 5 teilbar istm, weil nur das mit den größeren aufgefüllt werden kann.
mit 5-ern nur die nehmen, die in summe duch 10 teilbar sind.
evtl wird das was, ka.#
-
-
was ist denn die lösung?
-
Müßt Euch bis morgen gedulden. War aber sowas wie 4623. Kann den Code auch mal posten...
@Bashar: Ich wollte auf die Reichenfolge hinaus. Hatte Deine Lösung zuerst nicht verstanden.
-
@Surftipp: Die Aufgabe allgemein zu lösen ist dann wohl doch ein bischen härter.
-
jep das gheht ueber ne rekursion
mein prof hat mal ne * aufageb gestellt und zwar
wieviele kombinationen gibt es einen betrag mit 2,1,5 cent stuecken zu bezahlen
war nur leider nicht anwesend als er die leosung vorgestellt hatte geschweige denn sie gefunden zu haben
-
Die unoptimierte Basisversion:
#include <iostream> int muenzwerte[] = { 1, 2, 5, 10, 20, 50, 100 }; int zerlegungen(int betrag, int max_muenze) { if (betrag == 0) return 1; else if (betrag < 0) return 0; else { int zaehler = 0, i = max_muenze; while (true) { zaehler += zerlegungen(betrag - muenzwerte[i], i); if (i == 0) break; --i; } return zaehler; } } int main() { std::cout << "100 Cent können auf " << zerlegungen(100, 6) << " Arten zerlegt werden." << std::endl; }Gewinnt keinen Schönheitspreis, hat aber nicht lange gedauert und läuft im Millisekundenbereich.
-
int main(int argc, char* argv[]) { int c1, c2, c5, c10, c20, c50, ergebnis; c1=0; c2=2; c5=0; c10=0; c20=0; c50=0; ergebnis=0; /* Es werden ALLE möglichen Kombinationen durchgegangen. */ do { c1++; if (c1>100) { c1=0; c2++; if (c2>50) { c2=0; c5++; if (c5>20) { c5=0; c10++; if (c10>10) { c10=0; c20++; if (c20>5) { c20=0; c50++; } } } } } if (c1 + 2*c2 + 5*c5 + 10*c10 + 20*c20 + 50*c50 == 100) ergebnis++; } while (c50<2); ergebnis++; // + eine 100 Cent Stück Kombination. printf("%d", ergebnis); return 0; }Es sollte eigentlich 4563 rauskommen. Kommt aber nur 4561 raus
-
Hi,
die Frage war sehr interessant und interessante Fragen werden
hier
immer sehr freundlich und kompetent bearbeitet. Insbesondere auch
diese (siehe insb.[18]).Jockel