Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
$ ./cash_machine.py
Enter the requested money: 740
Please enter your PIN: 7249
+------+-----------------+
| Note | Number of Notes |
+======+=================+
| 500 | 1 |
+------+-----------------+
| 200 | 1 |
+------+-----------------+
| 20 | 2 |
+------+-----------------+
für die, die es nicht gemerkt haben: Ich habe bewusst schrecklichen Code geschrieben, indem ich unnötig Klassen verwendete und auf das Abfangen von Exceptions verzichtete.
@Dill:
Wow, der Code haut mich echt aus den Schuhen. Aber bevor ich mein Programm derartig ausbaue sollte ich vll zuerst "A Byte of Python" (dt. Übersetzung) weiterlesen.
Ich bin nämlich erst mit Kapitel 10 fertig
Übrigens, danke für das Kompliment
@snafu:
Das mit dem 'trenn' ist mir auch eingefallen. Mal schauen wie ich deinen Tipp einbauen kann.
Ich hab noch eine Idee für fortgeschrittene Programmierer. Am Bankautomaten kann man ja auswählen, welche Scheine man ausgezahlt bekommen will. Wie würde man denn das umsetzen?
Vll mit einer anfangs leeren scheine-Liste, danach können die einzelnen Scheine abgesegnet werden.
Ich würde die Wunschscheine in einer weiteren Liste sammeln und zuerst versuchen, den Betrag mit der Wunschliste zu bedienen. Einen evt. Restbetrag mit der orig. Scheinliste lösen. Dann müsste man noch kontrollieren, ob in der Wunschliste auch gültige Werte sind, d.h. keine 40€ scheine und so ...
Gerade weil scheine eine Liste ist, bei der es auf die Reihenfolge ankommt, würde ich sie nicht umsortieren, sondern im ganzen Programm gleich beibehalten. Ausserdem bedeutet dann "for schein in scheine:" nicht mal diese, mal jenes.
Und wenn man es ganz "pythonic" haben will, würde man vermutlich zum Zählen ein dict verwenden. Das gesamte Programm sähe dann so aus:
EyDu hat geschrieben:Wir haben aber beide noch Probleme mit beliebigen Scheinen. Angenommn wir haben die Beträge 7 und 5 und möchten 10 Euro abheben, dann werden wir nur 7 bekommen. Vielleicht sollten wir also die Vorraussetzung beibehalten, dass jeder Schein durch eine Kombination der kleineren Scheine konstruiert werden kann (wirklich ausreichende Bedingung?).
Für Konfigurationen aus zwei Scheinen, welche die Bedingung nicht erfüllen, lässt sich recht einfach zeigen, dass es immer einen Wert gibt, welcher auszahlbar ist aber nicht ausgezahlt wird. Vielleicht finde ich noch Zeit um mal einen Blick auf beliebig große Konfigurationen zu werfen.
Wenn jemand den Beweis möchte stelle ich ihn gerne online.
EyDu hat geschrieben:Wir haben aber beide noch Probleme mit beliebigen Scheinen. Angenommn wir haben die Beträge 7 und 5 und möchten 10 Euro abheben, dann werden wir nur 7 bekommen. Vielleicht sollten wir also die Vorraussetzung beibehalten, dass jeder Schein durch eine Kombination der kleineren Scheine konstruiert werden kann (wirklich ausreichende Bedingung?).
Für Konfigurationen aus zwei Scheinen, welche die Bedingung nicht erfüllen, lässt sich recht einfach zeigen, dass es immer einen Wert gibt, welcher auszahlbar ist aber nicht ausgezahlt wird. Vielleicht finde ich noch Zeit um mal einen Blick auf beliebig große Konfigurationen zu werfen.
Wenn jemand den Beweis möchte stelle ich ihn gerne online.
Die Bedingung "Jeder Schein kann durch eine Kombination der kleineren Scheine konstruiert werden" bedeutet, dass alle Scheine Vielfache des kleinsten sind.
Es reicht aber als Bedingung, wenn zu jedem Schein S das kleinste Vielfache V(S) des kleinstens Scheins s, das mindestens so groß wie S ist, vorhanden ist. (Damit kann S nur zur Auszahlung kommen, wenn S selbst ein Vielfaches von s ist, weil der Restbetrag immer ein Vielfaches von s ist.)
Wenn es einen Schein S gibt, der kein Vielfaches von s ist, wird V(S) nicht ausgezahlt, weil zunächst S ausgegeben wird, und der Rest kleiner als jeder Schein ist - aber positiv.
"Lustiger" Effekt: Die nicht-vielfachen Scheine werden nie ausgegeben.
Annahme dabei: Es wird stets der größtmögliche Schein ausgezahlt. (Bei der Hausfrauenmischung muss man evtl. noch die Summe aller Scheine dazuzählen.)
@bords0: es wäre gut, wenn du noch dazu schreiben würdes, was du zeigen möchtest.
bords0 hat geschrieben:Es reicht aber als Bedingung, wenn zu jedem Schein S das kleinste Vielfache V(S) des kleinstens Scheins s, das mindestens so groß wie S ist, vorhanden ist. (Damit kann S nur zur Auszahlung kommen, wenn S selbst ein Vielfaches von s ist, weil der Restbetrag immer ein Vielfaches von s ist.)
Das kgV von was genau meinst du hier? kgV(S, s)? Dann wäre auch {14, 7, 10, 5, 2} eine gültige Konfiguration, welche bei dem Betrag 20 scheitern würde.
EyDu hat geschrieben:@bords0: es wäre gut, wenn du noch dazu schreiben würdes, was du zeigen möchtest.
Äh, ja, das ging mir mit deinem Beitrag davor genauso, deshalb habe ich angenommen, dass es jeder außer mir wüsste...
Die Frage ist, bei welchen Scheingrößen jedes Vielfache des kleinsten Scheins asugezahlt wird, wenn immer der größtmögliche Schein ausgezahlt wird, der den Restbetrag nicht übersteigt.
EyDu hat geschrieben:
bords0 hat geschrieben:Es reicht aber als Bedingung, wenn zu jedem Schein S das kleinste Vielfache V(S) des kleinstens Scheins s, das mindestens so groß wie S ist, vorhanden ist. (Damit kann S nur zur Auszahlung kommen, wenn S selbst ein Vielfaches von s ist, weil der Restbetrag immer ein Vielfaches von s ist.)
Das kgV von was genau meinst du hier?
Überhaupt keins. Ein Vielfaches von s, aber (i.A.) nicht ein gemeinsames. Im deinem Beispiel [2, 5, 7, 10, 14] wären z.B. V(5)=6, V(7)=8, V(10)=10, V(14)=14. Es würden also 6 und 8 als Scheine "fehlen", und 6 und 8 werden nicht ausgezahlt (weil zuerst 5 bzw. 7 ausgezahlt werden und dann nur noch der Betrag 1 übrigbleibt, der nicht ausgezahlt werden kann, weil er kleiner als s (=2) ist).
Da haben wir wohl beide angenommen, dass die anderen schon verstehen würde was man meint ^^
Wie ich das kleinste gemeinsame Vielfache da rein interpretiert habe, habe ich selbst noch nicht ganz verstanden. Bei "Vielfaches" ist es mir wahrscheinlich in den Sinn gekommen und ich bin es nicht mehr losgeworden.
Also noch einmal zum Beispiel: aus meinem Vorschlag {2, 5, 7, 10, 14} müsste nun also durch V(5)=6 und V(7)=8 die neue Menge M={2, 5, 6, 7, 8, 10, 14} folgen und deine genannte Bedingung erfüllen.
Das würde nun allerdings in einem Problem beim Betrag 23=10+6+7 enden, da die Auszahlung in der Reihenfolge 14, 8 durchgeführt werden würde.
Vielleicht vorweg, nicht dass wir an einander vorbei reden: das man mit deinem Verfahren alle Vielfachen des kleinsten Betrag auszahlen kann sieht man sofort. So habe ich auch meinen Beweise geführt, dass bei zwei Zahlen, bei der die eine nicht das Vielfache der anderen ist, keine Konfiguration möglich ist, in der alle (validen) Beträge korrekt ausgegeben werden. Ich konstruiere also wie du immer einen ungültigen Betrag.
Mir geht es aber um den allgemeinen Fall. Wie man an Hand der Menge M (in diesem Post) sieht, sind auch valide Beträge möglich, welche kein Vielfaches des kleinsten Wertes sind. Oder noch einmal zusammengefasst: existiert eine Konfiguration, bei der nicht alle Scheine ein Vielfaches des kleinsten Scheins sind und trotzdem alle validen Beträge ausgegeben werden können.
Das Verfahren der (versuchten) Auszahlung ist, immer den größten Schein, der kleiner als der Restbetrag ist, auszuzahlen, bis dies nicht mehr möglich ist. Die Frage ist, ob alle zugelassenen Auszahlungsbeträge nach diesem Verfahren auch tatsächlich ausgezahlt werden.
1. Sind als auszuzahlender Betrag nur Vielfache des kleinsten Scheines zugelassen, ist ja schon geklärt, welche Scheinwertmengen stets die Auszahlung ermöglichen: Genau dann, wenn mit jedem Scheinwert S auch das kleinste Vielfache V(S) des kleinsten Scheinwertes s, der größer gleich S ist, als Scheinwert vorhanden ist, klappt es immer. (Allerdings werden dann auch immer nur Scheine ausgegeben, die Vielfache von s sind.)
2. Sind als auszuzahlender Betrag beliebige Linearkombinationen (mit nichtnegativen Koeffizienten) der Scheinwerte zugelassen, ist es etwas komplizierter. Ergebnis: Wenn nicht alle Scheine Vielfache des kleinsten Scheines sind, geht es nicht (mit endlichen Scheinwertmengen).
Als erstes überlegt man sich, dass für Scheinwertemengen, die stets auszahlen können, folgendes gilt: Mit zwei Scheinwerten S und T, für die S < T < S + s gilt, muss auch immer S + s ein Scheinwert sein. Beweis: Ansonsten kann S + s nicht ausgezahlt werden, weil der Restbetrag nach dem ersten ausgezahlten Schein kleiner als s ist.
Das gleiche Argument gilt nun auch für T < S + s < T + s, so dass auch T + s ein vorhandener Scheinwert sein muss. Und dann auch S + 2 * s, T + 2 * s usw. usf.
Sei nun S wieder ein beliebiger vorhandener Scheinwert, der aber kein Vielfaches von s sei. Dann ist S < V(S) < S + s. Da V(s) ein Scheinwert sein muss (da sonst beim Betrag V(s) sonst nach einer Auszahlung ein positiver Restbetrag < s vorhanden wäre), muss es nach dem obigen Argument unendlich viele Scheinwerte geben.
Übrigens genügt (bei unendlichen Scheinwertemengen) die obige Bedingung nicht, dass mit S < T < S + s auch S + s ein Scheinwert ist. Vielmehr muss offensichtlich noch für jeden Scheinwert S, der kein Vielfaches von s ist, jeder zugelassene Betrag b mit S < b < S + s ein Scheinwert sein.
Beispiel: Sind 3 und 7 die beiden kleinsten Scheinwerte, so muss zwingend auch 9 Scheinwert sein (zulässig als 3 + 3 + 3), damit auch 10 (7 < 9 < 7 + 3 = 10 = V(7)), damit auch 12 (zugelassen als 3 + 3 + 3 +3), damit auch 13 (10 < 12 < 10 + 3 = 13 = V(10)), damit auch 14 und 15 (zugelassen als 7 + 7 bzw. als 3 + 3 + 3 + 3 + 3) und damit offensichtlich auch alle größeren natürlichen Zahlen. Insgesamt also mindestens {3, 7, 9, 10, 12, 13, 14, 15, ...}
Es gilt sogar allgemein, dass dann stets fast alle (also alle bis auf endlich viele) Vielfache des ggT aller Scheinwerte ebenfalls Scheinwerte sind.
Die beiden oben genannten notwendigen Bedingungen sind sogar hinreichend, da die Intervalle (S, S + s], (S + s, S + 2 * s], ... abgedeckt sind, und damit alle Zahlen über S. Für Beträge unter S spielt es aber keine Rolle, dass auch S ein Scheinwert ist.
