hilfe hausaufgabe python

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.
frabron
User
Beiträge: 306
Registriert: Dienstag 31. März 2009, 14:36

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

@frabron: Das mit den 40€-Scheinen muss man nicht überprüfen, wenn man den Benutzer nur aus den vorhandenen Scheinen wählen lässt.
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

Verschönerungsvorschläge:

Ersetze

Code: Alles auswählen

    if betrag // schein:
durch

Code: Alles auswählen

    if betrag >= schein:
Ersetze

Code: Alles auswählen

scheine.reverse()
for schein in scheine:
durch

Code: Alles auswählen

for schein in reversed(scheine):
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:

Code: Alles auswählen

# Bankautomat
scheine = [5, 10, 20, 50, 100, 200, 500]
auszahlung = {}
betrag = int(raw_input('Wieviel soll ausgezahlt werden? '))
for schein in scheine:
    if betrag >= schein:
        auszahlung[schein] = 1
        betrag -= schein
    else:
        break
for schein in reversed(scheine):
    anzahl = betrag // schein
    if anzahl > 0:
        auszahlung[schein] += anzahl
        betrag -= schein * anzahl
print 'Ihre Auszahlung:'
for schein in sorted(auszahlung, reverse=True):
    print '%d * %d EUR' % (auszahlung[schein], schein)
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

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.
Das Leben ist wie ein Tennisball.
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

EyDu hat geschrieben:
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.)
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

@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.
Das Leben ist wie ein Tennisball.
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

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).
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

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.

Sebastian
Das Leben ist wie ein Tennisball.
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

OK, also zunächst halten wir mal fest:

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.

Puh, hoffentlich nicht vertippt...
Antworten