Задача о Ханойских башнях
Курсовая работа по информатикена тему:«Задача о Ханойских башнях»СодержаниеВведение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 на стержень cn=4
Другие файлы:
Рекурсия и функции
Определение функции, ее прототип. Рекурсия - частичное определение объекта через себя. Рекурсивная функция произведения 2-х целых чисел. Задача о вычи...
Рекурсивные функции
Классификация и стек рекурсивных функций. Методика распознавания формулы, записанной в строке. Реализация салфетки Серпинского и задачи о Ханойских ба...
Небесная механика. Аналитические и качественные методы
Оглавление: I. Вспомогательные теоремы. II. Устойчивость движения. III. Периодические решения. IV. Задача неподвижных центров. V. Ограниченная задача...
Динамическое и линейное программирование
Линейная производственная задача. Двойственная задача. Задача о "Расшивке узких мест производства". Транспортная задача. Распределение капитальных вло...
