na ile sposobów.....

kemot25 · Post autor: **kemot25** » 9 gru 2009, o 16:08

Złodziej napadł na bank zażądał 500 dolarów w banknotach 20 i 10 dolarowych. Na ile sposobów może kasjer mógł spełnić żądanie?

abc666 · Post autor: **abc666** » 9 gru 2009, o 18:40

Czy zadanie ma być rozwiązane przy pomocy funkcji tworzących?

Goter · Post autor: **Goter** » 9 gru 2009, o 22:35

Używając tylko nominału 10$ można wypłacić 500$ tylko na jeden sposób: samymi dziesiątkami. Ogólnie to mając tylko ten nominał możemy każdą wielokrotność 10$ wypłacić na dokładnie jeden sposób.

Teraz używajmy jeszcze nominału 20$. Możemy użyć 20-dolarówek:
0 razy (resztę wypełniamy dziesiątkami)
1 raz
2 razy
3 razy
itd
aż do 25 razy (wtedy jest zero 10-dolarówek)

Czyli sposobów jest 26.

kemot25 · Post autor: **kemot25** » 10 gru 2009, o 11:20

Tak, a przy pomocy funkcji tworzących

abc666 · Post autor: **abc666** » 10 gru 2009, o 11:28

Nie rozwodząc się, proponuje przeczytać ten temat. 127737.htm?hilit=%20tworz%C4%85ce
U nas jest dużo łatwiej. Mamy tylko dwa nominały. Więc dojdziemy do równania rekurencyjnego
$\displaystyle{ b_n=1+b_{n-2}}$
a konkretną odpowiedzią $\displaystyle{ b_{50}}$
(podzielić można wszystkie kwoty przez 10, to nic nie zienia)