Задача про Ханойські вежі

Курсова робота з інформатики

на тему:

«Задача про Ханойські Вежі»

Зміст

Введення

1. Побудова моделі

2. Розробка алгоритму

2.1 Покроковий алгоритм

2.2 Структограмма

3. Перевірка правильності алгоритму

4. Аналіз алгоритму і його складності

5. Реалізація алгоритму

Введення

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

за один раз можна переміщати тільки один диск;

більший диск не можна розташовувати на меншому диску;

знятий диск необхідно надіти на який-небудь шпиль перед тим, як буде відзнято наступний диск.

Працьовиті буддійські ченці день і ніч переносять диски зі шпиля на шпиль. Легенда стверджує, що коли ченці закінчать свою роботу, наступить кінець світу. Можна було б підрахувати, що для вирішення завдання з 64 дисками потрібно 264-1 переміщень (близько 1020). Тому, що стосується кінця світу, то він відбудеться після закінчення п'яти мільярдів століть, якщо вважати, що один диск переміщається за одну секунду. Втім і завдання, і легенду для неї придумав у 1883 році математик Е. Люка. Це дає нам право відкласти турботи про кінець світу в бік і перейти до вирішення наступного завдання.

Постановка завдання.

Є три кілочка a, b, c і n дисків різного розміру, переномерованних від 1 до n в порядку зростання їх розмірів. Спочатку всі диски надіті на кілочок a (рисунок 1.1),

Малюнок 1.1

потрібно перенести всі диски з кілочка a на кілочок c (рисунок 1.2),

Малюнок 1.2

дотримуючись при цьому наступні умови:

диски можна переносити тільки по одному;

більший не можна ставити на менший (рисунок 1.3).

Малюнок 1.3

Написати програму, яка друкує послідовність дій (у вигляді «перенести диск з q на r», де q і r - це a, b або c, вирішальну вказане завдання для n дисків, n - задане натуральне число).

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

1. Побудова моделі

Математичною моделлю даної задачі є рекурентне співвідношення.

Рекурентне співвідношення - це співвідношення, яке виражає значення функції за допомогою інших значень, обчислених для менших аргументів. Виходячи з даного визначення, випливає, що для кожної рекурентної функції потрібно задавати хоча б одне значення.

2. Розробка алгоритму

Для розробки алгоритму розв'язання даної задачі використовується рекурсивний метод.

При побудові алгоритму використовується підхід «розділяй і володарюй». Ідея полягає в наступному:

завдання розбивається на кілька підзадач меншого розміру;

вирішуються ці підзадачі;

рішення підзадач комбінуються, й виходить рішення вихідної задачі.

Як правило, завдання вирішуються безпосередньо, або за допомогою рекурсивного виклику.

Алгоритм називається рекурсивним, якщо при вирішенні деякої задачі він викликає сам себе для вирішення підзадачі.

Для того, щоб перекласти всю піраміду з дисків, треба спочатку перекласти все, що вище найбільшого диска, з першого на допоміжний кілочок, потім перекласти цей найбільший диск з першого на третій кілочок, а потім перекласти залишилася піраміду з другого на третій кілочок, користуючись перший кілочком як допоміжним.

2.1 Покроковий алгоритм (з рекурсією)

Вхідні дані: кількість дисків, що знаходяться на кілочку a;

Вихідні дані: послідовність дій;

Шаг0: {визначення типу змінних};

Шаг1: {опис процедури Pernesti, яка виводить послідовність дій};

Шаг1.1: {перемістити (n-1) дисків з кілочка a на кілочок b};

Шаг1.2: {перемістити n-ий диск з a на c};

Шаг1.3: {перемістити (n-1) диск з b на c};

(Кроки 1.2-1.3 виконуються рекурсивно);

КРОК 2: {основна програма};

Шаг2.1: {введення кількості дисків};

Шаг2.2: {виклик процедури Perenesti}.

2.2 Структограмма