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 (2010 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 (2010 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")
1800740

Du scheinst einen AdBlocker zu nutzen. Ich würde mich freuen, wenn du ihn auf dieser Seite deaktivierst und dich davon überzeugst, dass die Werbung hier nicht störend ist.