Ханойская башня — Википедия

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

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

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

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

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

// Ханойские башни #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; } 

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. 

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 

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) 

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);     } } 

#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].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Для некоторого ${\displaystyle k}$, ${\displaystyle 1\leq k<n}$, перенести верхние ${\displaystyle k}$ на стержень i, не являющийся ни начальным, ни конечным стержнем, затратив на это ${\displaystyle T(k,r)}$ ходов.
2. Не используя стержень i, содержащий теперь верхние ${\displaystyle k}$ дисков, перенести оставшиеся ${\displaystyle n-k}$ дисков на конечный стержень, используя только оставшиеся ${\displaystyle r-1}$ стержней и затратив на это ${\displaystyle T(n-k,r-1)}$ ходов.
3. Наконец, переместить верхние ${\displaystyle k}$ дисков на конечный стержень, затратив на это ${\displaystyle T(k,r)}$ ходов.

На весь процесс требуется ${\displaystyle 2T(k,r)+T(n-k,r-1)}$ ходов. Значение ${\displaystyle k}$ выбирается таким образом, чтобы значение этого выражения было минимальным. В случае 4 стержней, оптимальное ${\displaystyle k}$ равно ${\displaystyle n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1}$, где ${\displaystyle \left\lfloor \cdot \right\rceil }$ — это функция ближайшего целого.^[18]

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

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

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

Число перемещений дисков, которые должны совершить монахи, равно 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 ходов.

• Тест «Башня Лондона»

• последовательность A007664 в OEIS
• Константин Кноп. Ханойская башня  (неопр.). Элементы (22 октября 2012).
• Онлайн-игра Ханойские башни