Kombinatorik : Anordnung von Elementen

Neue Frage »

Ponchosi Auf diesen Beitrag antworten »
Kombinatorik : Anordnung von Elementen
Hallo

Wir sollen eine Formel entwickeln, mit der wir berechnen können, wieviele Möglichkeiten es gibt, eine Betrag zu bezahlen.

Zur verfügung stehen : 1,2,5,10 und eine 20 Cent Münze !

Für dieses Beispiel hat man 27518 Möglichkeiten, diesen Betrag zu bezahlen.

Nur leider komm ich nicht auf diese Lösung unglücklich Leider hab ich nicht mal einen Ansatz.
Nungut, es wird irgendwas mit nem Binomialkoeffizienten zu tun haben, mehr weiß ich leider nicht !

Danke für eure Hilfe !



Ein Beispiel für 60 Cent und 10,20 und 50 Cent Münzen:
1-te Moeglichkeit : 10 10 10 10 10 10
2-te Moeglichkeit : 10 10 10 10 20
3-te Moeglichkeit : 10 10 10 20 10
4-te Moeglichkeit : 10 10 20 10 10
5-te Moeglichkeit : 10 10 20 20
6-te Moeglichkeit : 10 20 10 10 10
7-te Moeglichkeit : 10 20 10 20
8-te Moeglichkeit : 10 20 20 10
9-te Moeglichkeit : 10 50
10-te Moeglichkeit : 20 10 10 10 10
11-te Moeglichkeit : 20 10 10 20
12-te Moeglichkeit : 20 10 20 10
13-te Moeglichkeit : 20 20 10 10
14-te Moeglichkeit : 20 20 20
15-te Moeglichkeit : 50 10
ObiWanKenobi Auf diesen Beitrag antworten »

Soll wirklich wie in Deinem Beispiel die Reihenfolge auch beachtet werden, also

20;20;10;10 ist eine andere Lösung als 20;10;20;10

oder geht es eigentlcih (so hätte ich es verstenden) nur um die möglichen "Stückelungen"
Ponchosi Auf diesen Beitrag antworten »

genau ! das wären 2 unterschiedliche lösungen ! smile
Ponchosi Auf diesen Beitrag antworten »

oh hab noch was vergessen bei der aufgabenstellung oben :

Zur verfügung stehen : 1,2,5,10 und eine 20 Cent Münze !

Bezahlt werden soll ein Betrag von 20 Cent !

Für dieses Beispiel hat man 27518 Möglichkeiten, diesen Betrag zu bezahlen.

Also für 20 Cent hat man 27518 Möglichkeiten, diese mit 1,2,5,10 und 20 Münzen zu bezahlen !
Lord Pünktchen Auf diesen Beitrag antworten »

Also ich würd es zuerst über eine Rekursionsformel versuchen.
Diese dann vereinfachen und falls möglich eine iterative Form herauslesen.


Die Möglichkeit einen Betrag von 20 Cent auszuzahlen ist dann

m(20) = 1*m(0) + 1*m(10) + 1*m(15) + 1*m(18) + 1*m(19)

( m(0) := 1 )


P.S. Ich würd mit kleinen Beträgen anfangen, da man dort eher die Übersicht behält und zusammenhänge erkennt

So setzen sich m(0) und m(1) aus einem Summanden zusammen
m(2), m(3) und m(4) haben schon 2 Summanden
m(5) bis m(9) haben 3 Summanden
etc.

und diese Summanden haben immer eine gemeinsamkeit bzgl. n, wobei n der zuzahlende Betrag sei
Ponchosi Auf diesen Beitrag antworten »

ich steh aufm schlau, kannste das vllt nen bissl genauer erörtern ? :-(
 
 
ObiWanKenobi Auf diesen Beitrag antworten »

Ich würd zunächst die möglichen stückelungen angehen und dann deren mögliche Kombinationen:

20*1 (Kombis:1)
18*1;1*2 (Kombis 19)
16*1:2*2 (Kombis 18 über 2 = 153)
15*1;1*5 (Kombis 16)
14*1;3*2 (kombis 17 über 3= 680)
13*1;1*5;1*2 (Kombis (15 über 2)*2 = 210)
12*1;4*2 (Kombis: 16 über 4 = 1820)
11*1;1*5;2*2 (Kombis (14 über 3)*(3 über 1) = 1092)
10*1;2*5 (Kombis 12 über 2 = 66)
10*1;5*2 (Kombis 15 über 5 = 3003)
10*1;1*10 (Kombis 11)
8*1;6*2 (Kombis 14 über 6 = 3003)
8*1;2*5;1*2 (Kombis (11 über 3)*(3 über 1) = 495)
8*1;1*10;1*2 (Kombis (10 über 2)*2 = 900)
6*1;7*2 (Kombis 13 über 7 = 1716)
6*1;2*5;2*2 (Kombis (10 über 5)*(4 über 2) = 270)
6*1;1*10;2*2
5*1;3*5
5*1;5*2;1*5
5*1;1*10;1*5
4*1;8*2
4*1;2*5;3*2
4*1;1*10;3*2
3*1;1*5;6*2
3*1;1*10;1*5;1*2
2*1;9*2
2*1;2*5;4*2
2*1;1*10;4*2
1*1;3*5;2*2
1*1;1*10;1*5;2*2
10*2
5*2;2*5
5*2;1*10
4*5
2*5;1*10
2*10
1*20
Mystic Auf diesen Beitrag antworten »

Ja, das ist korrekt, ich würde das Ganze nur etwas anders rechnen... Setzt man



so muss man ja offenbar nur einfach die Koeffizienten von aller Potenzen , berechnen und aufsummieren, d.h., insgesamt müsste man dann berechnen den Koeffizienten von von



Hier die Rechnung dazu in DERIVE:

u := x + x^2 + x^5 + x^10 + x^20
POLY_COEFF((u^21 - 1)/(u - 1), x, 20) = 27518

Edit: Eine andere Möglichkeit wäre es, nach der Devise "Nicht kleckern, klotzen!" gleich alle Potenzen aufzusummieren zu



und dann mit dem üblichen Algorithmus für die Invertierung in den Koeffizienten von rekursiv zu berechnen...
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »