Автор работы: Пользователь скрыл имя, 23 Октября 2013 в 19:34, курсовая работа
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН
КАЗАХСКИЙ УНИВЕРСИТЕТ ЭКОНОМИКИ, ФИНАНСОВ И МЕЖДУНАРОДНОЙ ТОРГОВЛИ
КАФЕДРА «ИНФОРМАТИКИ И ПРИКЛАДНОЙ ЭКОНОМИКИ»
КУРСОВАЯ РАБОТА
на тему:
«ИСПОЛЬЗОВАНИЕ ПЕРЕБОРНЫХ МЕТОДОВ (разработка программы для решения задачи «Ханойская башня»)»
по дисциплине «Объектно-ориентиованное программирование в среде Delphi»
АСТАНА
2013
СОДЕРЖАНИЕ
ВВЕДЕНИЕ…………………………………………………………
ВВЕДЕНИЕ
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
История создания головоломки
Эту игру придумал французский математик Эдуард Люка, в 1883 году, её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)», но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа — не более чем анаграмма фамилии изобретателя игры, профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).
Решение
Минимальное число ходов, необходимое для решения головоломки, равно 2n - 1, где n — число дисков.
Начнём с самого маленького кольца и переложим его на любую отметку. В дальнейшем это кольцо нужно перемещать в том же направлении, что и при первом перекладывании. Затем произведем единственно возможное перемещение оставшихся колец, после чего снова переложим самое маленькое кольцо и т. д. (Интересно заметить, что перенумеровав «кольца» по порядку, мы добьёмся неожиданного эффекта: чётные кольца будут перемещаться из одной вершины треугольника в другую в одном направлении, а нечётные — в противоположном направлении.)
1. ФОРМУЛИРОВКА ЗАДАЧИ
Разработать рекурсивную схему, написать и отладить программу решения задачи, которая формулируется следующим образом.
Даны три стержня и N дисков разного диаметра, которые надеты на стержень (1) в порядке убывания диаметра (Рис. 1).
Надо переместить N дисков за наименьшее число шагов на диск (3), так чтобы они остались в таком же порядке. При этом требуется соблюдать правила:
На каждом шаге ровно один диск перемещается с одного диска на другой;
Диск б0льшего диаметра нельзя помещать на диск меньшего диаметра;
Стержень (2) можно использовать как промежуточный.
Программа должна работать для нефиксированного числа дисков N.
2. РЕШЕНИЕ
2.1. Основные алгоритмы решения задачи.
Применение кода Грея для решения
Код Грея, рефлексный двоичный код в двоичной системе счисления, в котором два соседних значения различаются только в одном двоичном разряде.
Изначально код Грея предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления. Код получил имя исследователя лабораторий Bell Labs Фрэнка Грея. Он использовал этот код в своей импульсной системе связи, для чего был написан патент за номером 2632058.
Коды Грея применяются в решении задачи о Ханойских башнях. Пусть N — количество дисков. Начнём с кода Грея длины N, состоящего из одних нулей (то есть G(0)), и будем двигаться по кодам Грея (от G(i) переходить к G(i+1)). Поставим в соответствие каждому I-ому биту текущего кода Грея I-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита I как перемещение I-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t->…
Алгоритм Фрейма-Стюарта
Алгоритм Фрейма — Стюарта, дающий предположительно оптимальное решение для четырёх (или более) стержней, описывается следующим образом:
Пусть — количество дисков.
Пусть — число стержней.
Определим как наименьшее число ходов, необходимое для переноса n дисков с использованием r стержней.
Алгоритм может быть описан рекурсивно:
Для некоторого , , перенести верхние на стержень i, не являющийся ни начальным, ни конечным стержнем, затратив на это ходов.
Не используя стержень i, содержащий теперь верхние дисков, перенести оставшиеся дисков на конечный стержень, используя только оставшиеся стержней и затратив на это ходов.
Наконец, переместить верхние дисков на конечный стержень, затратив на это ходов.
На весь процесс требуется ходов. Значение выбирается таким образом, чтобы значение этого выражения было минимальным.
2.2. Общие принципы реализации.
Классический пример применения рекурсии для описания эффективного алгоритма - задача о ханойских башнях. На первый из трех стержней, закрепленных вертикально на подставке, насажено несколько дисков различных диаметров так, что диск меньшего диаметра лежит на диске большего диаметра. Два других стержня пусты (рис 1).
В задаче требуется переставить все диски с одного стержня на другой за несколько шагов. Каждый шаг - это перестановка верхнего диска одного стержня на верхний диск другого стержня с соблюдением правила: диаметр переставляемого диска должен быть меньше, чем диаметр диска, на который осуществляется перестановка.
1 2 3
Рис. 1
Пусть N – количество дисков на стержне, I – номер стержня, с которого осуществляется перестановка и J – номер стержня, на который диски требуется переставить. Переменные N, I, J – параметры процедуры HanoiTower, управляющей перестановками. Шаг решения – процедура Step с параметрами I, J.
HanoiTower( N, I, J) – процедура, переставляющая N дисков с I-того стержня на J-тый.
Step(I, J) – процедура, переставляющая один диск с I-того стержня на J-тый.
Заметим, что если I и J – номера двух стержней, то 6-I-J – номер третьего стержня.
Учтя, что при N = 1 задача решается с помощью процедуры Step(I, J), опишем процедуру HanoiTower(N, I, J) используя Step(I, J).
Так же будем использовать массив дисков – Rings[1..N, 1..3].
var
Form1: TForm1;
Rings: array of array of Integer; //Массив дисков
N, stp, spd: integer;
// N – число дисков
// stp – количество шагов
// spd – скорость перестановки
procedure Step(I: integer; J: integer);
var
number_i, number_j, k: integer;
begin
stp:=stp+1;
for number_i:=1 to N do if Rings[number_i, I]=0 then
for number_j:=1 to N do if Rings[number_j, J]=0 then
begin
Rings[number_j, J]:=Rings[number_i-1, I];
Rings[number_i-1, I]:=0;
exit;
end;
if Rings[N, I]<>0 then
for number_j:=1 to N do if Rings[number_j, J]=0 then
begin
Rings[number_j, J]:=Rings[N, I];
Rings[N, I]:=0;
end;
end;
procedure HanoiTower(N: integer; I: integer; J: integer);
begin
if N=1 then Step(I, J)
else begin
HanoiTower(N-1, I, 6-I-J);
Step(I, J);
HanoiTower(N-1, 6-I-J, J);
end;
end;
Графическая оболочка представляет собой окно (Рис. 2):
Рис. 2
Программа позволяет выбирать n-ое количество дисков и наблюдать за процессом перестановки, скорость которой задается в поле «Скорость перестановки».
В результате программа решает задачу расстановки дисков, показывает количество шагов проделанных в ходе алгоритма и выводит на экран результат перестановки дисков.
Диски изображаются
в окне приложения с помощью таблицы,
б0льший номер диска
Рис. 3
Легендарные Ханойские башни хранятся в тихом храме глубоко в джунглях. Они состоят из 64 полированных медных дисков, и несколько смен молчаливых монахов в чёрных одеяниях непрерывно перемещают диски по одному с одной пирамиды на другую.
Когда они завершат свою работу, наступит конец света. Так гласит предание! Если они смогут выполнить один ход за секунду, всё мероприятие займёт около половины триллиона лет, поэтому планы на ближайшие выходные менять не стоит.
В нашем примере можно определять скорость перестановки.
Задача о
Ханойской башне рассматривалас
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ