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

Перейти к навигацииПерейти к поиску
Модель Ханойской башни с восемью дисками

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

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

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

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

Решение

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

Существует несколько подходов к решению.

Рекурсивное решение

Рекурсивно решаем задачу «перенести башню из n−1 диска на 2-й штырь». Затем переносим самый большой диск на 3-й штырь, и рекурсивно решаем задачу «перенеси башню из n−1 диска на 3-й штырь».

Отсюда методом математической индукции заключаем, что минимальное число ходов, необходимое для решения головоломки, равно 2n − 1, где n — число дисков[2][3].

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

«Треугольное» решение

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

Циклическое решение

Обозначим через «1-2» такое действие: переложить диск или с 1-го штыря на 2-й, или со 2-го на 1-й, в зависимости от того, где он меньше. Тогда, чтобы решить головоломку с чётным количеством дисков, надо многократно повторять действия: 1-2, 1-3, 2-3. Если число дисков нечётно — 1-3, 1-2, 2-3.

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

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

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

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

hanoiSteps :: Int -> [(Int, Int)]
hanoiSteps n = step (max 0 n) 1 3 2 []
  where
    step 0 _ _ _ rest = rest
    step n f t s rest = step (n - 1) f s t $ (f, t) : step (n - 1) s t f rest

Пример алгоритма решения на языке 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)

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

public class Hanoi {
    public static void hanoiTowers(int quantity, int from, int to, int buf_peg)	{
        if (quantity != 0)
        {
            hanoiTowers(quantity-1, from, buf_peg, to);

            System.out.println("" + from + " -> " + to );

            hanoiTowers(quantity-1, buf_peg, to, from);
        }
    }

    public static void main(String[] args) {
        int start_peg = 1, destination_peg = 2, buffer_peg = 3, plate_quantity = 4;
        hanoiTowers(plate_quantity, start_peg, destination_peg, buffer_peg);
    }
}

Пример итеративного алгоритма решения на языке 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;
      }
   }
}

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

Решение для машины Тьюринга

В 1992 году студент второго курса РГАТУ им. П. А. Соловьёва Иван Басов, ныне доктор философии (PhD) , живущий и работающий в США, предложил запрограммировать головоломку «Ханойские башни» на машине Тьюринга[4]. Тогда же Иван предложил удобный способ описания размещения дисков по стержням, где каждому диску соответствует своя ячейка ленты. Первоначально все диски находятся на стержне A, поэтому все ячейки ленты содержат символ A. Слева и справа от этих ячеек размещены символы «#», ограничивающие исходные данные (пример: «…#AAAA#…»). Блок управления первоначально указывает на самую левую ячейку с символом A, соответствующую диску минимального диаметра. Один из вариантов входных данных, предложенных Иваном Басовым, подразумевал кодировку дополнительного стержня-приемника. Здесь же приведен упрощённый вариант задачи, где требуется переместить все диски со стержня A на любой другой стержень (либо B, либо C). Благодаря этому простому способу описания размещения дисков по стержням, Иван Басов, а также его научный руководитель В. Н. Пинаев написали каждый свою программу для машины Тьюринга[5]. В основе этих решений лежал известный простой нерекурсивный алгоритм перекладывания дисков[6].

Основная идея этого алгоритма звучит так:

  1. Каждый нечётный ход — это циклический ход первого диска:
    либо в направлении A⟶B⟶C⟶A⟶B⟶C⟶… (в случае чётного количества дисков),
    либо в направлении A⟶C⟶B⟶A⟶C⟶B⟶… (в случае нечётного количества дисков).
  2. Каждый чётный ход определяется однозначно (!):
    находим наименьший отличный от первого диск и перемещаем его на тот стержень, где нет первого диска.

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

Окончательно имеем следующий алгоритм:

  1. Перемещаем на один шаг по кругу A⟶B⟶C⟶A первый диск.
  2. Перемещаемся по дискам вправо до тех пор, пока идентификатор стержня совпадает с идентификатором стержня, на котором лежит первый диск.
  3. Если обнаружен знак конца дисков «#», то работа закончена.
  4. Если найден диск, лежащий на стержне, отличном от стержня первого диска, то перемещаем найденный диск на допустимый стержень (это третий оставшийся стержень, если исключить стержни первого и текущего дисков).
  5. Возвращаемся к пункту 1.

С этой задачей связана следующая интересная история. В 1992 году Иван Басов, будучи студентом второго курса РГАТУ им. П. А. Соловьёва, написал исследование под руководством В. Н. Пинаева и Б. Я. Фалевича, которое было представлено на всероссийский конкурс студенческих научных работ. Исследуя машину Тьюринга и головоломку «Ханойские башни», он провёл анализ нескольких алгоритмов, оценил число шагов машины Тьюринга, подробно описал программную реализацию и в том числе привёл таблицу управления, подобную вышеприведенной. Рецензентом этой работы оказался известный учёный сибирской школы алгебры и логики, А. С. Морозов, который сравнил Ивана с Левшой, «подковавшим» эту программистскую «блоху». В последующие десятилетия эта задача и её модификации неоднократно предлагались на российских и международных студенческих олимпиадах по программированию[7][8][9][10]. Кроме того, пример решения головоломки «Ханойские башни» на машине Тьюринга признан более содержательным, чем операции над унарными числами, которыми изобилуют примеры в публикациях и методических пособиях по этой тематике, и рекомендован при изучении машины Тьюринга[5].

Варианты

Перемешанные Ханойские башни

Перемешанные Ханойские башни — обложка журнала «Квант», № 10, 1991

В 1990 году преподаватель информатики РГАТУ им. П. А. Соловьёва В. Н. Пинаев предложил рассмотреть такую задачу: все диски расположены в произвольном порядке на всех трёх стрежнях, требуется собрать их на одном. Эта задача также всегда разрешима и названа её создателем «перемешанной Ханойской башней» или «Ханойской п-башней». Заметим, что идея этой головолмки идёт от кубика Рубика: запутаем расположение частей головоломки, а потом постараемся привести её к первоначальному виду с помощью разрешенных действий[11][12][13].

Следует отметить, что в общем случае изначальное расположение дисков может быть совершенно произвольным, и диск большего диаметра может оказаться на диске меньшего диаметра. В таком случае «Ханойская п-башня» является «сильно перемешанной». Если же изначальное расположение дисков исключает такое положение, то она является «слабо перемешанной». «Слабо перемешанная Ханойская башня» также может быть представлена методом Басова для машины Тьюринга (пример входных данных: «…#ACABC#…»)[4][5].

Сдвоенные Ханойские башни

Эта головоломка также была предложена В. Н. Пинаевым и использовалась на ученических и студенческих олимпиадах по программированию под названиями «Чёрный ящик», «Кодовый замо́к» и «Светофор». Смысл головоломки состоит в том, что две случайным образом «перемешанные Ханойские башни» (или «Ханойские п-башни») закодированные методом Басова для машины Тьюринга были «соединены» общим диском минимального диаметра. Чтобы это наглядно представить, нужно абстрагироваться от физических свойств «Ханойских башен» и рассматривать их только в контексте кода Басова[4][5].

Сдвоенные Ханойские башни — конкурс рекордов ручного открывания замка, 1998

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

В конструкции замка была предусмотрена внутренняя память из одной ячейки (недоступной пользователю). В этой ячейке хранилось состояние замка, которое определялось номером первой нажатой кнопки. Как используется и используется ли вообще эта ячейка — было неизвестно.

Принцип срабатывания элементов черного ящика был основан на известной игре-головоломке «Ханойская башня». Фактически, в зависимости от номера первого нажатого элемента замок распадался на две части: левую и правую. Каждая часть представляла собой отдельную Ханойскую башню со своими стержнями и дисками. Но диск минимального диаметра был общим для этих частей. Цвет элемента указывал, на каком стержне находится соответствующий диск. Отличие от стандартной Ханойской башни заключалось в том, что в исходном положении диски были размещены на стержнях в произвольном порядке. Задача в такой постановке называется «перемешанной Ханойской башней» или «Ханойской п-башней»[11][12][13].

Эта задача, как и многие другие, является многоуровневой. Можно было сначала собирать одну пирамиду, затем другую. А можно было собирать «одновременно» обе пирамиды. Очень важен был первый ход, который во многом определялся начальной раскраской. Действительно, если первым ходом нажать первую или последнюю кнопку, то мы будем иметь дело с одной пирамидой, но большего размера.

По задаче «Светофор» в декабре 1998 года в Санкт-Петербурге был проведен первый Всероссийский очно-заочный турнир «ПИК-АСМ98». В этом турнире приняли участие программисты со всей страны[7][8][9].

С четырьмя и более стержнями

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

Очевидно, что для любого количества стержней существует алгоритм для нахождения оптимальных решений, достаточно представить головоломку в виде неориентированного графа, сопоставив размещениям дисков вершины, а ходам — рёбра, и использовать любой алгоритм поиска (например, поиск в ширину) для нахождения оптимального решения. Однако эффективной стратегии определения оптимального решения для большого числа дисков нет: количество ходов, необходимое для решения головоломки с 10 стержнями и 1000 дисками, остаётся неизвестным.

Существует предположительно оптимальный алгоритм Фрейма — Стюарта, разработанный в 1941 году[14]. Связанная гипотеза Фрейма — Стюарта утверждает, что алгоритм Фрейма — Стюарта всегда находит оптимальное решение. Оптимальность алгоритма Фрейма — Стюарта была экспериментально проверена вплоть до 30 дисков на 4 стержнях[15]. В 2014 году было окончательно доказано, что для четырёх стержней Алгоритм Фрейма — Стюарта является оптимальным[16].

Другие варианты решения Ханойской башни с четырьмя стержнями рассматриваются в обзорной статье Пола Стокмайера[17].

Алгоритм Фрейма — Стюарта

Алгоритм Фрейма — Стюарта, дающий оптимальное решение для четырёх и предположительно оптимальное решение для большего количества стержней, описывается следующим образом:

  • Пусть  — количество дисков.
  • Пусть  — число стержней.
  • Определим как наименьшее число ходов, необходимое для переноса n дисков с использованием r стержней.

Алгоритм может быть описан рекурсивно:

  1. Для некоторого , , перенести верхние на стержень i, не являющийся ни начальным, ни конечным стержнем, затратив на это ходов.
  2. Не используя стержень i, содержащий теперь верхние дисков, перенести оставшиеся дисков на конечный стержень, используя только оставшиеся стержней и затратив на это ходов.
  3. Наконец, переместить верхние дисков на конечный стержень, затратив на это ходов.

На весь процесс требуется ходов. Значение выбирается таким образом, чтобы значение этого выражения было минимальным. В случае 4 стержней, оптимальное равно , где  — это функция ближайшего целого.[18]

Легенды

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

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

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

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

В культуре

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

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

Ханойская башня — одна из традиционных головоломок в видеоиграх канадской компании BioWare — в частности, «Jade Empire», «Star Wars: Knights of the Old Republic», «Mass Effect» и «Dragon Age: Inquisition». Встречается она и в квесте Legend of Kyrandia II.

В сериале «Доктор Кто» (классические серии; серия «Небесный игрушечник») Игрушечник использует Ханойскую башню из 10 колец как задание для Доктора, при этом правила усложнены: нужно собрать её за точную последовательность из 1023 ходов.

Примечания

  1. ↑ 1 2 Мартин Гарднер, Математические головоломки и развлечения
  2. ↑ Petković, Miodrag. Famous Puzzles of Great Mathematicians (неопр.). — AMS Bookstore, 2009. — С. 197. — ISBN 0-8218-4814-3.
  3. ↑ Graham, Ronald. Concrete Mathematics: A Foundation for Computer Science (англ.). — Addison–Wesley, 1998. — P. 21. — ISBN 0201558025.
  4. ↑ 1 2 3 Basov, I. (1993). "Решение головоломки «Ханойские башни» на машине Тьюринга". Министерство науки, высшей школы и технической политики России. Комитет по высшей школе. Рыбинский авиационный технологический институт. Архивировано 7 июля 2024.
  5. ↑ 1 2 3 4 Пинаев, В.Н. (2002). "Каждый выбирает свой ПИК!". Информатика (33): 18—27.
  6. ↑ Брудно, А.А. Московские олимпиады по программированию / А.А. Брудно, А.И. Каплан. — Москва : Наука. Гл. ред. физ.-мат. лит., 1990.
  7. ↑ 1 2 Пинаев, В.Н. (2000). "Опыт организации и проведения молодежных чемпионатов по информатике и программированию". Информатика (12): 29—31.
  8. ↑ 1 2 Пинаев, В.Н. Теория и практика творческих соревнований по информатике. — Рыбинск : РГАТА, 2000. — P. 83.
  9. ↑ 1 2 Пинаев, Владимир Николаевич (2001). Методика организации и проведения творческих соревнований по информатике (кандидат педагогических наук). Архивировано 8 июля 2024. Дата обращения: 8 июля 2024.
  10. ↑ Чемпионат ПИК-2002: Задание C. "Ханойская башня". Архивировано 14 мая 2002 года.
  11. ↑ 1 2 Пинаев, В. (1991). "Перемешанные Ханойские Башни". Квант (10): обложка. Архивировано 8 июля 2024.
  12. ↑ 1 2 Пинаев, В. (1991). "Перемешанные Ханойские Башни". Квант (11): 54. Представлена в статье: Савин А. «Ханойские Башни», Журнал «Квант», № 11, 1991, с. 52-54
  13. ↑ 1 2 Пинаев, В.Н. (1992). "Ханойские перемешанные башни". Информатика и образование (3—4): 97—98.
  14. ↑ Solution to advanced problem 3819, American Mathematical Monthly, 1941.
  15. ↑ Korf, Richard E., and Ariel Felner. Recent Progress in Heuristic Search: a Case Study of the Four-Peg Towers of Hanoi Problem (англ.) // IJCAI[англ.] : journal. — 2007. — P. 2324—2329. Архивировано 24 сентября 2015 года.
  16. ↑ Bousch, T. (2014). "La quatrième tour de Hanoï" (PDF). Bulletin of the Belgian Mathematical Society - Simon Stevin (фр.). 21: 895—912. Архивировано (PDF) 20 октября 2023.
  17. ↑ Paul Stockmeyer. Variations on the Four-Post Tower of Hanoi Puzzle (англ.) // Congressus Numerantium. — 1994. — Vol. 102. — P. 3—12. Архивировано 4 марта 2012 года.
  18. ↑ University of Toronto CSC148 Slog (5 апреля 2014). Дата обращения: 22 июля 2015. Архивировано 1 октября 2015 года.
  19. ↑ Рассел, Эрик Фрэнк. Ваш ход // Если. — 1994. — Апрель. — С. 34—42.

См. также

Ссылки