Логическая игра ханойская башня. Игра башня ханоя онлайн. код рекурсивной функции на Delphi

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

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

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

Эту известную игру придумал французский математик Эдуард Люка , в 1883 году её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)» но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа - не более чем анаграмма фамилии изобретателя игры - профессора Люка (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 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)

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

#include #include 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 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

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

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

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

В культуре

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

Примечания

Ссылки

Wikimedia Foundation . 2010 .

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

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

Правила игры

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


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


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


Чувствуете рекурсию?
Перекладывание стека из 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 of Integer; procedure MoveRing(var AtTower: TTower); end; TTowers = array of TTower; procedure InitTowers(var towers: TTowers); implementation procedure InitTowers(var towers: TTowers); var i: Integer; begin towers.RingCount:= MaxRingCount; towers.RingCount:= 0; towers.RingCount:= 0; for i:= 0 to MaxRingCount - 1 do begin towers.Rings[i] := MaxRingCount - i; towers.Rings[i] := 0; towers.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 < AtTower.Rings); Dec(RingCount); AtTower.Rings := Rings; Rings := 0; Inc(AtTower.RingCount); end; end.
TTower - структура описывающая башню. В ней в RingCount хранится количество фактически одетых колец на башне. Размер колец хранится в массиве Rings от 1 и до MaxRingCount. Поскольку у нас 3 башни - то был объявлен тип TTowers = array 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.MoveRing(towers); //перемещаем последнее кольцо на нужную нам ось 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 операций - получаем:

От суммы можно избавиться, ибо она равна:

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.PutRing(size); for i:= size - 1 downto 1 do FTowers.PutRing(i); FAction.FromIndex:= fromAxe; FAction.AtIndex:= atAxe; end else if actionIndex < pivot then begin //значит выполняется стадия перекладывания подстека на независимую ось FTowers.PutRing(size); //и нижний диск еще не переложен RestoreDisk(size - 1, actionIndex, actionCount - pivot - 1, fromAxe, thirdAxe); end else begin //значит выполняется стадия перекладывания подстека с независимой на нужную ось FTowers.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 связи. Все узлы и связи можно красиво расположить в форме треугольника. Треугольника Серпинского:


Подробнее об этом сказано на википедии

Древняя и увлекательная головоломка теперь есть в наших мобильных телефонах, и на компьютерах. Игра Башня Ханоя прекрасно развивает логику и мышление, поэтому ее можно показывать детям с самого маленького возраста. Суть головоломки заключается в том, чтобы построить башню. Тебе дается три стержня, на одном есть башня, собранная из деталей разного размера. Тебе необходимо переместить ее на стержень с другой стороны. Есть, конечно, несколько условий в игре Tower of Hanoi. Нельзя поставить большую деталь на меньшую. Поэтому прежде, чем разбивать башню, подумай, куда ты поставить детали так, чтобы потом можно собрать ее заново на другом стержне. За один ход можно передвинуть только один диск. Существуют целые теории, как решить эту головоломку, но в игре Башня Ханоя тебе придется самому принимать решения. Решить задачу тебе необходимо за меньшее количество ходов. На каждом уровне количество дисков будет увеличиваться на один. О происхождении этой головоломки ходит не одна легенда. Так придуманная обычным математиком задача стала очень популярна, ведь ее решение потребует не слабой дедукции от игрока. Пройди все пять уровней и докажи любому, что ты не хуже какого-то там математика умеешь логически размышлять. Только начни играть в Башня Ханоя и ты не выпустишь из рук мобильный телефон. Интерес к этой игре оправдан, ведь каждый раз можно начать уровень сначала и попробовать новый способ перекладки башни на другой стержень.