Содержание
Введение
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 – заданное натуральное число).
Вам будет интересно - Реферат: Записи в языке Turbo Pascal
Целью данной курсовой работы является изучение рекурсивного алгоритма решения задачи о Ханойских башнях, разработка программы, печатающей последовательность действий.
1. Построение модели
Математической моделью данной задачи является рекуррентное соотношение.
Рекуррентное соотношение – это соотношение, которое выражает значение функции с помощью других значений, вычисленных для меньших аргументов. Исходя из данного определения, следует, что для каждой рекуррентной функции нужно задавать хотя бы одно значение.
2. Разработка алгоритма
Похожий материал - Реферат: Засоби векторної трасировки растрових зображень в Corel Drow
Для разработки алгоритма решения данной задачи используется рекурсивный метод.
При построении алгоритма используется подход «разделяй и властвуй». Идея заключается в следующем:
задача разбивается на несколько подзадач меньшего размера;
решаются эти подзадачи;