Makarov Math Suite: Ханойская башня - маленькая головоломка с экспоненциальным характером

Есть три стержня и несколько дисков разного размера. Нужно перенести всю башню с одного стержня на другой, перемещая по одному диску и никогда не кладя большой диск на маленький. Правила помещаются в одну фразу, но число необходимых действий растёт удивительно быстро. Чтобы переместить самый большой диск, сначала нужно убрать с него все меньшие на вспомогательный стержень. После одного хода большим диском меньшую башню приходится переносить ещё раз. Так задача сама раскладывается на две задачи того же типа, но меньшего размера. Получается рекурсия: T(n) = 2T(n − 1) + 1. Из неё следует точный минимум - 2ⁿ − 1 ходов. Для трёх дисков достаточно семи, а для восьми уже нужно 255. В модуле можно переставлять диски вручную или наблюдать автоматическую последовательность, сравнивая свой счётчик с оптимальным. Попробуйте сначала решить небольшую башню и заметить повторяющиеся подзадачи. Затем добавьте диски: правила не станут сложнее, но работа резко вырастет. Это наглядный способ почувствовать разницу между краткостью алгоритма и количеством действий, которые ему предстоит выполнить.