Ханойські вежі

Кожен програміст знає головоломку "Ханойські вежі". Коротко нагадаємо її умову.

Є $3$ стержні: $A$, $B$, $C$. Спочатку $n$ дисків різного діаметру розміщено на стержні $A$: найменший диск розміщено зверху, і далі донизу за збільшенням діаметру. Другий та третій стержні порожні.

Необхідно перенести усі диски зі стержня $A$ на стержень $B$, використовуючи стержень $C$ як додатковий.

За один крок дозволяється зняти один верхній диск і покласти його або на порожній стержень, або на стержень, верхній диск якого має більший діаметр.

Майже усі книги з програмування містять рекурсивне розв'язання задачі. Наприклад, нижче наведено розв'язок на мові Паскаль.

Procedure Hanoi ($A$, $B$, $C$: integer; $N$:integer);

Begin

If N > 0 then

Begin

Hanoi ($A$, $C$, $B$, N-1);

Writeln('Disk ', $N$, ' from ', $A$, ' to ', $B$);

Hanoi ($C$, $B$, $A$, N-1)

End

End;

Відомо, що наведений вище розв'язок вимагає виконання (2^n - 1) кроків. З врахуванням початкового розміщення, є всього 2^n комбінацій розміщення $n$ дисків на трьох стержнях. Деякі комбінації ніколи не зустрічаються під час виконання алгоритму. Наприклад, комбінація "$CAB$" ніколи не зустрінеться у грі при n=3 (найменший диск розміщено на стержні $C$, середній на стержні $A$, а найбільший на $B$).

Напишіть програму, яка встановить, чи зустрінеться у грі задана комбінація.