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

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

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

    Правила игры


    Они очень просты. Есть 1 пирамидка с дисками разного размера, и еще 2 пустые пирамидки. Надо переместить диски с одной пирамидки на другую. Перекладывать можно только по одному диску за ход. Складывать диски можно только меньший на больший.
    Итак у нас есть вот такая пирамидка:
    image
    И нам надо переложить её скажем на среднюю ось.
    Если начать решать задачу не с начала, а с конца — она оказывается очень простой. Давайте подумаем. Чтобы переложить пирамидку на вторую ось — нам надо переложить самый нижний диск, а сделать это можно только когда 4 верхних диска будут на третьей оси:
    image
    Для того, чтобы переложить 4 диска на третью ось нужно по сути решить ту же задачу, но для 4-х дисков. То есть на третью ось мы можем переложить 4-ый диск только тогда, когда у нас 3 диска на второй оси:
    image
    Чувствуете рекурсию?
    Перекладывание стека из 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 операций — получаем:
    image
    От суммы можно избавиться, ибо она равна:
    image
    p.s. я избавился от суммы в голове, вспомнив сумму членов бесконечно убывающей геометрической прогрессии, но я надеюсь математики покажут как правильно записать эти преобразования
    Итого у нас после всех преобразований вышло:
    image

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

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


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

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


    Итак, мы знаем точное количество операций, а так же знаем индекс операции, для которой мы хотим восстановить состояние.
    Допустим у нас башня из 6 дисков (перемещаем как обычно, с 1-ой на среднюю ось), а значит операций у нас 2^6-1 = 63. Допустим нам требуется восстановить состояние для 49-ой операции.
    Делим целочисленно 63 на 2. Получается 31. Это индекс операции, на которой будет перемещен 6-ой диск:
    image
    У нас 49-ый индекс операции. Это значит что 6-ой диск уже лежит на средней оси. Кроме того, поскольку мы находимся в правой части, то пятый диск у нас лежит либо на 3-ей оси, либо на 2-ой. Для того чтобы мы могли работать с башней по тому же алгоритму — отнимаем от 49-ой операции 32, находим индекс подоперации. Это 17. Для перемещения стека из 5 дисков нужна 31 операция, при этом 5-ый диск перемещается на 16-ю операцию и с 3-ей оси на 2-ую.
    Итак число 17 лежит правее:
    image
    А это значит что диск 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 связи. Все узлы и связи можно красиво расположить в форме треугольника. Треугольника Серпинского:
    image
    Подробнее об этом сказано на википедии вот тут. Что в общем не удивительно, потому что мы уже знаем фрактальную природу решения ;)

    Итого


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

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

    Similar posts

    Comments 29

      +1
      Самое простое решение — готовая последовательность ходов: 1-2, 1-3, 2-3 для четного количества колец или 1-3, 1-2, 2-3 для нечетного. Числа — номера пирамидок, с которых или на которые надо переложить кольцо. Например, 1-2 означает либо с 1 на 2, либо с 2 на 1 — направление определяется размерами верхних колец. Повторяем нужную последовательность пока задача не окажется решена. Это решение не дает понимания сути процесса, зато очень легко применяется на практике без какой-либо вычислительной техники — достаточно уметь считать до трех. :)
        +1
        Да, это решение описывается в русской википедии (единственное, другие решения только в английской вики). Я специально не стал на нем останавливаться, потому что понимания сути никакого.
          0
          В вики есть? Интересно. Не знал. Я его нашел случайно еще в школе. А теперь очень удобно издеваться над людьми в пьяных компаниях. :)
        +1
        Сразу вспоминается фильм «планета обезьян».
        PS: ханойские башни на флеше без смс: igroflot.ru/logic/flash_game_206/
          0
          Мне больше по душе дзен-алгоритм (вроде так называли в учебнике «Алгоритмика»): «нетронутые поля меняются по кругу»
            0
            Причём в обратном направлении.
            –4
            Пообщавшись с некоторыми знакомыми программистами, внезапно обнаружил, что не все знают про Ханойскую башню, а среди тех кто знает — мало кто понимает как решается эта задача.


            Вы издеваетесь? Задача давалась нам классе в 3 на уроках информатики, причем для самостоятельного решения.

            Варианты решений конечно хорошо описали, но те программистов кто не понимает такую элементарщину надо реально гнать из профессии.
              0
              Спешу Вас разочаровать — по современной программе ни в 3 классе, ни в 9 эта задача не предусмотрена. И я не знаю как в 3, но 9 классники ее самостоятельно не решают! Разве что 1-2 на группу из 10 чел. отобранных в группу программирования на доп занятия!
              Хотя совершенно с вами согласен — кто не может решить — не программист, а кодер!
                +1
                Я просто оставлю это здесь:

                http://festival.1september.ru/articles/310523/

                Шел тот самый 1995 год, у нас была похожая структура урока(Правда там был пакет роботландия(ну или что то сильно похожее, не помню уже названия точного, но «игры» те же) который еще на УКНЦ работал), всем желающим было предложено самостоятельно разработать алгоритм для решения Ханоских башен со сложностью до 8 колец. Как ни странно, но не справилось с задачей буквально пара тройка человек, из 27. По другим классам из параллели аналогичная ситуация. Вполне себе обычный гимназический класс был.
                  0
                  Проект «Роботландия» хорош (насколько может быть хорош любой проект в современном копирастическом мире учебного книгоиздательства)…
                  Но к типовым программам он почти не имеет отношения. И к практике в школах — тем более.
                    0
                    Еще скажите что к обучению алгоритмизации он не имеет никакого отношения? И насколько я могу судить, многие учебники информатики содержат курс рассчитаный как раз на этот пакет.

                    Не имеет отношению к реальному программированию? Не имеет. Но это не позволяет на псевдокоде обучаться алогоритмам.
                +1
                программистов кто не понимает такую элементарщину надо реально гнать из профессии

                Программистов практически не останется :(

                Поделюсь печальным наблюдением на эту тему. Мы выбрали эту задачу на собеседование программистов C++ и Java в прошлом году. При этом разрешили пользоваться интернетом. Вот только ни википедия, ни разжованный вариант на стековерфлоу почему-то людям не помогали и за отведенные на решение часы хороший результат был в лучшем случае у одного из двадцати. Большинство не то что бы закодили, они даже сам алгоритм не смогли понять (ни итеративную, ни рекурсивную версии).
                  0
                  Вот вот. Это и стало причиной написания статьи. Сначала я узнал, что оказывается не все умеют решать Ханойскую башню, а когда полез смотреть в интернет, понял что понятного материала на эту тему нет. Я постарался объяснить понятнее, чем на вики и стековерфлоу.
                  Глядишь — теперь больше народу пройдет собеседование у вас :D
                0
                memcpy(tower[1], tower[0], sizeof(**tower));
                memset(tower[0], 0, sizeof(**tower));
                  0
                  Что это значит — я прекрасно знаю, но к чему бы это?
                  0
                  Алогитмичиская сложность — поправьте этот подзаголовок в статье
                    0
                    Поправил, спасибо. Проверку орфографии не использую просто, вот как-то и пропустил.
                    0
                    Моим первым приложением, использующем рекурсию, было не вычисление факториала, а именно Ханойская башня. Спасибо за статью.
                      +1
                      Эту бы статью в годы моего детства, когда я пытался пройти эту локацию



                      P.S. для тех, кто не знает — это «инвертированные Ханойские башни» из Kyrandia 2
                        0
                        Кстати Ханойские башни встречаются во многих играх, в особенности во всяких квестах.
                        0
                        Искал этот рассказ, а нашёл на элементах такую же задачу с усложнением в виде дополнительного правила.
                          +2
                          Прочитав заголовок, подумал, что автор предлагает надеть диски разного размера на пальцы, и перенадевать с одного на другой.
                          В качестве развлечения в дороге, например.
                          Milfgard, ловите идею, пока горячая :-)
                            +1
                            Поймал, спасибо. Только не знаю, что с ней пока делать. Диски на пальцах держать неудобно, потому что диски большие и крулые, а пальцы, увы, сходятся у ладони. Я вот вырезал прототип трёх из бумаги, проверил. Да и вообще, тренд такой, что в дорогу берут либо компанейские настолки у нас, либо планшеты у Яблока и Гугла.
                              0
                              Ну, можно не диски, а полоски разной длины с дырками у одного из концов… Типа ваших скидочных карт
                              Не знаю, правда, будет ли кто заморачиваться с покупкой…
                                0
                                ещё альтернативное применение у них получится — закладки для книг
                                  0
                                  У нас для таких целей йо-йо и кубики Рубика берут. Одному в метро посидеть или в дороге поиграть. Особо циничное издевательство — подарить человеку кубик Рубика 2х2, который он сначала считает предельно простым, а потом, где-то через час, начинает сомневаться в собственном интеллекте. Были дорожные «НЛО» Рубика, но пошли плохо. Ещё хорошо лабиринты идут, в которых надо шарик прогнать через полосу препятствий. А вот любые головоломки кроме кубиков — не очень. Я же говорю, планшеты отлично заменяют.
                                  +2
                                  Совсем необязательно дискам быть круглыми. Могут быть узкими и вытянутыми.

                                  А если такая игра в «рабочем положении» будет напоминать кастет, тогда в неё можно будет играть и по дороге от электрички до дома тёмным вечером :-)
                                0
                                когда-то сталкивался с задачей «постройки» башни с произвольным количеством дисков и осей и известной конечной осью(на которую собирать). К стыду своему, решить не смог. С интересом бы почитал об алгоритме для такого случая.
                                  0
                                  Для произвольного кол-ва дисков и осей задача перемещения за минимальное число ходов не решена. Только строить граф всех перемещений и делать поиск пути в графе.

                                Only users with full accounts can post comments. Log in, please.