Python :: Aufgabe #224
4 Lösungen
Begleichung einer Rechnung ausschließlich mit Münzen
Anfänger - Python
von hollst
- 02.05.2019 um 15:46 Uhr
Angenommen, ihr hättet an der Kasse einen Betrag X zwischen (einschließlich) einem Cent und einem Euro zu bezahlen.
Schreibe ein Program, dass die Anzahl der Möglichkeiten berechnet, X ausschließlich mit 1, 2, 5 und 10 Cent-Münzen zu begleichen.
Beispiel: X = 5 Cent -> 4 Möglichkeiten (5; 2 + 2 + 1; 2 + 1 + 1+ 1; 1 + 1 + 1 + 1 + 1)
Achtung: für einen EURO (100 Cent) gibt es bereits 2.156 Möglichkeiten!
Viel Spaß!
Schreibe ein Program, dass die Anzahl der Möglichkeiten berechnet, X ausschließlich mit 1, 2, 5 und 10 Cent-Münzen zu begleichen.
Beispiel: X = 5 Cent -> 4 Möglichkeiten (5; 2 + 2 + 1; 2 + 1 + 1+ 1; 1 + 1 + 1 + 1 + 1)
Achtung: für einen EURO (100 Cent) gibt es bereits 2.156 Möglichkeiten!
Viel Spaß!
Lösungen:
Python-Code
import itertools menge = 1 anzahl = 0 for menge in range(1,101): for i in list(itertools.combinations_with_replacement([1, 2, 5, 10], menge)): if sum(i) == 100: anzahl += 1 print("Es gibt {} Lösungen".format(anzahl))
Python-Code
cent = 100 d = [cent] lc = [10, 5, 2, 1] kombinationen = [] n = 0 def kombi(li,c): ko = [] for e in li: while e <= c: ko.append(e) c -= e return ko def xxx(d): global n global cent p = d[:] p.reverse() e = p[n] if e > 1: i = lc.index(e) + 1 p.remove(e) for j in range(2): p.append(lc[i]) if sum(p) < cent: p.append(1) sr(p) if p not in kombinationen: kombinationen.append(p) xxx(p) sr(p) if e == 1 : if n < len(p)-1: n += 1 xxx(p) def sr(s): s.sort(); s.reverse() # Start d = kombi(lc,cent) kombinationen.append(d) xxx(d) # Fehlende hinzufügen sr(kombinationen) for e in kombinationen: if len(e) > 1: p = e[:] if (p[-1] == 1 and p[-2] == 1) : del p[-1]; del p[-1] p.append(2) sr(p) if p not in kombinationen: if sum(p) == cent: kombinationen.append(p) sr(kombinationen) for e in kombinationen: if len(e) > 1: p = e[:] if (p[0] > p[1] and p[1] != 1 and p[2] == 1): del p[1] p.append(1); p.append(1) sr(p) if p not in kombinationen: if sum(p) == cent: kombinationen.append(p) sr(kombinationen) if kombinationen[-1][0] == 2: p = kombinationen[-1][:] del p[0] p.append(1); p.append(1) sr(p) kombinationen.append(p) # Doppelte ausfiltern k = [] for e in kombinationen: if e not in k: k.append(e) # Ausgabe sr(k) for e in k: print(e) print('Anzahl der Kombinationen:', len(k))
Python-Code
import itertools muenzen = [1, 2, 5, 10] cent = 5 anzahl = 0 for menge in range(1, cent +1): for i in list(itertools.combinations_with_replacement(muenzen, menge)): if sum(i) == cent: print(i) anzahl += 1 print("Es gibt {} Lösungen.".format(anzahl))
Python-Code
x = int(input("Welche Zahl soll gebildet werden?")) #Eingabe der Zahl, die gebildet werden soll a = [] #Die Liste, die darstellt, aus welchen Münzwerten wir x bilden i = 0 #Der Counter für die Anzahl der gefundenen Möglichkeiten for b in range(0,((x//10)+1)): #Wir gehen von Grund auf (also von 1 aufwärts bis 10) alle Möglichkeiten durch for c in range(0,((x//5)+1)): #Das +1 ist dazu da, eine range(0,0) zu verhindern für x<10; die Gleichheitsabfrage weiter unten verhindert zusätzliche Zählungen dadurch for d in range(0,((x//2)+1)): a.append(b*10) a.append(c*5) a.append(d*2) while sum(a) < x: a.append(1) if sum(a) == x: i += 1 a = [] print("Für die Zahl ", x , " gibt es ", i , " Möglichkeiten") input("Gern geschehen")