Ханойская башня на пальцах

Пообщавшись с некоторыми знакомыми программистами, внезапно обнаружил, что не все знают про Ханойскую башню, а среди тех кто знает — мало кто понимает как решается эта задача.
Википедия по этому поводу пишет очень строго, по делу, и ничего не объясняет. Мол принимайте как прописную истину. Поэтому понять как она решается — сходу трудновато. А ведь задача очень простая, и между тем интересная в программировании и математически.

В статье будет много картинок. Объяснение как решать задачу рекурсивно. Как она решается бинарным поиском
В общем статья посвящается тем смелым, кто пока еще боится Ханойской башни, но хочет перестать её боятся.

Правила игры

Они очень просты. Есть 1 пирамидка с дисками разного размера, и еще 2 пустые пирамидки. Надо переместить диски с одной пирамидки на другую. Перекладывать можно только по одному диску за ход. Ложить диски можно только меньший на больший.
Итак у нас есть вот такая пирамидка:

И нам надо переложить её скажем на среднюю ось.
Если начать решать задачу не с начала, а с конца — она оказывается очень простой. Давайте подумаем. Чтобы переложить пирамидку на вторую ось — нам надо переложить самый нижний диск, а сделать это можно только когда 4 верхних диска будут на третьей оси:

Для того, чтобы переложить 4 диска на третью ось нужно по сути решить ту же задачу, но для 4-х дисков. То есть на третью ось мы можем переложить 4-ый диск только тогда, когда у нас 3 диска на второй оси:

Чувствуете рекурсию?
Перекладывание стека из 5 дисков — это:
1. Перекладывание стека из 4х дисков на независимую ось
2. Перекладывание 5-го диска на нужную нам ось
3. Перекладывание стека из 4х дисков на нужную нам ось

В свою очередь перекладывание стека из 4 дисков — это:
1. Перекладывание стека из 3х дисков на независимую ось
2. Перекладывание 4-го диска на нужную нам ось
3. Перекладывание стека из 3х дисков на нужную нам ось

Вот и все.

Рекурсивная реализация

После такого подробного описания не составит сложности реализовать это алгоритмически.

Реализация на Delphi

Итак я описал модуль с типами башенок:

unit untHTypes;  interface  const MaxRingCount = 5;  type   TTower = record     RingCount: Integer;     Rings: array [0..MaxRingCount-1] of Integer;     procedure MoveRing(var AtTower: TTower);   end;    TTowers = array [0..2] of TTower;  procedure InitTowers(var towers: TTowers);  implementation  procedure InitTowers(var towers: TTowers); var i: Integer; begin   towers[0].RingCount := MaxRingCount;   towers[1].RingCount := 0;   towers[2].RingCount := 0;   for i := 0 to MaxRingCount - 1 do   begin     towers[0].Rings[i] := MaxRingCount - i;     towers[1].Rings[i] := 0;     towers[2].Rings[i] := 0;   end; end;  { TTower }  procedure TTower.MoveRing(var AtTower: TTower); begin   Assert(RingCount > 0);   Assert(AtTower.RingCount - 1 < MaxRingCount);   if AtTower.RingCount > 0 then     Assert(Rings[RingCount - 1] < AtTower.Rings[AtTower.RingCount - 1]);    Dec(RingCount);   AtTower.Rings[AtTower.RingCount] := Rings[RingCount];   Rings[RingCount] := 0;   Inc(AtTower.RingCount); end;  end.

TTower — структура описывающая башню. В ней в RingCount хранится количество фактически одетых колец на башне. Размер колец хранится в массиве Rings от 1 и до MaxRingCount. Поскольку у нас 3 башни — то был объявлен тип TTowers = array [0..2] of TTower;
Так же с башни можно переложить верхее кольцо на другую с помощью функции MoveRing. Функция проверяет корректность операции через Assert-ы.
Само же решение башни находится в файле проекта:

program Hanoy;  {$APPTYPE CONSOLE}  uses   SysUtils,   untHTypes in 'untHTypes.pas';  {$R *.res}  procedure SolveHanoy; var towers: TTowers;   function GetThirdIndex(index1, index2: Integer): Integer; //по двум имеющимся осям возвращает третью независимую ось   begin                                                     //на которую временно можно переложить стек     Assert(index1 <> index2);     case index1 of       0: if index2 = 1 then Result := 2 else Result := 1;       1: if index2 = 2 then Result := 0 else Result := 2;       2: if index2 = 0 then Result := 1 else Result := 0;     else       Assert(False,'wrong indeces');     end;   end;   procedure MoveStack(stacksize: Integer; fromindex, atindex: Integer); //перемещает стек из пирамидок с одной оси на другую   var thirdindex: Integer;   begin     if stacksize = 0 then Exit;     thirdindex := GetThirdIndex(fromindex, atindex);     //подбираем независимую ось     MoveStack(stacksize - 1, fromindex, thirdindex);     //перемещаем подстек (на 1 меньший) на независимую ось     towers[fromindex].MoveRing(towers[atindex]);         //перемещаем последнее кольцо на нужную нам ось     WriteLn(fromindex,'-',atindex);                      //  записываем в консоль наше действие     MoveStack(stacksize - 1, thirdindex, atindex);       //вовзращаем подстек с независимой на нужную нам ось   end; begin   InitTowers(towers);   MoveStack(MaxRingCount, 0, 1); end;  begin   SolveHanoy; end.

Алогитмичиская сложность

Мы легко можем подсчитать, сколько действий нам понадобится, чтобы переместить пирамидку.
Если мы перемещаем стек из одного диска — то нам нужно 1 действие.
Если стек из двух — то 1 * 2 (переместить дважды стек из одного диска ) + 1 (перемещаем последний диск)
Если из трех ((1 * 2) + 1) * 2 + 1
Из пяти: (((((1 * 2) + 1) * 2 + 1) * 2 + 1) * 2 + 1)
Итак каждая операция увеличивает в 2 раза + 1 кол-во перемещений. Раскрыв скобки для n операций — получаем:

От суммы можно избавиться, ибо она равна:

p.s. я избавился от суммы в голове, вспомнив сумму членов бесконечно убывающей геометрической прогрессии, но я надеюсь математики покажут как правильно записать эти преобразования
Итого у нас после всех преобразований вышло:

То есть если нам захочется странного, например записать решение ханойской башни для 64 дисков, то никаких современных носителей информации нам не хватит. В действительности — нам вообще не надо ничего никуда записывать. Это все равно, что записывать все числа от 0 до +бесконечности, чтобы потом их использовать, потому что решение ханойской башни — это фрактал.

Фрактальная природа

Да да. Решение ханойской башни имеет фрактальную природу. Давайте посмотрим. Допустим у нас каждое действие записывается в строку. Тогда для башни из 6 дисков можно записать это как-то так:

Ну а поскольку это фрактал — то мы можем легко назвать любую операцию зная лишь её порядковый номер. И даже более, мы можем в точности восстановить положение всех дисков на момент любой операции.

Бинарный алгоритм

Итак, мы знаем точное количество операций, а так же знаем индекс операции, для которой мы хотим восстановить состояние.
Допустим у нас башня из 6 дисков (перемещаем как обычно, с 1-ой на среднюю ось), а значит операций у нас 2^6-1 = 63. Допустим нам требуется восстановить состояние для 49-ой операции.
Делим целочисленно 63 на 2. Получается 31. Это индекс операции, на которой будет перемещен 6-ой диск:

У нас 49-ый индекс операции. Это значит что 6-ой диск уже лежит на средней оси. Кроме того, поскольку мы находимся в правой части, то пятый диск у нас лежит либо на 3-ей оси, либо на 2-ой. Для того чтобы мы могли работать с башней по тому же алгоритму — отнимаем от 49-ой операции 32, находим индекс подоперации. Это 17. Для перемещения стека из 5 дисков нужна 31 операция, при этом 5-ый диск перемещается на 16-ю операцию и с 3-ей оси на 2-ую.
Итак число 17 лежит правее:

А это значит что диск 5 уже перемещен на вторую ось.
По аналогии восстанавливаем положение остальных дисков.

Реализация (бинарный способ)

Я добавил красивую отрисовку башенок. Согласитесь, скучно смотреть в консольный лог. Поэтому реализация разрослась, и я прикреплю полный проект (исходник + бинарник) в конце статьи. Здесь же приведу

код рекурсивной функции на Delphi

procedure TfrmView.RestoreDisk(size, actionIndex, actionCount, fromAxe, atAxe: Integer);
var pivot: Integer;
i: Integer;
thirdAxe: Integer;
begin
pivot := actionCount div 2;
thirdAxe := GetThirdIndex(fromAxe, atAxe);

if actionIndex = pivot then //попали в центр, значит знаем какой диск сейчас перекладывается
begin //и можем восстановить весь стек дисков меньшего размера. Конец рекурсии
FTowers[fromAxe].PutRing(size);
for i := size — 1 downto 1 do
FTowers[thirdAxe].PutRing(i);
FAction.FromIndex := fromAxe;
FAction.AtIndex := atAxe;
end
else
if actionIndex < pivot then
begin //значит выполняется стадия перекладывания подстека на независимую ось
FTowers[fromAxe].PutRing(size); //и нижний диск еще не переложен
RestoreDisk(size — 1, actionIndex, actionCount — pivot — 1, fromAxe, thirdAxe);
end
else
begin //значит выполняется стадия перекладывания подстека с независимой на нужную ось
FTowers[atAxe].PutRing(size); //и нижний диск уже переложен
RestoreDisk(size — 1, actionIndex — pivot — 1, actionCount — pivot — 1, thirdAxe, atAxe);
end;
end;

procedure TfrmView.RestoreTowers;
var index: Integer;
begin
ClearTowers(FTowers);
index := tbOperation.Position;
RestoreDisk(MaxRingCount, index, 2 shl (MaxRingCount — 1) — 1, 0, 1);
Invalidate;
end;

Треугольник Серпинского

Я хотел бы еще вскользь упомянуть интересную особенность. Если все возможные перемещения колец собрать в граф, то для каждого узла будет чаще всего по 3 связи. Все узлы и связи можно красиво расположить в форме треугольника. Треугольника Серпинского:

Подробнее об этом сказано на википедии вот тут. Что в общем не удивительно, потому что мы уже знаем фрактальную природу решения 😉

Итого

Я постарался показать, насколько иногда просто может решаться казалось бы не совсем очевидная задача. Более того, при внимательном изучении можно внезапно обнаружить совершенно другие интересные алгоритмы решения задачи, открывающие новые возможности. Ищите разные подходы, экспериментируйте, анализируйте. Ведь мы на то и программисты 😉
Спасибо тем кто дочитал, и кому статья понравилась. Прикрепляю демо пример, в котором можно поелозить трекбаром, и посмотреть на то как перекладываются башенки.

Пример бинарного алгоритма (exe + исходный код, Delphi)

ссылка на оригинал статьи http://habrahabr.ru/post/200758/