Zadanie 78
Na ile sposobów możemy wydać 5000zł za pomocą monet 1, 2, 3, 5, 10
złotowych?
Rozwiązanie
Rozwiązanie zadania oparte jest na użyciu funkcji tworzących i równań rekurencyjnych.
Rozpatrzmy pierwszy przypadek, gdy nie mamy nic poza jednozłotówkami:
Suma wszystkich sposobów, na ile możemy wydać resztę w złotówkach może być zapisana:
P = 0 + 1zł + 1zł 1zł + 1zł 1zł 1zł + & = 0 + 1zł + 1zł2 + 1zł3 + &
Pierwszy składnik oznacza na ile sposobów możemy wydać zero jednozłotówek, drugi jedną
jednozłotówkę itd.
W przypadku posiadania dwóch nominałów mianowicie monety jedno i dwuzłotowej
otrzymujemy:
N = P + 5złP + (5zł 5zł)P+ & = (0 + 5zł + 5zł2 + & )P
W trzecim przypadku dodajemy do naszych nominałów monetę 3 złotową. Otrzymujemy:
D = (0 + 3zł + 3zł2 + 3zł3 + & )N
Podobnie w przypadku monet 5zł i 10zł:
Q = (0 + 5zł + 5zł2 + 5zł3 + & )D
C = (0 + 10zł + 10zł2 + 10zł3 + & )Q
Naszym celem jest znalezienie liczby składników w C o wartości 5000zł
Aadne rozwiązanie możemy otrzymać poprzez zastąpienie każdego składnika przez zn.
Wówczas otrzymamy:
1zł = z
2zł = z2
3zł = z3
5zł = z5
10zł = z10
Niech Pn, Nn, Dn, Qn i Cn będą liczbami sposobów na ile można rozmienić n złotówek.
Analiza pokazuje nam, że są to współczynniki przy zn w odpowiednich szeregach
potęgowych:
P = 1 + z + z2 + z3 + &
N = (1 + z2 + z4 + z6 + & )P
D = (1 + z3 + z6 + z9 + & )N
Q = (1 + z5 + z10 + z15 + & )D
C = (1 + z10 + z20 + z30 + & )Q
Stosując funkcje tworzące ze wzoru:
G(x) = "(n=0 do ") xn = 1/(1-x) otrzymujemy następujące przekształcenie:
P = 1/(1 z)
N = P/(1 z2)
D = N/(1 z3)
Q = D/(1 z5)
C = Q/(1 z10)
Mnożąc przez mianowniki otrzymujemy:
(1 z)P = 1
(1 z2)N = P
(1 z3)D = N
(1 z5)Q = D
(1 z10)C = Q
Porównując w tych równaniach współczynniki przy zn otrzymujemy równanie rekurencyjne, z
którego możemy obliczyć wszystkie potrzebne współczynniki do obliczenia naszego zadania:
Pn = Pn 1 + [n = 0]
Nn = Nn 2 + Pn
Dn = Dn 3 + Nn
Qn = Qn 5 + Dn
Cn = Cn 10 + Qn
Np.:
Chcąc obliczyć na ile sposobów możemy wydać 10 zł przy pomocy monet o powyższych
nominałach stosujemy powyższe równanie:
C10 = C10 10 + Q10 = C0 + Q10
Chcemy więc znalezć Q10 :
Q10 = Q10 5 + D10 = Q 5 + D10
itd& aż otrzymamy wynik 21.
Rozwiązaniem C5000 = 87 536 696 445
Odpowiedz:
5000zł w powyższych nominałach można wydać na 87 536 696 445 sposobów.
Zadanie 21
Kostka do gry ma sześć ścian oznaczonych oczkami od 1 6. Rzucasz kostką tak długo, aż
wypadną wszystkie liczby oczek. Znajdz wartość oczekiwaną liczby wykonanych rzutów.
Rozwiązanie
W zadaniu tym skorzystam z rozkładu geometrycznego oraz z procesu Bernoulliego.
Konieczne będzie także użycie funkcji losowej.
Wartość oczekiwana jest to suma iloczynów wartości zmiennej losowej oraz
prawdopodobieństwa z jakimi są przyjmowane.
"k pk k
k wszystkie możliwe wartości X
pk prawdopodobieństwo tego, że X przyjmie wartość k
X zmienna losowa
X = X1 + X2 + X3 + Xi
Xi czas oczekiwania na i-ty wynik różniący się od wcześniej otrzymanych czyli (i 1).
W przypadku kostki do gry mamy 6 możliwych wyników w związku z tym zmienne losowe
mają następującą postać:
X = X1 + X2 + X3 + X4 + X5 + X6
W pierwszym rzucie prawdopodobieństwo tego, że wypadnie oczko w przedziale od 1 6
wynosi 1, gdyż zawsze coś wypadnie i nie jest istotne jaka ilość oczek. W związku z tym:
X1 = 1.
W drugim rzucie prawdopodobieństwo tego, że wypadnie liczba oczek, która jest różna od
poprzednio już wyrzuconej wynosi 5/6.
W trzecim rzucie: 4/6
W czwartym: 3/6
W piątym : 2/6
W szóstym: 1/6
Zmienne losowe mają rozkład geometryczny. Wzór na funkcję rozkładu prawdopodobieństwa
geometrycznego jest następujący:
(1 p)k 1 p
Wartość oczekiwana EX wynosi więc:
EX = 1 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 14,7
Odpowiedz
Wartością oczekiwaną liczby wykonanych rzutów jest wartość 14,7.
Wyszukiwarka
Podobne podstrony:
Artur Andrzeuk uczucia i sprawnosci w podejmowaniu decyzjiTN Andrzejki GimnazjumAndrzej Pilipiuk Tajemnica wody (2)Prezydent RP Andrzej Duda Polska narodziła się z wód chrzcielnychNowacki Andrzej Jak zarobić na allegro up by EsiAndrzej Sapkowski Wiedźmin Sezon Burz Rozdzial 1więcej podobnych podstron