29.09.2013

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

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

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

В статье будет много картинок. Объяснение, как решать задачу рекурсивно и как она решается бинарным поиском.

В общем статья посвящается тем смелым, кто пока еще боится Ханойской башни, но хочет перестать её бояться.

Правила игры

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

Итак у нас есть вот такая пирамидка:

И нам надо переложить её скажем на среднюю ось.

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

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

Чувствуете рекурсию?

Перекладывание стека из 5 дисков — это:

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

В свою очередь перекладывание стека из 4 дисков — это:

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

Вот и все.

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

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

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.

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

Мы легко можем подсчитать, сколько действий нам понадобится, чтобы переместить пирамидку.

Если мы перемещаем стек из одного диска, то нам нужно 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 связи. Все узлы и связи можно красиво расположить в форме Треугольника Серпинского.

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

Итого

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

Спасибо тем, кто дочитал и кому статья понравилась.

Источники:

1. habrahabr.ru