Hej,
Nie wiem jak się w ogóle zabrać za to zadanie.
Bankomat ma w zasobach tylko banknoty o wartości \(\displaystyle{ 20}\) i \(\displaystyle{ 50}\) dolarów. Znajdz zależność rekurencyjną na liczbę sposobów na które może bankomat wydać nam \(\displaystyle{ 10 \cdot n}\) dolarów. Zakładamy, że kolejność wydawania banknotów jest istotna i może być dowolna.
Prosze o pomoc
Rozmienienie kwoty
-
- Użytkownik
- Posty: 562
- Rejestracja: 20 maja 2013, o 16:33
- Płeć: Mężczyzna
- Lokalizacja: Kielce
- Podziękował: 98 razy
Rozmienienie kwoty
Ostatnio zmieniony 9 sie 2017, o 00:07 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Rozmienienie kwoty
Warunki początkowe:
\(\displaystyle{ x _{20} = x _{50} = 1}\)
\(\displaystyle{ x_{y} = 0}\), dla \(\displaystyle{ y < 0}\)
\(\displaystyle{ x_{0} = x_{10} = x_{30} = 0}\)
Ostatnim wydanym banknotem mogło być \(\displaystyle{ 20}\) lub \(\displaystyle{ 50}\), więc są dwa przypadki, które musimy zsumować:
\(\displaystyle{ x_{10n} = x_{10n - 20} + x_{10n - 50}}\)
\(\displaystyle{ x _{20} = x _{50} = 1}\)
\(\displaystyle{ x_{y} = 0}\), dla \(\displaystyle{ y < 0}\)
\(\displaystyle{ x_{0} = x_{10} = x_{30} = 0}\)
Ostatnim wydanym banknotem mogło być \(\displaystyle{ 20}\) lub \(\displaystyle{ 50}\), więc są dwa przypadki, które musimy zsumować:
\(\displaystyle{ x_{10n} = x_{10n - 20} + x_{10n - 50}}\)
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Rozmienienie kwoty
To znaczy przyjmiemy chyba, że maszyna ma wypluwać banknoty o nominałach w kolejności nierosnącej. Wtedy to zadanie jest równoważne początkowemu zadaniu tylko takiemu, w którym zakładamy, że kolejność banknotów nie ma znaczenia (bo możemy je posortować w kolejności nierosnącej).
Wtedy dostajemy równanie: \(\displaystyle{ 20x + 50 y = 10n}\), czyli \(\displaystyle{ 2x + 5y = n}\) i liczba jego rozwiązań to odpowiedź.
Wtedy dostajemy równanie: \(\displaystyle{ 20x + 50 y = 10n}\), czyli \(\displaystyle{ 2x + 5y = n}\) i liczba jego rozwiązań to odpowiedź.