Ханойська вежа

Ханойська вежа є однією з найпопулярніших головоломок XIX століття. Це завдання, яке ілюструє рекурсію, дуже люблять програмісти.

Правила гри «Ханойська вежа» полягають у наступному:

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

При перестановці повинні дотримуватись деяких правил.

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

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

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

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

На малюнку зображено кілька дозволених та кілька заборонених ходів.

Так можна: Так не можна:

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

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

• Першим звернув увагу та описав властивості чисел, згодом названими його іменем – чисел Люка.

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

• Вигадав ряд цікавих завдань, у тому числі відому головоломку Ханойська вежа.

Десь у непрохідних джунглях, неподалік міста Ханоя, є монастир бога Брахми. На початку часів, коли Брама створював Світ, він спорудив у цьому монастирі три високі алмазні стрижні і на один з них поклав 64 диски, зроблені з чистого золота. Він наказав ченцям перенести цю вежу на інший стрижень (відповідно до правил, зрозуміло) З цього часу ченці працюють день і ніч. Коли вони закінчать свою працю-настане кінець світу.

ІІІ. Розв'язання головоломки:

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

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

Кількість гуртків : Оптимальна кількість ходів:

Вийшла числова послідовність: 1,3,7,15,31,.

Перше рішення. Друге рішення.

Питання: Як дізнатися чергове число послідовності, знаючи попереднє? Випишемо ступеня числа 2

Якщо помножити попереднє число на 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=”;

PRINT "кількість кроків ="; kol

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

1: IF N=0 THEN RETURN

PRINT "перемістити диск"; N; A; "->";C

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 = 86400 секунд

У році - в 365 більше, тобто приблизно 32 мільйонисекунд, або 32*106 секунд

Щоб дізнатися, скільки років необхідно ченцям, потрібно розділити одне з отриманих чисел на інше:

(16 * 1018) / (32 * 106) = 0,5 * 10 12 = 500 000 000 000 років

Так що якщо вас турбує «кінець» світла, що наступає, то можна не хвилюватися, п'ятсот мільярдів років-термін досить великий.

D) Розв'язання задачі на суперкомп'ютері.

Уявімо собі замість ченців майбутній суперкомп'ютер: Нехай він здійснює за секунду 1 мільярд операцій. Скільки часу потрібно комп'ютеру перекласти вежу з 64 гуртків?

Оскільки комп'ютер працює в мільярд разів швидше за ченців, то йому знадобиться в мільярд разів менше часу - всього 500 років.

Існує одна притча:

«Сперечалися двоє друзів:

-Світ давно вже повинен бути загинути!

-Чому ти так думаєш?

-Знаєш, існує давнє переказ, за яким варто перенести всього лише 64 гуртки і настане кінець світу

- Всього лише 64, варто задуматися, що якщо один хід проробляти за 1 секунду, то за годину можна зробити 3600 перенесень

- А за добу- близько ста тисяч. У десять днів-мільйон ходів. Мільйоном же ходів можна, я певен, перенести хоч тисячу гуртків.

- Помиляєшся. Щоб перенести всього 64 гуртки, потрібно вже круглим рахунком 500 мільярдів років!

- Так, це дуже великий термін»

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