Курсовая работа поинформатике
на тему:
«Задача оХанойских башнях»
Содержание
Введение
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 на стержень c
n=4
переместить диск со стержня a на стержень b
переместить диск со стержня a на стержень c
переместить диск со стержня b на стержень c
переместить диск со стержня a на стержень b
переместить диск со стержня c на стержень a
переместить диск со стержня c на стержень b
переместить диск со стержня a на стержень b
переместить диск со стержня a на стержень c
переместить диск со стержня b на стержень c
переместить диск со стержня b на стержень a
переместить диск со стержня c на стержень a
переместить диск со стержня b на стержень c
переместить диск со стержня a на стержень b
переместить диск со стержня a на стержень c
переместить диск со стержня b на стержень c
4. Анализ алгоритма и его сложности
Алгоритм решения задачи о Ханойских башнях являетсяконечным, так как все используемые циклы выполняются конечное число раз.
Сложность – количественная характеристика алгоритма,которая говорит о том, сколько времени он работает (временная сложность), либоо том, какой объем памяти он занимает (емкостная сложность). На практике сложностьрассматривают как временную сложность.
Из определения сложности следует, что она зависит отразмерности входных данных или, как говорят, от длины входа. В задаче оХанойских башнях входными данными является число дисков.
Рассчитаем порядок временной сложности в соответствии спошаговым алгоритмом.
Временная сложность процедуры Perenesti будет зависеть отколичества переносов, которое равно 2n-1, значит О(2n-1).
5. Реализация алгоритма
Program kyrsovaya;
uses crt;(подключение модуля очистки экрана)
var(описание переменных)
n: integer;(целый тип данных)
a,b,c: char;(описание символьных типов данных)
procedure Perenesti(n: integer;a,b,c:char);
begin(начало процедуры)
if n>0 then(если n>0значит)
begin
Perenesti(n-1,a,c,b);
writeln ('Peremestit" disk sosterzhnya ',a,' na sterzhen" ',b);(ввели)
Perenesti(n-1,c,b,a);
end;
end;
begin
clrscr;(очистка экрана)
writeln ('Vvedite natural«noechislo n');
read (n);(ввод числовых данных)
a:='a'; b:='b'; c:='c'; присвоение по членных переменных(то, что до этого ввели)
Perenesti (n,a,c,b);
readln;(процедура чтения)
end.