Основы программирования. Файлы. Рекурсия - 27 стр.

UptoLike

Составители:

Рубрика:

Однако, такое «лобовое» решение крайне неэффективно, поскольку содержит

большое количество повторяющихся вычислений. Изобразим дерево рекурсивных

вызовов для вызова

Fib(7):

Из рисунка видно, что, например, Fib(5) вычисляется дважды, Fib(4) –

трижды,

Fib(3) – 5 раз и т.д., то есть количество повторных вызовов представля-

ет собой, по иронии судьбы, последовательность чисел Фибоначчи!

2.6 Более сложные примеры использования рекурсии

Пример 8. Ханойские башни.

Это – классический пример задачи, у которой имеется простое рекурсивное

решение, а нерекурсивное решение является существенно более громоздким и да-

ет лишь незначительный выигрыш в эффективности.

Задача состоит в следующем. Имеется три штыря, на одном из которых ле-

жит пирамида из n дисков, причем, меньшие диски лежат на

больших (см. рису-

нок).

Требуется, перекладывая по одному диску на соседние штыри, переложить

всю пирамиду с одного штыря на другой за наименьшее количество ходов. При

этом запрещается класть больший диск на меньший.

Сведем задачу с n дисками к задаче с n – 1 дисками (фактически, применим

метод математической индукции по числу дисков). Пусть нам требуется перело-

жить пирамиду из дисков со штыря с номером f (from) на штырь с номером t (to),

используя штырь

w (work) в качестве вспомогательного. Для этого необходимо

вначале переложить пирамиду из n – 1 диска со штыря f на штырь w, используя

штырь

t в качестве вспомогательного, затем переместить оставшийся диск со

штыря f на штырь t и, наконец, переложить пирамиду из n – 1 диска со штыря w

на штырь

t, используя штырь f в качестве вспомогательного.