Wieża Hanoi

Zadanie 8 z 13 · rozdział 15Trudność: 2 z 3rekurencjaHanoi

Treść zadania

Na słupku A leży N krążków o różnych średnicach: na dole największy, a każdy kolejny jest mniejszy od poprzedniego. Słupki B i C są puste. Należy przenieść wszystkie krążki na słupek B, korzystając ze słupka C jako pomocniczego. Obowiązują zasady:

  • w jednym ruchu przenosimy dokładnie jeden krążek — górny krążek z jednego słupka na inny,
  • nie wolno położyć większego krążka na mniejszym.

Napisz rekurencyjną funkcję hanoi(n, skad, dokad, pomocniczy), która wypisuje ruchy przenoszące n krążków ze słupka skad na słupek dokad. Program wczytuje N i wypisuje najkrótszą sekwencję ruchów (ma ona $2^N - 1$ ruchów i jest wyznaczona jednoznacznie).

Dane wejściowe

Jedna liczba naturalna N.

Dane wyjściowe

$2^N - 1$ linii — kolejne ruchy w formacie X -> Y, gdzie X to słupek, z którego zdejmujemy krążek, a Y to słupek, na który go kładziemy.

Ograniczenia

  • 1 ≤ N ≤ 10

Uwagi

  • Aby przenieść n krążków ze słupka skad na dokad: przenieś n-1 górnych krążków na słupek pomocniczy, przenieś największy krążek na dokad, a na koniec przenieś n-1 krążków ze słupka pomocniczy na dokad. Przypadek bazowy: jeden krążek (albo zero krążków — wtedy nic nie robimy).

Przykład

Wejście
3
Wyjście
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B

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.

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

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
1
Oczekiwane wyjście
A -> B

Test 2

Nie uruchomiono
Wejście
2
Oczekiwane wyjście
A -> C
A -> B
C -> B

Test 3

Nie uruchomiono
Wejście
4
Oczekiwane wyjście
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
A -> B
C -> B
C -> A
B -> A
C -> B
A -> C
A -> B
C -> B

Test 4

Nie uruchomiono
Wejście
5
Oczekiwane wyjście
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
A -> C
B -> C
B -> A
C -> A
B -> C
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
C -> A
B -> C
B -> A
C -> A
C -> B
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
Uruchom z własnymi danymi