sposoby
assa: Na ile sposobów można rozmienić 5000 zł za pomocą monet 1, 2, 3, 5
złotowych?
16 mar 15:14
muflon: Istnieją monety 3 zł?
16 mar 15:27
assa: nie istnieja ale w zadaniu muszą byc
16 mar 15:36
Trivial:
Zadanko można rozwiązać korzystając z funkcji tworzących.
Tutaj jest to opisane:
http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Wyk%C5%82ad_7:_Funkcje_tworz%C4%85ce
Zapisujemy funkcje tworzące opisujące liczbę rozwiązań przy użyciu jednej monety
(o nominale 1,2,3,5).
G(x) = g
0 + g
1x + g
2x
2 + g
3x
3 + ...
Współczynnik g
k oznacza liczbę sposobów rozmienienia kwoty k przy użyciu danej monety.
| | 1 | |
G1(x) = 1 + x + x2 + x3 + ... = |
| |
| | 1−x | |
| | 1 | |
G2(x) = 1 + 0*x + x2 + 0*x3 + x4 + ... = 1 + x2 + (x2)2 + ... = |
| |
| | 1−x2 | |
| | 1 | |
G3(x) = 1 + x3 + (x3)2 + (x3)3 + ... = |
| |
| | 1−x3 | |
| | 1 | |
G5(x) = 1 + x5 + (x5)2 + (x5)3 + ... = |
| |
| | 1−x5 | |
Liczbę sposobów rozmienienia kwoty k przy użyciu tych czterech monet opisze funkcja:
| | 1 | |
G1(x)G2(x)G3(x)G5(x) = |
| |
| | (1−x)(1−x2)(1−x3)(1−x5) | |
Którą jednak trudno wykorzystać do obliczenia współczynników. Dużo lepszym sposobem jest
rozbicie tego mnożenia na poszczególne kroki:
| | A(x) | |
B(x) = A(x)G2(x) = |
| |
| | 1−x2 | |
| | B(x) | |
C(x) = B(x)G3(x) = |
| |
| | 1−x3 | |
| | C(x) | |
D(x) = C(x)G5(x) = |
| |
| | 1−x5 | |
Każde równanie mnożymy przez 1−x
k. Otrzymujemy:
A(x) = 1 + xA(x)
B(x) = A(x) + x
2B(x)
C(x) = B(x) + x
3C(x)
D(x) = C(x) + x
5D(x)
W przełożeniu na współczynniki daje to:
a
n = 1 (bo A(x) = a
0 + a
1x + a
2x
2 + a
3x
3 + ... ≡ 1 + x + x
2 + x
3 + ...)
b
n = a
n + b
n−2
c
n = b
n + c
n−3
d
n = c
n + d
n−5
Warunki początkowe: a
n, b
0, b
1, c
0, c
1, c
2, d
0, d
1, d
2, d
3, d
4 = 1.
Trzeba znaleźć d
5000.
16 mar 16:02
Trivial:
Złe warunki początkowe. Powinno być:
a
n = 1
b
k = a
k, dla k = 0,1
c
k = b
k, dla k = 0,1,2
d
k = c
k, dla k = 0,1,2,3,4
Wystarczy to policzyć. Do dzieła.
16 mar 16:05
assa: dzięki wielkie
16 mar 16:09
muflon: assa, to jest zadanie ze studiów, czy z liceum?
16 mar 16:10
assa: studiów
16 mar 16:12
16 mar 16:35