Легенда о ханойской башне кратко

Обновлено: 05.07.2024

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

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

При перестановке должны соблюдаться некоторые правила.

1) кружки переставляются с одного стержня на другой, при этом их укладывают друг на друга, так что получаются маленькие башни. Нельзя откладывать кружки в сторону или ставить один кружок вместо другого;

2) при каждом ходе двигается только один кружок. Нельзя переносить несколько кружков одновременно. Например, запрещено брать по кружку в каждую руку;

3) можно брать кружок лишь с вершины какой–нибудь башни и класть его только на вершину другой башни. Нельзя брать кружок из середины башни или вставлять его в середину другой башни;

4) запрещено класть больший кружок на меньший.

На рисунке изображены несколько разрешенных и несколько запрещенных ходов.

Так можно: Так нельзя:

Эту романтическую легенду, придумал в 1883 году французский математик ЭДУАРД ЛЮКА.

Франсуа Эдуард Анатоль Люка (François Édouard Anatole Lucas; 4 апреля 1842, Амьен- 8 октября 1891) французский математик, профессор. Работал в лицее Лунле-Гран в Париже. Важнейшие работы Люка относятся к теории чисел и неопределенному анализу. Считал, что с помощью машин или каких-либо приспособлений сложение удобнее производить в двоичной системе, чем в десятичной.

• В 1878 г. Люка дал критерий для определения того, простым или составным является число Мерсенна Mp = 2p - 1, ныне известный как тест Люка — Лемера. Применяя свой метод, Люка установил, что M127 = 2127 − 1 — простое число. В течение 75 лет это число оставалось наибольшим простым числом, известным науке. Оно же позволило ему определить 12-е совершенное число.

• Первым обратил внимание и описал свойства чисел, впоследствии названными его именем - чисел Люка.

• Описал свойства последовательностей, удовлетворяющих однородным линейным рекуррентным уравнениям второго порядка, частным случаем которых являются числа Фибоначчи. Такие последовательности теперь называются последовательностями Люка.

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

Где-то в непроходимых джунглях, недалеко от города Ханоя, есть монастырь бога Брахмы. В начале времен, когда Брама создавал Мир, он воздвиг в этом монастыре три высоких алмазных стержня и на один из них возложил 64 диска, сделанных из чистого золота. Он приказал монахам перенести эту башню на другой стержень (в соответствии с правилами, разумеется) С этого времени монахи работают день и ночь. Когда они закончат свой труд- наступит конец света.

III. Решение головоломки:

А) Формула зависимости ходов от числа кружков башни

Если составить таблицу зависимости ходов от числа кружков игры, то результат будет очевиден:

Число кружков : Оптимальное число ходов:

Получилась числовая последовательность: 1,3,7,15,31,.

Первое решение. Второе решение.

Если умножить предыдущее число на 2 и прибавить один, получим требуемое. 21 =2 ; 22=4; 23=8 ; 24=16; 25=32

7= 2*3+1 Вычитаем единицу из этих чисел, получаем нашу последовательность:

Обозначим n-ое число через a n , получаем формулу: 15= 24 -1

а 3 =2* а 2 + 1 an = 2n -1

B) Решение задачи на языке программирования.

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

Игра "Ханойские башни" состоит следующем. Есть N дисков и три стержня: А, В и С. В начальной конфигурации все диски надеты на один из стержней, образуя башню в виде пирамиды (меньшие диски в ней расположены поверх больших). Ход -> это перекладывание одного диска. Можно переместить верхний диск со стержня на стержень, но нельзя помещать больший диск поверх меньшего. Требуется указать последовательность ходов, перемещающих всю башню с исходного стержня на заданный.

Алгоритм решения задачи:

1. Если n>0, остановиться

2. Переместить верхние n-1 дисков со стержня А на стержень В, используя стержень С как вспомогательный.

3. Переместить оставшийся диск со стержня А на стержень С

4. Переместить n-1 дисков со стержня В на стержень С, используя стержень А как вспомогательный.

Нетрудно заметить, что этот алгоритм рекурсивный. Действительно, на шаге 2 и шаге 4 алгоритма требуется решить задачу, аналогичную первоначальной, только для меньшего числа дисков.

Рекурсивный алгоритм- это алгоритм, использующий в качестве вспомогательного самого себя.

Листинг программы на языке программирования Turbo Pascal.

PROGRAM hanoy; typebachnia =char; var a,b,c: bachnia; k, kol: integer;

procedure H (n: integer; a,b,c :bachnia); begin if n>0 then begin

H (n-1,a,c,b); write (‘переместить диск ’, n); writeln (a, ‘- > ,’ c); kol:=kol+1;

H (n-1,b,a,c); end; end;

begin write (‘ввести количество кружков =’); readln (k); a:=’A’; b:=’B’ ; c:=’C’;

H (k,a,b,c); writeln (‘количество шагов=', kol); end.

Результат тестирования программы

При количестве кружков К=3

переместить диск 1 А - > С

переместить диск 2 А - > В

переместить диск 1 С - > В

переместить диск 3 А - > С

переместить диск 1 В - > А переместить диск 2 В - > С

переместить диск 1 А - > С

КОЛИЧЕСТВО ШАГОВ = 7

(проверка формулы 2n -1 = 23 -1=7 шагов)

При количестве кружков К=4 переместить диск 1 А - > В переместить диск 2 А - > С переместить диск 1 В - > С переместить диск 3 А - > В переместить диск 1 С - > А переместить диск 2 С - > В переместить диск 1 А - > В переместить диск 4 А - > С переместить диск 1 В - > С переместить диск 2 В - > А переместить диск 1 С - > А переместить диск 3 В - > С переместить диск 1 А - > В переместить диск 2 А - > С переместить диск 1 В - > С

КОЛИЧЕСТВО ШАГОВ = 15

(проверка формулы 2n -1 = 24 -1=15 шагов)

Листинг программы на языке программирования QBasic.

REM ОСНОВНАЯ ПРОГРАММА

INPUT “введите N=”;N

PRINT “количество шагов=”; kol

REM РЕКУРСИВНАЯ ПОДПРОГРАММА

1: IF N=0 THEN RETURN

PRINT “переместить диск “;N ; A; “->”;C

Если использовать полученную формулу из п. III , раздела А) то можно подсчитать, что свою работу они закончат за ( 264 -1) шагов.

264 = 24 * 260 = 16* 260 ( 16 * (210 ) 6 ( 16*(10 3)6 ( 16 *1018 т. к. 210 = 1024 ( 1000 = 10 3 получили, что число ходов приблизительно равно шестнадцати квинтильонам.

В одних сутках 24 часа, в часе 60*60=3600 секунд.

Значит, в сутках 24* 3600= 86 400 секунд

В году- в 365 больше, т. е. приблизительно 32 миллиона секунд, или 32 * 106 секунд

Чтобы узнать, сколько лет необходимо монахам, нужно разделить одно из полученных нами чисел на другое:

(16 *1018 ) / (32 * 106 ) = 0,5 * 10 12 = 500 000 000 000 лет

D) Решение задачи на суперкомпьютере.

Представим себе вместо монахов будущий суперкомпьютер: Пусть он совершает в секунду 1 миллиард операций. Сколько времени понадобиться компьютеру переложить башню из 64 кружков?

Т. к. компьютер работает в миллиард раз быстрее монахов, то ему понадобиться в миллиард раз меньше времени - всего 500 лет.

Существует одна притча:

«Спорили два друга:

-Мир давно уже должен быть погибнуть!

-Почему ты так думаешь?

-Знаешь, существует древнее предание, по которому стоит перенести всего лишь 64 кружка и наступит конец света

- Всего лишь 64, стоит задуматься, что если один ход проделывать за 1 секунду, то в час можно сделать 3 600 перенесений

- А в сутки- около ста тысяч. В десять дней- миллион ходов. Миллионом же ходов можно, я уверен, перенести хоть тысячу кружков.

- Ошибаешься. Чтобы перенести всего 64 кружка, нужно уже круглым счетом 500 миллиардов лет!

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

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

Содержание

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

Решение

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

Код Грея, рефлексный двоичный код в двоичной системе счисления, в котором два соседних значения различаются только в одном двоичном разряде. Изначально, код Грея предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления. Код получил имя исследователя лабораторий 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->…

Легенда:
В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.

Франсуа Эдуард Анатоль Люка (1842-1891)

M32582 657 = 2^32 582 657 ? 1

является 44-м простым числом Мерсенна и содержит 9808358 цифр. В его поиске принимали участие тысячи людей по всему миру в рамках масштабного проекта распределенных вычислений — Great Internet Mersenne Prime Search(GIMPS): любой желающий мог скачать себе программу, которая периодически связывалась с основным сервером, получала от него задание, выполняла и передавала результаты обратно. Кстати, этот проект продолжает свою работу, а за нахождение простого числа из более чем 10^7 цифр назначена награда в 100000 долларов. Но важно другое: исследования простых чисел, в том числе и исследования Люка, казавшиеся ранее практически бесполезными, нашли широкое применение в криптографии.

Далее, именно Люка привлек внимание математиков (и не только!) к замечательной числовой последовательности:

Читайте также: