Министерство сельского хозяйства Российской Федерации
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ
Кафедра системного анализа и обработки информации
Пояснительная записка
к курсовой работе
по дисциплине: Алгоритмы и структуры данных
на тему: Методы решения задачи о Ханойских башнях
выполнил студент группы ПИ-1201
Горятов Александр Александрович
Допущен к защите
Руководитель проекта Анищик Т.А.
Нормоконтролер _________________________________________________
(подпись, расшифровка подписи)
Защищен_____________________ Оценка______________________
(дата)
Члены комиссии__________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
(подпись, дата, расшифровка подписи)
Краснодар
2013 Г. Реферат
Пояснительная записка содержит:
15 листов,
7 картинок,
2 приложения.
Целью курсовой работы является рассмотрение различных методов решения задачи о Ханойских башнях и программная реализация в среде Visual Studio 2010.
Результатом работы являются две программы, которые иллюстрируют два метода нахождения решения задачи о Ханойских башнях в среде Visual Studio 2010.
Оглавление
Горятов Александр Александрович 1
ВВЕДЕНИЕ 4
ПОСТАНОВКА ЗАДАЧИ 5
1.1 Цель и задачи работы нахождение решения задачи о восьми ферзях. 5
1.2 Обоснование выбора средства программирования 5
1.3 Входная и выходная информация 5
1.4 Требования к аппаратному и программному обеспечению 6
СВЕДЕНИЯ ИЗ ТЕОРИИ 7
АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ 8
ОПИСАНИЕ ПРОГРАММ 10
4.1 Функциональное назначение 10
4.2 Директивы предпроцессора и константы 10
РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ 10
ЗАКЛЮЧЕНИЕ 14
ЛИТЕРАТУРА 16
ПРИЛОЖЕНИЕ 1 16
ПРИЛОЖЕНИЕ 2 17
17
Введение
В настоящее время стремительными темпами развиваются информационные технологии и связанные с ними сферы человеческой деятельности. С каждым годом всё больший объём информации обрабатывается с помощью современных персональных компьютеров.
Для того чтобы написать программу любого уровня сложности применяют так называемые средства быстрой разработки приложений. Их ключевым преимуществом является отсутствие необходимости проектировать стандартные элементы управления операционной системы Windows. А так же можно визуально наблюдать за каждым процессом написания и отладки программного обеспечения. Все это значительно упрощает процесс создания программы.
Целью курсовой работы является получение практических навыков и опыта разработки программ в среде визуального программирования Visual Studio 2010 express с помощью разработки приложения Решение задачи о ханойских башнях.
Постановка задачи
1.1 Цель и задачи работы нахождение решения задачи о восьми ферзях.
Основной целью данной работы является разработка программы «Нахождение решения задачи о ханойских башнях», а также закрепление практических навыков программирования в среде “Visual Studio 2010”.
Задачи курсовой работы:
-изучить методы решения задачи о ханойских башнях;
-разработать алгоритм решения задачи;
-осуществить программную реализацию в среде “Visual Studio 2010”;
-протестировать разработанное приложение.
1.2 Обоснование выбора средства программирования
Для написания программы выбрана среда программирования “Visual Studio 2010 express”, основанную на языке программирования C++. Данная среда выгодно отличается эффективностью и надежностью. А так же C++ предоставляет разработчику более комфортные условия и более широкие возможности для создания дружественного интерфейса.
1.3 Входная и выходная информация
Входными данными для программы являются:
- количество колец;
- количество колышек;
-переменные;
Выходными данными являются результаты вычислений, иначе говоря расстановка восьми ферзей на шахматной доске.
1.4 Требования к аппаратному и программному обеспечению
Персональный компьютер фирмы IBM серии PC (или совместимый с этими моделями), работающий под управлением операционной системы (ОС) Windows 98/XP/Vista/7/8, операционная память не менее 64 Мбайт, процессор с тактовой частотой не менее 133 MHz, клавиатура, мышь.
СВЕДЕНИЯ ИЗ ТЕОРИИ
Ханойская башня является одной из популярных головоломок XIXв.
Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшие на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Легенда гласит, что в Великом храме города Бенарас, под собором,
отмечающим середину мира, находится бронзовый диск, на котором
укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу.
Давным-давно, в самом начале времён, монахи этого монастыря провинились
перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и
на один из них возложил 64 диска, сделанных из чистого золота. Причем так,
что каждый меньший диск лежит на большем.
Как только все 64 диска будут переложены со стержня, на который Брахма
сложил их при создании мира, на другой стержень, башня вместе с храмом
обратятся в пыль и под громовые раскаты погибнет мир.
Количество перекладываний в зависимости от количества колец вычисляется
по формуле 2n-1.
Число перемещений дисков, которые должны совершить монахи, равно 18
446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали
каждую секунду одно перемещение диска, их работа продолжалась бы 584
миллиарда лет.
В информатике задачи, основанные на легенде о Ханойской башне, часто
рассматривают в качестве примера использования рекурсивных алгоритмов и
преобразования их к не рекурсивным.