Рекурсия в задаче о Ханойской башне

РефератПомощь в написанииУзнать стоимостьмоей работы

Рекурсия в задаче о Ханойской башне (реферат, курсовая, диплом, контрольная)

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

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

Структурно рекурсивная функция на верхнем уровне всегда представляет собой команду ветвления (выбор одной из двух или более альтернатив в зависимости от условия (условий), которое в данном случае уместно назвать «условием прекращения рекурсии»), имеющей две или более альтернативные ветви, из которых хотя бы одна является рекурсивной и хотя бы одна —терминальной. Рекурсивная ветвь выполняется, когда условие прекращения рекурсии ложно, и содержит хотя бы один рекурсивный вызов — прямой или опосредованный вызов функцией самой себя. Терминальная ветвь выполняется, когда условие прекращения рекурсии истинно; она возвращает некоторое значение, не выполняя рекурсивного вызова. Правильно написанная рекурсивная функция должна гарантировать, что через конечное число рекурсивных вызовов будет достигнуто выполнение условия прекращения рекурсии, в результате чего цепочка последовательных рекурсивных вызовов прервётся и выполнится возврат.

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

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

Эту игру придумал французский математик Эдуард Люка, в 1883 году, её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)», но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа — не более чем анаграмма фамилии изобретателя игры, профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).

Предположим, что мы хотим получить в итоге программу, которая по заданному значению N будет нам выводить последовательность действий, решающих задачу, т. е. алгоритм переноса всех колец со стержня, А на стержень B. Действие переноса одного кольца будет иметь вид: A -> B, что означает перенос одного верхнего кольца со стержня с именем А, на стержень с именем B. Рассмотрим, как должны выглядеть решения для малых N: рекурсия вычислительный ханойский башня.

N=1: A -> B.

N=2: A -> C, A -> B, C -> B.

N=3: A -> B, A -> C, B -> C, A -> B, C -> A, C -> B, A -> B.

Минимальное число ходов, необходимое для решения головоломки, равно 2ⁿ — 1, где n — число дисков. Начнём с самого маленького кольца и переложим его на любую отметку. В дальнейшем это кольцо нужно перемещать в том же направлении, что и при первом перекладывании. Затем произведем единственно возможное перемещение оставшихся колец, после чего снова переложим самое маленькое кольцо и т. д. (Интересно заметить, что перенумеровав «кольца» по порядку, мы добьёмся неожиданного эффекта: чётные кольца будут перемещаться из одной вершины треугольника в другую в одном направлении, а нечётные — в противоположном направлении.).

Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит в переносе m дисков с левого стержня на правый.

Задача может быть решена одним перемещением только для одного (m = 1) диска. В общем случае потребуется 2^m-1 перемещений.

Построим рекурсивное решение задачи, состоящее из трех этапов:

a) перенести башню, состоящую из m — 1 диска, с левого стержня на средний;

b) перенести один оставшийся диск с левого стержня на правый;

c) перенести башню, состоящую из m — 1 диска, со среднего стержня на правый.

Таким образом, задача о перемещении m дисков сводится к задаче о перемещении m — 1 диска. Обращаясь опять к этому же алгоритму, сведем задачу к перемещению m — 2 дисков. Продолжая этот процесс, получим, в конце концов, задачу о перемещении одного диска. Эта задача решается за один ход. Таким образом, в процессе решения возникают промежуточные задачи: переместить башню из нескольких n дисков с одного стержня на другой.

Обозначим тот стержень, с которого следует снять диски, через s1, на который надеть — через sk, а вспомогательный стержень через sw.

Оформим алгоритм решения задачи о переносе башни из n дисков с s1 на sk в виде процедуры move с 4-мя параметрами: n, s1, sw, sk; алгоритм для n = 1выделим в отдельную процедуру step, которая перемещает один диск со стержня s1на sk.

Тогда программный код будет выглядеть следующим образом:

type.

st = (left, middle, right);

nat = 1. maxint;

var.

m: nat; {m — число дисков}.

procedure move (n: nat; s1, sw, sk: st); {перемещение n дисков с s1 на sk}.

procedure step; {перемещение одного диска с s1 на sk}.

procedure print (s: st);

begin

case s of.

left: write (' лев. ');

middle: write (' средн. ');

right: write (' прав. ').

end;

begin {step}.

write (' снять диск с ');

print (s1);

write (' надеть на ');

print (sk);

writeln.

end;

begin {move}.

if n = 1 then

step.

else begin

move (n — 1, s1, sk, sw);

step;

move (n-1, sw, s1, sk).

end

end;

begin

read (m); {число дисков}.

writeln ('для ', m:3, ' дисков следует произвести ',.

'следующие действия:');

move (m, left, middle, right);

readln.

end.

При тестировании программы получаются следующие результаты:

для 2 дисков следует произвести следующие действия:

снять диск с лев. надеть на средн.