Rozmienienie kwoty

[Matiks21]

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

[Mruczek]

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}}\)

[Takahashi]

Jak zmieni się odpowiedź do tego zadania, jeśli wymusimy, by maszyna wypluwała banknoty o coraz mniejszych nominałach?

[Mruczek]

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ź.