Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Задача о Ханойских башнях

Название: Задача о Ханойских башнях
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 19:19:47 05 февраля 2010 Похожие работы
Просмотров: 421 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Курсовая работа по информатике

на тему:

«Задача о Ханойских башнях»


Содержание

Введение

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(начало процедуры)

ifn>0 then(если n>0 значит)

begin

Perenesti(n-1,a,c,b);

writeln ('Peremestit" disk so sterzhnya ',a,' na sterzhen" ',b);(ввели)

Perenesti(n-1,c,b,a);

end;

end;

begin

clrscr;(очистка экрана)

writeln ('Vvedite natural"noe chislo n');

read (n);(ввод числовых данных)

a:='a'; b:='b'; c:='c';присвоение по членных переменных (то ,что до этого ввели)

Perenesti (n,a,c,b);

readln;(процедура чтения)

end.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений06:47:16 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:53:04 28 ноября 2015

Работы, похожие на Курсовая работа: Задача о Ханойских башнях

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150559)
Комментарии (1836)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru