Презентація на тему:
Ханойська башта, або один чудовий алгоритм

Ханойська башта, або один чудовий алгоритм {

Одна із стародавніх легенд свідчить: «У непрохідних джунглях недалеко від міста Ханоя є храм бога Брами. У ньому знаходиться бронзова плита з трьома діамантовими стрижнями. на один з стрижнів бог при створенні світу нанизав 64 диска різних діаметрів з чистого золота. Найбільший диск лежить на бронзовій плиті, а інші утворюють піраміду, що звужується догори. це вежа Брами. Працюючи день і ніч, жерці храму переносять диски з одного стрижня на іншій, дотримуючись законів Брами . Коли всі 64 диска будуть   перенесені з одного стрижня на іншій, настане кінець світу »

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

Ця давня легенда покладена в основу завдання про Ханойські вежі: перемістити n дисків зі стрижня 1 на стрижень 3, використовуючи проміжний стрижень 2 і дотримуючись законів Брами.

Для перенесення вежі з 1 диска, потрібно 1 хід: 1-3 Для переносу 2 дисків, 3 ходу: 1-2; 1-3; 2-3 Для перенесення вежі з 3 дисків потрібно 7 ходів: 1-3; 1-2; 3-2; 1-3; 2-1; 2-3; 1-3 і т.д. Зверніть увагу, за перші три ходи ми переносимо вежу з двох верхніх дисків на другий проміжний стержень. Потім переносимо найбільший диск з першого стрижня на третій і ще раз проробляємо добре знайому нам операцію: переносимо вежу з двох дисків на третій диск.

Отже, щоб перенести вежу з чотирьох дисків з першого стрижня на третій, необхідно діяти за планом: 1) перенести вежу з трьох верхніх дисків з першого стрижня на другий (7 ходів); 2) найбільший диск перенести з першого стрижня на третій (1 хід); 3) перенести вежу з трьох дисків з другого стрижня на третій (7 ходів). Всього на перенесення потрібно 15 ходів.

Розмірковуючи аналогічним чином, порахуємо число ходів, необхідних для перенесення вежі з п'яти дисків:?? 15 + 1 + 15 = 2 • 15 + 1 = 31.? Для башти з 6 дисків отримуємо: 2 • 31 + 1 = 63 і т. д.

Розглянутий нами Алгоритм рішення задачі «Ханойська башта» володіє одним дивовижну властивість: у ході його виконання для вежі, що складається з n кілець, ми використовуємо алгоритм для трохи більш простій ситуації - перенесення вежі, що складається з n - 1 кільця. У свою чергу, в алгоритмі для вежі з n - 1 кільця використовується цей же алгоритм для n - 2 кілець і т. д.

Прийом, коли деякий процес описується через самого себе, називається рекурсією. Алгоритм рішення задачі «Ханойська башта» - приклад рекурсивного алгоритму.