Kombinatorik : Anordnung von Elementen |
02.05.2010, 19:45 | Ponchosi | Auf diesen Beitrag antworten » |
Kombinatorik : Anordnung von Elementen 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 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 |
||
02.05.2010, 19:54 | 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" |
||
02.05.2010, 20:16 | Ponchosi | Auf diesen Beitrag antworten » |
genau ! das wären 2 unterschiedliche lösungen ! |
||
02.05.2010, 20:20 | 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 ! |
||
02.05.2010, 20:50 | 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 |
||
02.05.2010, 21:23 | Ponchosi | Auf diesen Beitrag antworten » |
ich steh aufm schlau, kannste das vllt nen bissl genauer erörtern ? :-( |
||
Anzeige | ||
|
||
03.05.2010, 03:38 | 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 |
||
03.05.2010, 07:39 | 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... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|