Курсова робота з інформатики
на тему:
В«Задача про Ханойські вежі В»
Зміст
Введення
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 Структограмма
3. Перевірка правильності алгоритму
Правильність алгоритму перевіримо при n = 3 і n = 4.
n = 3
перемістити диск із стержня a на стрижень c
перемістити диск із стержня a на стрижень b
перемістити диск із стержня c на стрижень b
перемістити диск із стержня a на стрижень c
перемістити диск із стержня b на стрижень a
перемістити диск із стержня b на стрижень c
перемістити диск із стержня a на стрижень c
n = 4
перемістити диск із стержня a на стрижень b
перемістити диск із стержня a на стрижень c
перемістити диск із стержня b на стрижень c
перемістити диск із стержня a на стрижень b
перемістити диск із стержня c на стрижень a
перемістити диск із стержня c на стрижень b
перемістити диск із стержня a на стрижень b
перемістити диск із стержня a на стрижень c
перемістити диск із стержня b на стрижень c
перемістити диск із стержня b на стрижень a
перемістити диск із стержня c на стрижень a
перемістити диск із стержня b на стрижень c
перемістити диск із стержня a на стрижень b
перемістити диск із стержня a на стрижень c
перемістити диск із стержня b на стрижень c
4. Аналіз алгоритму і його складності
Алгоритм рішення задачі про Ханойські вежі є кінцевим, так як всі використовувані цикли виконуються кінцеве число раз.
Складність - кількісна характеристика алгоритму, яка говорить про те, скільки часу він працює (тимчасова складність), або про те, який обсяг пам'яті він займає (ємнісна складність). На практиці складність розглядають як тимчасову складність.
З визначення складності випливає, що вона залежить від розмірності вхідних даних або, як кажуть, від довжини входу. У задачі про Ханойські вежі вхідними даними є число дисків.
Розрахуємо порядок тимчасової складності у відповідності з покроковим алгоритмом.
Часова складність процедури Perenesti буде залежати від кількості переносів, яке дорівнює 2n-1, значить О (2n-1).
5. Реалізація алгоритму
Program kyrsovaya;
uses crt; (підключення модуля очищення екрана)
var (опис змінних)
n: integer; (цілий тип даних)
a, b, c: char; (опис символьних типів даних)
procedure Perenesti (n: integer; a, b, c: char);
begin (початок процедури)
if n> 0 then (якщо n> 0 значить)
begin
Perenesti (n-1, a, c, b);
writeln ('Peremestit "disk so sterzhnya ', a,' na sterzhen "', b); (ввели)
Perenesti (n-1, c, b, a);
end;
end;
begin
clrscr; (очищення екрана)
writeln ('Vvedite natural "noe chislo n ');
read (n); (введення числових даних)
a: = 'a'; b: = 'b'; c: = 'c'; привласнення по членних змінних (Те, що до цього ввели)
Perenesti (n, a, c, b);
readln; (процедура читання)
end.
