Головоломка «Ханойская башня»

«Ханойская башня» (Tower of Hanoi) —головоломка очень полезная для детей и взрослых  используется как тренажёр аналитических способностей. 

Как играть

Правила очень простые:

есть три стержня, на первом сложена пирамидка из любого числа дисков. Перенесите всю башню в противоположный конец, на последний стержень.

При переносе учитываются следующие ограничения:

· · за раз переносится только 1 диск;

·         можно брать один из верхних кругов любой башни и переносить на любой из соседних стержней;

элемент меньшего размера должен покрывать крупный

В головоломке «Ханойская башня» можно играть с 3, 4, 5 или 6,7 дискам одновременно. Чем их больше, тем сложнее.

Алгоритм «Ханойской башни»

Циклическое решение

Обозначим через «1-2» такое действие: переложить диск или с 1-го штыря на 2-й, или со 2-го на 1-й, в зависимости от того, где он меньше. Тогда, чтобы решить головоломку с чётным количеством дисков, надо многократно повторять действия: 1-2, 1-3, 2-3. Если число дисков нечётно — 1-3, 1-2, 2-3.

Самым простым решением головоломки является чередование переноса наименьших дисков. Если начальное число дисков чётное, всегда переносите наименьший диск вправо, если начальное число кусков нечётное — на самый крайний стержень. Например, вы начали играть в «Ханойскую башню» из 3 кругов. Переместите наименьшую часть на противоположный конец, а затем продолжайте ходом влево. Следование этому правилу завершает головоломку с наименьшим количеством ходов.