Hi-Tech  ->  Компьютеры  | Автор: | Добавлено: 2015-03-23

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

Постоянный интерес к старым задачам обусловлен множеством причин. Это и красивые легенды, обрамляющие условие, и изящные решения, и интересные расширения, вытекающие из исходных ограничений. В «Сборнике задач по курсу информатики» к учебникам за 10-11 класс автора Белоусова, Веприк представлены более 600 задач разного уровня сложности для абитуриентов и школьников. Задача о Ханойских башнях, представленная в задачнике, сопровождается одной из самых интригующих легенд о конце света. Дополнительный колорит ей придает блеск золотых дисков и алмазных стержней

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

I. Правила игры.

Правила игры «Ханойская башня» состоят в следующем:

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

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

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

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

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

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

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

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

II. Легенда

Эту романтическую легенду, придумал в 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

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

3= 2*1+1

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

15= 2*7+1 1= 21 -1

31= 2*15+1 3= 22 -1

. 7= 23 -1

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

а 1 =1 31= 25 -1

а 2 =2* а 1 + 1.

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

а n+1 =2* а n + 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;

{a,b,c - наименование стрежней, k - количество дисков}

{ kol- подсчет количества шагов}

{процедура, описывающая рекурсивный алгоритм} procedure H (n: integer; a,b,c :bachnia); begin if n>0 then begin

{ перемещаем верхние n-1 дисков, с А на В}

{ используя С как вспомогательный стержень}

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

{пронумеруем стержни для работы в программе}

GOSUB 1 {вызов подпрограммы}

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

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

1: IF N=0 THEN RETURN

{ моделируем рекурсивное обращение, меняем местами значения стержней}

GOSUB 1

{ моделируем возврат, восстанавливаем значения}

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

KOL=KOL+1 {считаем количество шагов}

{ моделируем рекурсивное обращение, меняем местами значения стержней}

GOSUB 1

{ моделируем возврат, восстанавливаем значения}

C) Время от «начала» и до «конца» света.

Интересно подсчитать, за сколько времени монахи монастыря Брамы (см. легенду) закончат работу и наступит «конец» света.

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

Предположим, что монахам требуется 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 миллиардов лет!

- Да, это очень большой срок»

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

Комментарии


Войти или Зарегистрироваться (чтобы оставлять отзывы)