Задача о ханойских башнях

1.

Министерство науки и образования РФ
Федеральное государственное бюджетное учреждение
высшего образования
«Тверской государственный технический университет»
(ТвГТУ)
Кафедра программного обеспечения
Курсовая работа
по дисциплине: «Теория алгоритмов»
ЗАДАЧА О ХАНОЙСКИХ
БАШНЯХ
Выполнил:
студент группы
Б.ПИН.РИС-20.06
Филатов Ю.А.

2.

ЦЕЛЬ РАБОТЫ
Изучение алгоритмов решения задачи о Ханойских башнях
2

3.

ЗАДАЧИ
изучить методы решения задачи о ханойских башнях;
разработать алгоритм решения задачи;
осуществить программную реализацию на языке python;
протестировать разработанное приложение.
3

4.

ХАНОЙСКИЕ БАШНИ
Ханойские башни — это игра, в которой используются три штыря и
набор дисков. Все диски различаются диаметром и нанизываются на
штыри через отверстие в центре каждого диска. Первоначально все
диски находятся на левом штыре.
Цель игры состоит в том, чтобы переместить все диски на
центральный штырь. Правый штырь можно использовать как
«запасной» для временного размещения дисков. При каждом
перемещении диска с одного штыря на другой должны соблюдаться два
ограничения: перемещать можно только самый верхний диск на штыре,
и, кроме того, нельзя ставить диск на другой диск меньшего размера.
4

5.

ХАНОЙСКИЕ БАШНИ
Рис. 1 Ханойские башни
5

6.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
Математической моделью данной задачи является рекуррентное
соотношение. Рекуррентное соотношение — это соотношение, которое
выражает значение функции с помощью других значений, вычисленных
для меньших аргументов. Исходя из данного определения, следует, что
для каждой рекуррентной функции нужно задавать хотя бы одно
значение.
T(n) = 2 * T(n - 1) + 1
6

7.

РЕКУРСИВНОЕ РЕШЕНИЕ
Рис. 2 рекурсивный алгоритм
7

8.

ИТЕРАТИВНОЕ РЕШЕНИЕ
Рис. 3 Итеративный алгоритм
Рис. 4 Подпрограмма move_disk
8

9.

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
Для осуществления поставленных задач было создано два класса:
Класс, описывающий диски, Disk, включающий в себя числовое поле
size, размер диска, и методы сравнения объектов данного класса между
собой.
И класс Tower, описывающий стержни, на которых будут лежать диски, с
методами для добавления и удаления дисков и методом для заполнения
колышка дисками.
9

10.

ДИАГРАММА КЛАССОВ
Рис. 5 Диаграмма классов
10

11.

ПОЛЬЗОВАТЕЛЬСКИЙ ИНТЕРФЕЙС
Для программы был реализован пользовательский интерфейс с
помощью библиотеки pygame. Интерфейс позволяет пользователю
выбрать количество дисков и алгоритм решения задачи, если
пользователь пожелает, он может выбрать опцию решать головоломку
самостоятельно.
11

12.

ПОЛЬЗОВАТЕЛЬСКИЙ ИНТЕРФЕЙС
Рис. 6 Выбор сложности
Рис. 7 Самостоятельное решение 12

13.

ТЕСТИРОВАНИЕ
Рис. 8 Решение задачи алгоритмом
13

14.

ТЕСТИРОВАНИЕ
Рис. 9 Тестирование времени выполнения
Рис. 10 Сравнение алгоритмов
14

15.

ЗАКЛЮЧЕНИЕ
В результате выполнения курсовой работы была создана программа, позволяющая
решить задачу о ханойских башнях с помощью двух алгоритмов: рекурсивного и
итеративного. Так же пользователю дана возможность решить задачу самостоятельно.
Программа выполнена в двух вариантах: консольном и вариантом с интерфейсом,
созданным с помощью pygame. Первый вариант позволяет вводить число дисков,
ограниченное ресурсами компьютера, и тестировать время выполнения алгоритмов, а
второй позволяет наблюдать поэтапную работу алгоритмов на красивом интерфейсе.
В результате тестирования программы выяснилось, что рекурсивный алгоритм
работает быстрее, чем итеративный.
15