Тема: организация стека. Рекурсивные алгоритмы

Лабораторная работа № 5

Цель работы: Изучение методов работы со стеком.

План работы: Разработать рекурсивный алгоритм.

Теоретический материал:

Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.

Стек — самая популярная и, пожалуй, самая важная структура данных в программировании. Стек представляет собой запоминающее устройство, из которого элементы извлекаются в порядке, обратном их добавлению. Это как бы неправильная очередь, в которой первым обслуживают того, кто встал в нее последним. В программистской литературе общепринятыми являются аббревиатуры, обозначающие дисциплину работы очереди и стека. Дисциплина работы очереди обозначается FIFO, что означает первым пришел — первым уйдешь (First In First Out). Дисциплина работы стека обозначается LIFO, последним пришел — первым уйдешь (Last In First Out).

Головоломка "Ханойские башни" достаточно старая и хорошо известная, с ней связано несколько забавных легенд, но суть проблемы, которую я попытаюсь рассмотреть на примере данной задачи - использование рекурсивных алгоритмов и преобразование их к не рекурсивным.

Для начала сформулируем саму задачу. Даны три стержня ((н) - начальный, (к)- конечный, (д) - дополнительный) на стержень (н) нанизано некоторое количество дисков (будем полагать его равным n) при этом все диски имеют разный диаметр и расположены на стержне (н) в порядке уменьшения диаметра снизу в верх (см. рис).

Необходимо переместить все диски на стержень (к), т.е. головоломка должна быть приведена к виду:

при этом за один ход можно переместить только один диск, и в результате хода не должно возникнуть ситуации, когда диск с большим диаметром будет положен на диск с меньшим диаметром.

Выбор той или иной стратегии перемещения дисков приводит к новому вопросу, сколько необходимо ходов для того чтобы головоломка была полностью разрешена. Причем очевидно что количество ходов растет с ростом числа дисков, и желательно получить некоторую функцию f(n), которая выдавала бы для данной стратегии количество ходов необходимых для решения задачи в зависимости от числа дисков. В статье рассматривается только одна стратегия, оптимальность которой можно доказать. Вначале стратегия получается в виде рекурсивного алгоритма, а затем преобразуется к не рекурсивной форме.

Дата добавления: 2015-05-06