Ханойская башня

Модель Ханойской башни с восемью дисками

Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

История создания головоломки

Эту известную игру придумал французский математик Эдуард Люка, в 1883 году^[1] её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)»^[1] но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа — не более чем анаграмма фамилии изобретателя игры — профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).

Ход решения головоломки с четырьмя дисками.

Решение

Блок схема рекурсивного алгоритма решения.

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

Применение кода Грея для решения

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Код Грея, рефлексный двоичный код в двоичной системе счисления, в котором два соседних значения различаются только в одном двоичном разряде. Изначально, код Грея предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления. Код получил имя исследователя лабораторий Bell Labs Фрэнка Грея. Он использовал этот код в своей импульсной системе связи, для чего был написан патент за номером 2632058.

Коды Грея применяются в решении задачи о Ханойских башнях. Пусть N — количество дисков. Начнём с кода Грея длины N, состоящего из одних нулей (то есть G(0)), и будем двигаться по кодам Грея (от G(i) переходить к G(i+1)). Поставим в соответствие каждому I-ому биту текущего кода Грея I-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита I как перемещение I-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t->…

Реализации алгоритма  

Пример алгоритма решения на языке C++:

// Ханойские башни
#include <iostream>
 
using namespace std;
 
void hanoi_towers(int quantity, int from, int to, int buf_peg)  //quantity-число колец, from-начальное положение колец(1-3),to-конечное положение колец(1-3)
{                                                               //buf_peg - промежуточный колышек(1-3)
        if (quantity != 0)
        {
                hanoi_towers(quantity-1, from, buf_peg, to);
 
                cout << from << " -> " << to << endl;
 
                hanoi_towers(quantity-1, buf_peg, to, from);
        }
}
 
int main()
{
        setlocale(LC_ALL,"rus");
        int start_peg, destination_peg, buffer_peg, plate_quantity;
        cout << "Номер первого столбика:" << endl;
        cin  >> start_peg;
        cout << "Номер конечного столбика:" << endl;
        cin  >> destination_peg;
        cout << "Номер промежуточного столбика:" << endl;
        cin  >> buffer_peg;
        cout << "Количество дисков:" << endl;
        cin  >> plate_quantity;
 
        hanoi_towers(plate_quantity, start_peg, destination_peg, buffer_peg);
return 0;
}

Пример алгоритма решения на языке Pascal:

program hanoi-bns(input,output);
var n:integer;
procedure tower(k:integer;a,b,c:char);
begin
     if k>1 then tower(k-1,a,c,b);
     writeln('from ',a,' to ',b);
     if k>1 then tower(k-1,c,b,a)
end;
begin
     read(n);
     tower(n,'A','C','B')
end.

Пример алгоритма решения на языке Python:

def Hanoi(n, A, C, B):
    if n != 0:
        Hanoi(n - 1, A, B, C)
        print 'Move the plate from', A, 'to', C
        Hanoi(n - 1, B, C, A)

Пример итеративного алгоритма решения на языке C

#include <stdio.h>
#include <math.h>
 
void carryingOver(int, int, int);
 
main()
{
   int number, countDisk, counter = 1, count;
 
   printf("Введите количество дисков: "); /* Ханойская башня */
   scanf("%d", &number);
 
   while (counter <= pow(2, number) - 1) { /* Запускаем цикл повторений */
 
      if (counter % 2 != 0) { /* На нечетном ходу мы будем трогать только самый маленький диск */
         printf("%3d %d ", counter, 1);
         carryingOver(number, counter, 1); /* С помощью этой функции определяем для данного диска перемещение */
      }
 
      else {  /* Определяем диск который нужно переместить на четном ходу */
         count = counter;
         countDisk = 0;
 
         while (count % 2 == 0) {  /* Диск который нужно переместить */
            countDisk++;           /* будет числом деления номера хода на 2 без остатка */
            count = count / 2;
         }
         printf("%3d %d ", counter, countDisk + 1);
         carryingOver(number, counter, countDisk + 1);
      }
      counter++;
   }
   return 0;
}
 
/* Функция определения перемещения дисков */
void carryingOver(int n ,int i, int k)
{
   int t, axisX, axisY, axisZ;
 
   if (n % 2 == 0) {  /* Определяем порядок осей в зависимости от четности */
      axisX = 1;      /* и не четности количества дисков */
      axisY = 2;
      axisZ = 3;
   }
 
   else {
      axisX = 1;
      axisY = 3;
      axisZ = 2;
   }
 
   /* Номер хода можно представить единственным образом */
   /* как произведение некоего нечетного числа на степень двойки */
   /* k будет номером диска который мы перемещаем */
   t = ((i / pow(2, k - 1)) - 1) / 2;
 
   if (k % 2 != 0) {    /* Определяем перемещение дисков  для нечетного хода */
 
      switch (t % 3) {         /* Выбираем перемещение в зависимости от данного условия */
         case 0:               
            printf("%d -> %d\n", axisX, axisY);
            break;
         case 1:
            printf("%d -> %d\n", axisY, axisZ);
            break;
         case 2:
            printf("%d -> %d\n", axisZ, axisX);
            break;
      }
   }
 
   else {     /* Определяем перемещение дисков  для чётного хода */
 
      switch (t % 3) {
         case 0:
            printf("%d -> %d\n", axisX, axisZ);
            break;
         case 1:
            printf("%d -> %d\n", axisZ, axisY);
            break;
         case 2:
            printf("%d -> %d\n", axisY, axisX);
            break;
      }
   }
}

Существуют программы визуализации решения этой головоломки.

Легенды

Легенда гласит, что в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и на один из них возложил 64 диска. Брахма поместил на один из стержней 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем.

Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

Количество перекладываний в зависимости от количества колец вычисляется по формуле $2^n-1$.

Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.

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

В культуре

В рассказе Эрика Фрэнка Рассела "Ваш ход" ("Quiz Game", в другом переводе "Игра на выживание")^[2] чтобы оттянуть время казни главный герой выбирает игру в Ханойскую башню с 64 дисками в качестве последней игры. Объявленные правила модифицированы для двух игроков - игроки должны перекладывать диски по одному за ход, победителем считается тот, кто сделает последний ход. Герой называет такую игру "арки-маларки" и клянётся, что "священнослужители Бенаресского храма" на Земле играют в эту игру.

Примечания

1. ↑ ^{1 2} Мартин Гарднер, Математические головоломки и развлечения
2. ↑ Рассел, Эрик Фрэнк (4 1994). «Ваш ход». Если: 34-42.

Ссылки