Seite 1 von 1

Wechselgeld-Algorithmus aufstellen

Verfasst: Sonntag 4. Mai 2014, 13:02
von IT-Muslim
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.

Re: Wechselgeld-Algorithmus aufstellen

Verfasst: Sonntag 4. Mai 2014, 13:11
von Darii
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.

Re: Wechselgeld-Algorithmus aufstellen

Verfasst: Sonntag 4. Mai 2014, 13:47
von BlackJack
@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.

Re: Wechselgeld-Algorithmus aufstellen

Verfasst: Sonntag 4. Mai 2014, 14:25
von Hyperion
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.

Re: Wechselgeld-Algorithmus aufstellen

Verfasst: Sonntag 4. Mai 2014, 14:34
von BlackJack
@Hyperion: Ich denke das eine `int()` in der `main()`-Funktion sollte ein `float()` sein.

Re: Wechselgeld-Algorithmus aufstellen

Verfasst: Sonntag 4. Mai 2014, 14:37
von Hyperion
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

Re: Wechselgeld-Algorithmus aufstellen

Verfasst: Dienstag 6. Mai 2014, 09:40
von BlackJack
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.

Re: Wechselgeld-Algorithmus aufstellen

Verfasst: Dienstag 6. Mai 2014, 12:25
von pillmuncher
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'].