Rekurencja
Materiały
Dla nauczyciela
Dla ucznia
Zadania
Zadanie 1. Roztargniony profesor
Pewien profesor, aby dostać się do swego gabinetu, musi pokonać \(N\) schodów. Profesor pokonuje zazwyczaj jeden lub dwa schody na raz. Oblicz, na ile różnych sposobów profesor może pokonać schody. Podaj te sposoby.
Wejście
Jedna liczba całkowita \(N\) (\(1 \leq N \leq 25\)) - liczba schodów.
Wyjście
Wyjście zawiera w pierwszym wierszu liczbę możliwych kombinacji, w kolejnych wierszach wszystkie możliwe kombinacje w porządku leksykograficznym.
Przykład
| Wejście | Wyjście |
|---|---|
| 3 | 3 1 1 1 1 2 2 1 |
Wskazówka
Zasymuluj rekurencyjnie wszystkie możliwe sposoby.
Zadanie 2. Mysz w labiryncie
Do labiryntu trafiła mysz. Pomóż jej odnaleźć wyjście!
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite \(n\) i \(m\) (\(2 \leq n, m \leq 1000\)) oznaczające rozmiar labiryntu: \(n\) kolumn i \(m\) wierszy. W kolejnych liniach znajdują się znaki oznaczające kolejno:
- "-" możliwość przejścia (korytarz);
- "x" brak przejścia (ściana);
- "o" początkowe położenie myszy;
- "w" wyjście (końcowe położenie myszy).
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien wypisać „TAK” – jeśli istnieje wyjście z labiryntu, lub „NIE” – jeżeli warunek nie będzie spełniony.
Przykład
| Wejście | Wyjście |
|---|---|
| 8 8 w--x-x-- xx-x-x-- ---x---- --xxxx-- --x--x-- -----x-o xxxx---- ------x- |
TAK |
Wskazówka
Rekurencyjnie przesuwaj mysz w lewo, prawo, do góry i do dołu. Sprawdź po obejściu całej planszy, czy odwiedzone jest wyjście.
Zadanie 3. Problem 8 hetmanów
Janek uczy się grać w szachy. Poznaje sposób poruszania się różnych figur. Najśmieszniejszy wydaje mu się styl skoków konika. Zastanawia się również, co byłoby, gdyby na szachownicy znalazło się kilka figur hetmanów. Analizuje, czy na planszy o wymiarach \(n \times n\) możliwe jest takie rozstawienie \(n\) tych figur, aby żaden z nich się nie szachował, a jeśli tak, to na ile sposobów można to zrobić?
Wejście
\(n\) - rozmiar szachownicy, liczba naturalna mniejsza niż \(15\).
Wyjście
Liczba sposobów, na jakie można rozmieścić figury hetmanów na szachownicy tak, by się wzajemnie nie szachowały.
Przykład
| Wejście | Wyjście |
|---|---|
| 8 | 92 |
Wskazówka
Zasymuluj ustawianie hetmanów korzystając z przeszukiwania z nawrotami.