Python :: Aufgabe #224

4 Lösungen Lösungen öffentlich

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ß!

Lösungen:

vote_ok
von kamikatze (420 Punkte) - 02.07.2019 um 22:57 Uhr
Quellcode ausblenden 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))
1 Kommentar
vote_ok
von AlexGroeg (340 Punkte) - 28.11.2019 um 17:27 Uhr
Quellcode ausblenden 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))

vote_ok
von AlexGroeg (340 Punkte) - 04.12.2019 um 16:24 Uhr
Quellcode ausblenden 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))
vote_ok
von Moin (20 Punkte) - 25.02.2020 um 20:26 Uhr
Quellcode ausblenden 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")