История и суть задачи "Ханойские башни", построение ее математической модели в виде рекуррентного соотношения. Решение задачи с помощью рекурсии и кода Грея, ее связь с теорией графов. Анализ временных затрат. Различные головоломки с измененным условием.
Ханойские башни - это игра, в которой используются три штыря и набор дисков. Все диски различаются диаметром и нанизываются на штыри через отверстие в центре каждого диска. Первоначально все диски находятся на левом штыре. Цель игры состоит в том, чтобы переместить все диски на центральный штырь. При каждом перемещении диска с одного штыря на другой должны соблюдаться два ограничения: перемещать можно только самый верхний диск на штыре, и, кроме того, нельзя ставить диск на другой диск меньшего размера.Даны три стержня из N дисков разного диаметра, которые надеты на стержень (1) в порядке убывания диаметра (Рис. Надо переместить N дисков за наименьшее число шагов на стержень (3), так чтобы они остались в таком же порядке.Рекуррентное соотношение - это соотношение, которое выражает значение функции с помощью других значений, вычисленных для меньших аргументов.Многим из тех людей, которые играют в эту игру, практически никогда не удается обнаружить весьма простую стратегию, позволяющую успешно играть в Ханойские башни с тремя штырями и N дисками. Чтобы не утомлять вас поисками решения этой задачи, мы откроем его: • Граничное условие выполняется в случае, когда на исходном (левом) штыре нет дисков. • Переместить N-1 дисков с исходного штыря на запасной (правый) штырь, используя итоговый штырь как запасной; отметим, что это перемещение осуществляется рекурсивно. • Наконец, переместить N-1 дисков с запасного на итоговый, используя исходный штырь в качестве запасного. В программировании рекурсия - вызов функции (процедуры) из нее же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция - функцию .Проведем анализ временных затрат для ханойских башен (и всех задач, сводящихся к решению двух подзадач размерности n-1). Сложность - количественная характеристика алгоритма, которая говорит о том, сколько времени он работает (временная сложность), либо о том, какой объем памяти он занимает (емкостная сложность). Еще одно замечательное следствие состоит в том, что в процессе перекладывания колец встретятся все допустимые расположения колец на трех стержнях, так сказать, «все позиции». Потому, что общее число позиций равно 2n (чтобы задать позицию, мы для каждого из n колец должны выбрать тот из трех стержней, на котором оно в этой позиции находится - а порядок колец на стержне жестко задан их размерами), и по той простой причине, что никакая позиция не встречается в процессе перекладывания дважды (иначе процесс можно было бы сократить). В задаче было показано, что путь от исходного (все кольца собраны на левом стержне) до конечного (все кольца собраны на правом из трех стержней) состояния проходит абсолютно через все допустимые позиции.Начнем с кода Грея длины N, состоящего из одних нулей (то есть G(0)), и будем двигаться по кодам Грея (от G(i) переходить к G(i 1)). Поставим в соответствие каждому I-ому биту текущего кода Грея I-ый диск (причем самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту - наибольший).Ханойские башни - старая задача и она уже давно решена, поэтому сейчас существует уже много задач, условие которых было изменено или доработано для усложнения. 2) На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 на 3, а со стержня 3 на 1.Во время выполнения курсовой работы мною были изучены следующие вопросы: 1) Алгоритм рекурсии; Мной была составлена программа для наглядного представления работы рекурсии на примере задачи о Ханойских башнях на С# в VISUALSTUDIO 2010.Код программы на языке C# using System; using System.Collections.Generic; using System.Text; char from = "A", to = "B", help = "C"; Console.Write(" Введите количество дисков: ");Пояснения к программе: 1)Вводим количество дисков.(Program) using System; using System.Collections.Generic; (Strategy) using System; Trace.Assert(towers.TOWERSCOUNT == 3); Debug.Assert(towers.ISCONTAINRADIUS(FIRSTTOWER, n));Пояснения к программе 2: 1)Вводим количество дисков.(Program) using System; using System.Collections.Generic; (Strategy) using System; Trace.Assert(towers.TOWERSCOUNT == 3); Trace.Assert(towers.ISCONTAINRADIUS(FIRSTTOWER, n));Пояснения к программе 3: 1)Вводим количество дисков.
План
Содержание
Введение
1. История задачи «Ханойские башни»
2. Суть задачи
3. Построение модели
4. Решение с помощью рекурсии
5. Сложность и затраты времени
6. Связь задачи «Ханойские башни» с теорией графов
7. Применение кода Грея для решения
8. Различные задачи с измененным условием
Заключение
Список используемой литературы
Приложения
Введение
Ханойские башни - это игра, в которой используются три штыря и набор дисков. Все диски различаются диаметром и нанизываются на штыри через отверстие в центре каждого диска. Первоначально все диски находятся на левом штыре.
Цель игры состоит в том, чтобы переместить все диски на центральный штырь. Правый штырь можно использовать как «запасной» для временного размещения дисков. При каждом перемещении диска с одного штыря на другой должны соблюдаться два ограничения: перемещать можно только самый верхний диск на штыре, и, кроме того, нельзя ставить диск на другой диск меньшего размера.
В данной курсовой работе будет рассмотрен способ решения поставленной задачи «Ханойские башни», связь этой задачи с теорией графов. Так же будут рассмотрены рекурсия, на примере данной задачи и код Грея.
1. История задачи «Ханойские башни»
Эту известную игру придумал французский математик Эдуард Люка, в 1883 году ее продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус из Колледжа Ли-Су-Стьян» но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа - не более чем анаграмма фамилии изобретателя игры - профессора Люка из колледжа Сен-Луи.
Но история этой задачи уходит довольно глубже. Легенда гласит, что в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времен, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и на один из них возложил 64 диска. Брахма поместил на один из стержней 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем.
Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
Количество перекладываний в зависимости от количества колец вычисляется по формуле .
Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.
В информатике задачи, основанные на легенде о Ханойской башне, часто рассматривают в качестве примера использования рекурсивных алгоритмов и преобразования их к не рекурсивным.
Вывод
Во время выполнения курсовой работы мною были изучены следующие вопросы: 1) Алгоритм рекурсии;
2) Код Грея;
3) Связь задачи «Ханойские Башни» с теорией графов;
4) Некоторые методы работы с языком программирования С# ;
Мной была составлена программа для наглядного представления работы рекурсии на примере задачи о Ханойских башнях на С# в VISUALSTUDIO 2010. После проведенных тестов, был сделан вывод, что программа работает корректно, следовательно, поставленная задача выполнена.
Список литературы
1. С. М. Окулов, А. В. Лялин «Ханойские Башни» 2008г. 248 стр.
6. В данной пояснительной записке использованы ссылки на следующие стандарты: 7. ГОСТ Р 1.5-2004. Стандарты национальные РФ. Правила построения, изложения, оформления и обозначения.
8. ГОСТ 2.301-68 ЕСКД. Форматы.
9. ГОСТ Р 7.0.5-2008 СИБИД. Библиографическая ссылка. Общие требования и правила составления.
10. ГОСТ 7.12-93 СИБИД. Библиографическая запись. Сокращения слов на русском языке. Общие требования и правила.
11. ГОСТ 7.9-95 СИБИД. Реферат и аннотация. Общие требования.
12. ГОСТ 7.82-2001 СИБИД. Библиографическая запись. Библиографическое описание электронных ресурсов. Общие требования и правила составления.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
