Размещено на http://www.allbest.ru/

Министерство сельского хозяйства Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ

Кафедра системного анализа и обработки информации

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

по дисциплине: Алгоритмы и структуры данных

на тему: Методы решения задачи о Ханойских башнях

выполнил студент группы ПИ-1201

Горятов Александр Александрович

Руководитель проекта Анищик Т.А.

Краснодар

2013 г.



Реферат

Пояснительная записка содержит:

15 листов,

7 картинок,

2 приложения.

Целью курсовой работы является рассмотрение различных методов решения задачи о Ханойских башнях и программная реализация в среде Visual Studio 2010.

Результатом работы являются две программы, которые иллюстрируют два метода нахождения решения задачи о Ханойских башнях в среде Visual Studio 2010.

ханойский башня программирование директив



Оглавление

• Введение
• 1. Постановка задачи
• 1.1 Цель и задачи работы нахождение решения задачи о ханойских башнях
• 1.2 Обоснование выбора средства программирования
• 1.3 Входная и выходная информация
• 1.4 Требования к аппаратному и программному обеспечению
• 2. Сведения из теории
• 3. Алгоритм решения задачи
• 4. Описание программ
• 4.1 Функциональное назначение
• 4.2 Директивы предпроцессора и константы
• 5. Руководство пользователя
• Заключение
• Литература
• Приложение 1
• Приложение 2


Введение

В настоящее время стремительными темпами развиваются информационные технологии и связанные с ними сферы человеческой деятельности. С каждым годом всё больший объём информации обрабатывается с помощью современных персональных компьютеров.

Для того чтобы написать программу любого уровня сложности применяют так называемые средства быстрой разработки приложений. Их ключевым преимуществом является отсутствие необходимости проектировать стандартные элементы управления операционной системы Windows. А так же можно визуально наблюдать за каждым процессом написания и отладки программного обеспечения. Все это значительно упрощает процесс создания программы.

Целью курсовой работы является получение практических навыков и опыта разработки программ в среде визуального программирования Visual Studio 2010 express с помощью разработки приложения Решение задачи о ханойских башнях.



1. Постановка задачи

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, клавиатура, мышь.



2. Сведения из теории

Ханойская башня является одной из популярных головоломок XIXв.

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

Легенда гласит, что в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу.

Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.

Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

Количество перекладываний в зависимости от количества колец вычисляется по формуле 2ⁿ-1.

Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали

каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.

В информатике задачи, основанные на легенде о Ханойской башне, часто рассматривают в качестве примера использования рекурсивных алгоритмов и преобразования их к не рекурсивным.



3. Алгоритм решения задачи

Минимальное число ходов, необходимое для решения головоломки, равно 2ⁿ - 1, где т -- число дисков.

Начнём с самого маленького кольца и переложим его на любую отметку. В дальнейшем это кольцо нужно перемещать в том же направлении, что и при первом перекладывании. Затем произведем единственно возможное перемещение оставшихся колец, после чего снова переложим самое маленькое кольцо и т. д.

Рекурсивный алгоритм решения задачи

В программировании рекурсия -- вызов функции из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция -- функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Рекурсивная программа позволяет описать повторяющееся или даже потенциально бесконечное вычисление, причём без явных повторений частей программы и использования циклов.

Структурно рекурсивная функция на верхнем уровне всегда представляет собой команду ветвления (выбор одной из двух или более альтернатив в зависимости от условия (условий), которое в данном случае уместно назвать «условием прекращения рекурсии»), имеющей две или более альтернативные ветви, из которых хотя бы одна являетсярекурсивной и хотя бы одна -- терминальной. Рекурсивная ветвь выполняется, когда условие прекращения рекурсии ложно, и содержит хотя бы один рекурсивный вызов -- прямой или опосредованный вызов функцией самой себя. Терминальная ветвь выполняется, когда условие прекращения рекурсии истинно; она возвращает некоторое значение, не выполняя рекурсивного вызова. Правильно написанная рекурсивная функция должна гарантировать, что через конечное число рекурсивных вызовов будет достигнуто выполнение условия прекращения рекурсии, в результате чего цепочка последовательных рекурсивных вызовов прервётся и выполнится возврат.

Помимо функций, выполняющих один рекурсивный вызов в каждой рекурсивной ветви, бывают случаи «параллельной рекурсии», когда на одной рекурсивной ветви делается два или более рекурсивных вызова.

Параллельная рекурсия типична при обработке сложных структур данных, таких как деревья. Простейший пример параллельно-рекурсивной функции -- вычисление ряда Фибоначчи, где для получения значения n-го члена необходимо вычислить (n-1)-й и (n-2)-й.



4. Описание программ

4.1 Функциональное назначение

Данные программы предназначены для нахождения решения задачи о ханойских башнях.

4.2 Директивы предпроцессора и константы

Директива #include указывает препроцессору, что нужно обработать содержимое указанного файла, если эти содержимое отображалось в программе- источник в точке отображения директивы.* (http://msdn.microsoft.com/ru-ru/library/36k2cdd4.aspx)

#include <iostream> - это заголовочный файл включающий классы, функции и переменные для организации ввода и вывода в С++.

CH - число колец;

N - начальное положение колец;

K- конечное положения колец;

PR - промежуточный колышек;



5. Руководство пользователя

Запускаемым файлом программы является файл башня.exe.

После запуска первой программы нахождения решения задачи о ханойских башнях на экране появляется главное окно программы, представленное на рисунке 1.

Рисунок 1 - Главное окно программы «1 Нахождение решения задачи о восьми ферзях»

Далее вводим исходный колышек

Рисунок 2 - ввод главного колышка

После вводим конечный колышек



Рисунок 3 - ввод конечного колышка.

После вводим «промежуточное хранилище»

Рисунок 4 - ввод «промежуточного хранилища»

И в конце вводим количество дисков



Рисунок 5 - ввод количества дисков

В результате получаем решение

Рисунок 7 - решение задачи о ханойских башнях



Заключение

В ходе выполнения курсовой работы были получены и закреплены навыки программирования в среде Visual Studio 2010. В результате созданы два рабочих приложения «1 Нахождение решения задачи о Ханойских башнях». Проведенное тестирование работы программы не выявило существенных ошибок. Но это не исключает возможности их появления при проведении более глубокого и длительного тестирования.



Литература

http://ru.wikipedia.org/wiki/Ханойская_башня

http://ru.wikipedia.org/wiki/Рекурсия



Приложение 1

Листинг основного модуля программы «1 нахождение решения задачи о восьми ферзях» .

#include <iostream>

using namespace std;

void hanoi_bashnya(int CH, int N, int K, int PR) //CH-число колец, N-начальное положение колец, K-конечное положение колец PR - промежуточный колышек

{

if (CH != 0)

{

hanoi_bashnya(CH-1, N, PR, K);

cout << N << " --> " << K << endl;

hanoi_bashnya(CH-1, PR, K, N);

}

}

int main()

{

setlocale(LC_ALL,"rus"); //подключение русского языка

int start_peg, destination_peg, PR_peg, plate_CH;

cout << "Исходный колышек:" << endl;

cin >> start_peg;

cout << "Конечный колышек:" << endl;

cin >> destination_peg;

cout << "Промежуточное хранилище:" << endl;

cin >> PR_peg;

cout << "Количество дисков:" << endl;

cin >> plate_CH;

hanoi_bashnya(plate_CH, start_peg, destination_peg, PR_peg);

system("pause");

}



Приложение 2

Блок схема рекурсивного решения алгоритма

Размещено на Allbest.ru

...