Matematyka dyskretna, zadanie nr 4346

Autor	Zadanie / Rozwiązanie
4kiru postów: 11	2016-03-01 09:15:55 Witam dostałem zadanie z matematyki dyskretnej które mam rozwiazac za pomocą programu który mam napisać jednak nie bardzo wiem jak się do niego zabrać jesli kto mógłby mi rozpisać plan działań (matematyczne zależności) potrzebnych do rozwiązania problemu byłbym wdzięczny zadanie jest nastepujace: Na ile sposobów można rozmienić 1000 zl używając banknotów o nominalach 10, 20, 50, 100 i 200 zl. Z Góry dzieki za pomoc. Wiadomość była modyfikowana 2016-03-01 09:23:30 przez 4kiru

janusz78 postów: 820	2016-03-01 12:33:05 Na ile sposobów możemy przedstawić liczbę $ 1000 $ w postaci kombinacji $ 1000= k\cdot 10+l\cdot 20+ m\cdot 50 +n\cdot 100 +p\cdot 200$ (1) Rozpatrujemy sumę szeregu geometrycznego $ S(x)=\sum_{k,l,m,n,p\in N}x^{k\cdot 10+l\cdot 20+ m\cdot 50 +n\cdot 100 +p\cdot 200}.$ $S(x)= (\sum_{k\in N}x^{10k})(\sum_{l\in N}x^{10l}) (\sum_{m\in N}x^{50m})(\sum_{n\in N}x^{100n})(\sum_{p\in N}x^{200p}).$ $S(x)= \frac{1}{(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})}.$ Czynniki w powyższym iloczynie to szeregi geometryczne zbieżne jednostajnie w kole $\|x\|<1,$ a więc $S(x)$ jako iloczyn Cauchy'ego jest zbieżny jednostajnie w tym kole. Zauważmy, że wyraz stopnia 1000 w $ S(x)$ to dokładnie $\sum_{k,l,m,n,p \in N}x^{k\cdot 10+l\cdot 20+ m\cdot 50 +n\cdot 100 +p\cdot 200} = a_{1000}x^{1000},$ gdzie współczynnik $ a_{1000}$ jest liczbą wszystkich piątek spełniających równanie (1) Rozwiązanie w Mathematica 9 $ f[x_]:= 1 / ((1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200}));$ $S = Series[f[x],\left\{x,0,1000\right\}]$ SeriesCoefficient[S,1000] Wynik $ 4111$ Wiadomość była modyfikowana 2016-03-01 15:38:48 przez janusz78

tumor postów: 8070	2016-03-01 17:23:31 Dane są niewielkie, więc jest sens liczyć rekurencyjnie, nie zabije to zasobów. Niech S(K,N(k)) oznacza ilość możliwości wydania kwoty K przy największym użytym nominale N(k), gdzie N jest tablicą [10,20,50,100,200], załóżmy, że numerujemy od 0. Zatem masz policzyć S(1000,N(4)). Zauważamy, że wydanie kwoty K przy użyciu nominałów najwyżej N(k) można rozbić na przypadki a) istnieje co najmniej jeden nominał N(k), b) nie istnieje nominał N(k), ale jest co najmniej jeden N(k-1) c) i tak dalej Zatem $S(1000,N(4))=S(800,N(4))+S(900,N(3))+S(950,N(2))+S(980,N(1))+S(990,N(0))$ ogólnie $S(K,N(k))=\sum_{i=0}^{k}S(K-N(i),N(i))$

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj