Ćwiczenie 5 - rekurencja - wieże Hanoi

Przykład pomocniczy:

factorial.c - program obliczający silnię z liczby podanej jako parametr wywołania, przy użyciu metody rekurencyjnej.

Zadanie

Proszę napisać program rozwiązujący w sposób rekurencyjny problem wież Hanoi, dla zadanego parametru N - liczby krązków.

Szczegóły dotyczące problemu:

Sytuację wyjściową w sposób schematyczny, przedstawia poniższy rysunek:

Na drążku "A" spoczywa N krążków w kolejności od największego do najmniejszego (wszystkie krążki różnią się od siebie rozmiarem). Zadanie polega na tym aby przełożyć wszystkie krążki z drążka "A" na drążek "B", używając drążka pomocniczego "C", przy zachowaniu następujących reguł:

1. można na raz przenosić tylko jeden krążek,
2. w żadnym z etapów pośrednich nie może krążek większy leżeć na mniejszym.

Program powinien:

1. pobierać jeden parametr wywołania - liczbę krążków
2. zawierać rekurencyjną funkcję która rozwiązuje problem, oraz wypisuje na ekran każde przeniesienie krążka, w postaci:
   A->B, przy przeniesieniu krążka z drążka "A" na "B",
   C->A przy przeniesieniu krążka z drążka "C" na "A"
   .... itd.

Algorytm:

W celu lepszego zrozumienia działania algorytmu, warto przed napisaniem programu, prześledzić na kartce jego działanie dla np. N=3.

* Zadanie dodatkowe (nieobowiązkowe):
Proszę tak napisać program, aby dodatkowo przy każdym ruchu wyświetlał również schematycznie ułożenie ponumerowanych krążków na poszczególnych wieżach, np. dla pozycji wyjściowej:
|3|2|1
|0|0|0
|0|0|0