Gra

Zadanie 10 z 13 · rozdział 15Trudność: 2 z 3rekurencjakombinatoryka

Treść zadania

W grze w każdym ruchu gracz zdobywa 3, 5 albo 10 punktów. Gracz wygrywa, gdy uzbiera dokładnie N punktów.

Napisz rekurencyjną funkcję liczba_sposobow(n, ruchy), która zwraca, na ile sposobów można uzbierać dokładnie n punktów, używając ruchów o wartościach z listy ruchy. Sposoby różniące się tylko kolejnością ruchów traktujemy jako ten sam sposób — liczy się tylko, ile razy gracz zdobył 3, ile razy 5, a ile razy 10 punktów.

Program wczytuje N i wypisuje liczbę sposobów wygrania gry.

Dane wejściowe

Jedna liczba naturalna N (N ≥ 1).

Dane wyjściowe

Jedna liczba naturalna — liczba sposobów (może wynosić 0).

Ograniczenia

1 ≤ N ≤ 100

Uwagi

Rozbij problem na dwa mniejsze: sposoby, w których co najmniej raz użyjemy pierwszego ruchu z listy (wtedy zostaje n - ruchy[0] punktów, a lista ruchów się nie zmienia), oraz sposoby, w których tego ruchu nie użyjemy wcale (te same n punktów, lista ruchy[1:]). Wynik to suma obu liczb.
Przypadki bazowe: n == 0 — znaleźliśmy jeden sposób; n < 0 albo pusta lista ruchów — żadnego sposobu.

Przykład

Wejście

Wyjście

Sposoby: $10 + 10$, $10 + 5 + 5$, $5 + 5 + 5 + 5$ oraz $5 + 3 + 3 + 3 + 3 + 3$.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 15

Poniższe zadania uczą rekurencji: funkcja rozwiązuje problem, wywołując samą siebie dla mniejszych danych, aż dojdzie do przypadku bazowego, w którym odpowiedź jest znana od razu (np. $0! = 1$).

Konwencje wspólne:

Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście. Program wczytuje dane, wywołuje funkcję opisaną w treści i wypisuje wynik (gotowy szkielet znajdziesz w sekcji „Kod startowy”).
Rozwiązanie musi być rekurencyjne. Właściwe obliczenia wykonuje funkcja, która wywołuje samą siebie. Nie używaj w niej pętli for ani while, ani gotowych narzędzi, które wykonają całą pracę za Ciebie (np. sum(), pow(), operatora **, math.factorial(), list.index()). Sprawdzarka porównuje tylko wynik, ale celem zadań jest ćwiczenie rekurencji.
Każda funkcja rekurencyjna potrzebuje przypadku bazowego (kiedy przestajemy się wywoływać) i kroku rekurencyjnego (wywołania dla mniejszego problemu). Bez przypadku bazowego program przerwie działanie błędem RecursionError.
Python ogranicza głębokość rekurencji (domyślnie do około 1000 zagnieżdżonych wywołań), dlatego dane w zadaniach są małe.
Liczby naturalne liczymy od zera: $0, 1, 2, \dots$
Program nie wypisuje komunikatów typu „Podaj liczbę:”.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Twój kod w Pythonie

Python uruchomi się w przeglądarce przy pierwszym teście.

Nie uruchomiono

Wejście

Oczekiwane wyjście

Uruchom z własnymi danymi

Dane wejściowe (to, co program odczyta przez input())