Wechselgeld-Algorithmus aufstellen

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.
Antworten
IT-Muslim
User
Beiträge: 1
Registriert: Sonntag 4. Mai 2014, 12:45

Sonntag 4. Mai 2014, 13:02

Hallo liebe Leute,

ich bin neu im Programmieren und benötige ein wenig Hilfestellung. Die Aufgabe ist folgende:

Gesucht wird ein Algorithmus zur Wechselgeldrückgabe. Zu wechseln ist ein Betrag von x
Cent. Es stehen dazu genügend Münzen im Wert von 1, 2, 5, 10, 20, 50 Cent und 1 Euro
zur Verfügung. Ziel ist es, mit möglichst wenigen Münzen auszukommen.
Beispiel: 57 CentWechselgeld lassen sich mit drei Münzen ausgeben: eine 50-Cent-Münze,
eine 5-Cent-Münze und eine 2-Cent-Münze
(a) Geben Sie einen Algorithmus in Python- oder Java-Code für dieses Problem an.

Meine Lösung:

Code: Alles auswählen

Wechselgeld = input("Geldbetrag in Euro: ")
wechselgeld = int(100)

100 = wechselgeld/100
wechselgeld = Wechselgeld/100

50 = wechselgeld/50
wechselgeld = wechselgeld % 50

20 = wechselgeld/20
wechselgeld = wechselgeld % 20

10 = wechselgeld/10
wechselgeld = wechselgeld % 10

5 = wechselgeld/5
wechselgeld = wechselgeld % 5

2 = wechselgeld/2
wechselgeld = wechselgeld % 2

1 = wechselgeld/1
wechselgeld = wechselgeld % 2

print("Der Betrag setzt sich zusammen aus: ")
print(100, "mal 100 Cent)
print(50, "mal 50 Cent)
print(20, "mal 20 Cent)
print(10, "mal 10 Cent)
print(5, "mal 5 Cent)
print(2, "mal 2 Cent)
print(1, "mal 1 Cent)
Ist das so jetzt richtig? Ich bitte um Hilfe und danke euch.
Zuletzt geändert von Hyperion am Sonntag 4. Mai 2014, 13:11, insgesamt 1-mal geändert.
Grund: Code in Python-Code-Tags gesetzt.
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Sonntag 4. Mai 2014, 13:11

Hast du denn mal versucht das Programm auszuführen und die Fehlermeldungen zu beseitigen? Und bitte Python code in

Code: Alles auswählen

-Tags setzen.
BlackJack

Sonntag 4. Mai 2014, 13:47

@IT-Muslim: Es könnte auch helfen den Algorithmus in Worte zu fassen, also präzise zu beschreiben wie *Du* vorgehen würdest, wenn Du einen bestimmten Betrag mit möglichst wenig Münzen zusammenstellen sollst. Möglichst so, dass die Beschreibung als Handlungsanweisung für jemand anderen verwendbar ist. Denn das ist ja letztendlich ein Algorithmus: Eine Handlungsanweisung an jemand anderen. Ziel in diesem Fall ist eine in Python (oder Java) formulierte Anweisung an den Rechner.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7477
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Sonntag 4. Mai 2014, 14:25

Ich würde Dir empfehlen, das ganze in einer Funktion zu kapseln, nennen wir sie ``calc_change`` (oder zur Not ``berechne_Wechselgeld``, wenn es denn Deutsch sein muss). Du speicherst diese Funktion einfach in einer Datei Namens `` change.py``. Dann sieht Dein Modul ``change`` nun so aus:

Code: Alles auswählen

COINS = (1, 2, 5, 10, 20, 50, 100, 200)

def calc_change(money, coins=COINS):
    pass
Da ich immer mit fixen Münzen rechnen will, definiere ich einfach ein Modul-globales Tupel mit den vorgegebenen Münzen. Dieses übergebe ich der Funktion als Default-Parameter, damit ich den Wert nicht bei jedem Aufruf angeben muss. Ich kann sie aber auch mit einem anderen Portfolio aus Münzen aufrufen kann - wenn ich das denn einmal will.

Nun schreibe ich einfach mal ein Stück Code, welches testet, ob beim Aufruf der Funktion mit 57 Cent wirklich 1x 50, 1x 5 und 1x 2 Cents zurückgegeben werden:

Code: Alles auswählen

def test_calc_change_with_57_cents_returns_50_5_2_cent_coins():
    result = calc_change(57)
    assert result == [50, 5, 2]
Nun ergänze ich obige Funktion noch so, dass ich das als ein lauffähiges Testprogramm ausführen kann:

Code: Alles auswählen

#!/usr/bin/env python

from calc_change import calc_change

def test_calc_change_with_57_cents_returns_50_5_2_cent_coins():
    result = calc_change(57)
    assert result == [50, 5, 2]

def main():
    try:
        test_calc_change_with_57_cents_returns_50_5_2_cent_coins()
        print("Test erfolgreich!")
    except AssertionError:
        print("Failed!")

if __name__ == "__main__":
    main()
Das ``assert`` Statement in Python bewirkt, dass eine ``AssertException`` geworfen wird, sofern die Bedingung nach der Anweisung ``False`` ergibt. Dies mache ich mir zu Nutze und fange die Exception beim Aufruf der Testfunktion einfach ab. Tritt eine Exception auf, weiß ich, dass der Test fehlgeschlagen ist, wenn nicht, weiß ich, dass er erfolgreich war.

Wenn ich nun mein Testprogramm ausführe, so muss ich "Failed!" lesen, da ich die Funktion noch nicht richtig implementiert habe. Nun kann ich mich an die Implementierung der Funktion machen und immer mal wieder prüfen, ob ich sie denn vollständig implementiert habe. Sobald ich die Erfolgsmeldung sehe, weiß ich, dass die Funktion so funktioniert, wie ich mir das vorgestellt (und durch einen Test abgesichert!) habe.

Der Vorteil davon ist, dass ich nicht jdes Mal *manuell* irgend welche Zahlen eingeben muss, um zu testen, ob mein Algorithmus funktioniert :-)

Dies nennt man "Test Driven Development" (TDD).

Ein Glück bietet Python bereits fertige Module dafür an, so dass ich den ganzen Overhead für die Auswertung nicht selber schreiben muss. Ich habe für das Problem mal mit pytest einige Test geschrieben, die auch einen Randfall abdecken, sowie die Konstellation, dass eine Münze mehrfach in der Lösung vorkommt:

Code: Alles auswählen

#!/usr/bin/env python

from change import calc_change

def test_calc_change_with_57_cents_returns_50_5_2_cent_coins():
    result = calc_change(57)
    assert result == [50, 5, 2]

def test_calc_change_with_0_cents_returns_empty_list():
    result = calc_change(0)
    assert result == []

def test_calc_change_with_44_cents_returns_20_20_2_2_cent_coins():
    result = calc_change(44)
    assert result == [20, 20, 2, 2]
Wenn ich das ohne Implementierung der ``calc_change``-Funktion aufrufe erhalte ich folgende Ausgabe:

Code: Alles auswählen

1 nelson@vitory ~/Source/Python/Snipptes/Forum/change % py.test unit_tests.py 
======================================= test session starts ========================================
platform linux -- Python 3.4.0 -- py-1.4.20 -- pytest-2.5.2
plugins: cov
collected 3 items 

unit_tests.py FFF

============================================= FAILURES =============================================
_____________________ test_calc_change_with_57_cents_returns_50_5_2_cent_coins _____________________

    def test_calc_change_with_57_cents_returns_50_5_2_cent_coins():
        result = calc_change(57)
>       assert result == [50, 5, 2]
E       assert None == [50, 5, 2]

unit_tests.py:8: AssertionError
________________________ test_calc_change_with_0_cents_returns_empty_tuple _________________________

    def test_calc_change_with_0_cents_returns_empty_tuple():
        result = calc_change(0)
>       assert result == []
E       assert None == []

unit_tests.py:13: AssertionError
___________________ test_calc_change_with_44_cents_returns_20_20_2_2_cent_coins ____________________

    def test_calc_change_with_44_cents_returns_20_20_2_2_cent_coins():
        result = calc_change(44)
>       assert result == [20, 20, 2, 2]
E       assert None == [20, 20, 2, 2]

unit_tests.py:18: AssertionError
===================================== 3 failed in 0.02 seconds =====================================
In den drei Zeilen, die mit "E" beginnen sehe ich, was ``result`` tatsächlich war. In meinem Falle immer ``None``, da die Funktion ja nichts (also ``None``) zurückliefert, egal, was ich als Parameter übergebe.

Nachdem ich die Funktion implementiert habe, sehe ich folgende Ausgabe:

Code: Alles auswählen

1 nelson@vitory ~/Source/Python/Snipptes/Forum/change % py.test unit_tests.py                    :(
======================================= test session starts ========================================
platform linux -- Python 3.4.0 -- py-1.4.20 -- pytest-2.5.2
plugins: cov
collected 3 items 

unit_tests.py ...

===================================== 3 passed in 0.01 seconds =====================================
Alle drei Tests sind erfolgreich durchgelaufen :-)

Man kann sich nun noch mehr Tests überlegen, etwa für den Fall, dass man ein leeres Münztupel übergibt oder dass man einen negativen Betrag übergibt usw. Damit kann man seine Funktion immer robuster machen und sicher stellen, dass man an alles gedacht hat.

Ein großer Vorteil von solchen automatisierten Tests (in diesem Falle sogar tatsächliche Unit-Tests) ist auch, dass ich quasi nach jeder Zeile Code, die ich schreibe, den Test erneut aufrufen kann und somit *ohne* manuelle Eingaben *alle* bis dato erdachten Szenarien durchtesten kann.

Zum Schluss kannst Du das Modul ``change`` noch zu einem lauffähigen Programm erweitern, indem Du folgende Zeilen ergänzt:

Code: Alles auswählen

def main():
    money = int(int(input("Geldbetrag in Euro: ")) * 100)
    change = calc_change(money)
    print("Der Betrag setzt sich zusammen aus: ", str(change))

if __name__ == "__main__":
    main()
Die Ausgabe kann man natürlich noch aufhübschen ;-)

Du kannst natürlich auch im nachhinein Tests für Deine Funktion schreiben. Ich würde Dir das wirklich nahelegen.
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
BlackJack

Sonntag 4. Mai 2014, 14:34

@Hyperion: Ich denke das eine `int()` in der `main()`-Funktion sollte ein `float()` sein.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7477
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Sonntag 4. Mai 2014, 14:37

Oops, ja klar... so muss es aussehen:

Code: Alles auswählen

money = int(float(input("Geldbetrag in Euro: ")) * 100)
Das sollte man wohl eh sinnvoller Weise auch in eine Funktion ``convert_to_cents`` oder so auslagern :-D
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
BlackJack

Dienstag 6. Mai 2014, 09:40

Eine Lösung in MIPS-Assembler (für den SPIM-Emulator):

Code: Alles auswählen

        .rdata
# Values of EUR coins in descending order.
coin_values:
        .byte 200, 100, 50, 20, 10, 5, 2, 1

ask_amount_txt:
        .asciiz "Amount of change in cents: "
done_txt:
        .asciiz "\ndone.\n"

        .text
# 
# In:   $a0 - argc
#       $a1 - &argv
#       $a2 - &env
#
# Uses: $t0 - current amount of change in cents.
#       $t1 - pointer into the `coin_values` array.
#       $t2 - current coin value.
# 
        .globl main
main:
        li      $v0, 4                  # print_str
        la      $a0, ask_amount_txt
        syscall

        li      $v0, 5                  # $t0 = read_int();
        syscall
        move    $t0, $v0

        la      $t1, coin_values        # Initialise coin value pointer.
change_loop:
        beqz    $t0, change_loop_end    # If no change, then exit loop.

        lbu     $t2, ($t1)              # Load coin value from array.
        add     $t1, 1                  # Move coin value pointer to next value.
        div     $t0, $t2                # $lo, $hi = divmod($t0, $t2);

        mflo    $a0                     # Move division result to $a0.
        beqz    $a0, change_loop        # If no coin, skip printing of coin.

        mfhi    $t0                     # Move remainder to current amount.

        li      $v0, 1                  # Print <count> x <coin value> <space>.
        syscall
        li      $v0, 11
        li      $a0, 'x'
        syscall
        li      $v0, 1
        move    $a0, $t2
        syscall
        li      $v0, 11
        li      $a0, ' '
        syscall

        b       change_loop
change_loop_end:
        
        li      $v0, 4                  # print_str
        la      $a0, done_txt
        syscall

        j       $ra
        nop
Testläufe:

Code: Alles auswählen

Amount of change in cents: 57
1x50 1x5 1x2 
done.
Amount of change in cents: 0

done.
Amount of change in cents: 42
2x20 1x2 
done.
Benutzeravatar
pillmuncher
User
Beiträge: 1165
Registriert: Samstag 21. März 2009, 22:59
Wohnort: München

Dienstag 6. Mai 2014, 12:25

SWI-Prolog:

Code: Alles auswählen

coin('1 Euro', 100).
coin('50 Cent', 50).
coin('20 Cent', 20).
coin('10 Cent', 10).
coin('5 Cent', 5).
coin('2 Cent', 2).
coin('1 Cent', 1).

change(0, []) :- !.
change(Amount, [Coin|Coins]) :-
    coin(Coin, Cents), Rest is Amount - Cents, Rest >= 0, !,
    change(Rest, Coins).
Ergebnis:

Code: Alles auswählen

?- change(57, V).
V = ['50 Cent', '5 Cent', '2 Cent'].

?- change(157, V).
V = ['1 Euro', '50 Cent', '5 Cent', '2 Cent'].

?- change(257, V).
V = ['1 Euro', '1 Euro', '50 Cent', '5 Cent', '2 Cent'].

?- change(297, V).
V = ['1 Euro', '1 Euro', '50 Cent', '20 Cent', '20 Cent', '5 Cent', '2 Cent'].

?- change(298, V).
V = ['1 Euro', '1 Euro', '50 Cent', '20 Cent', '20 Cent', '5 Cent', '2 Cent', '1 Cent'].
Oder endrekursiv mit Accelerator:

Code: Alles auswählen

change(In, Out) :- change(In, [], Out).

change(0, Acc, Acc) :- !.
change(Amount, Acc, Coins) :-
    coin(Face, Cents), Rest is Amount - Cents, Rest >= 0, !,
    change(Rest, [Face|Acc], Coins).
Das Ergebnis ist dann in umgekehrter Reihenfolge:

Code: Alles auswählen

?- change(298, V).
V = ['1 Cent', '2 Cent', '5 Cent', '20 Cent', '20 Cent', '50 Cent', '1 Euro', '1 Euro'].
In specifications, Murphy's Law supersedes Ohm's.
Antworten