КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Техника рекурсивных описаний
End End;
Тело функции F содержит два рекурсивных вызова, выполняемых последовательно. Поэтому полная картинка рекурсии имеет вид дерева! Построим ее при n = 5. Каждая рекурсивная копия, если ее параметр k >= 2, вызывает две новых копии. Полная картинки вызовов имеет вид дерева, из каждого ветвления которого выходят две ветви. (с параметрами k-1, k-2). В каждый момент времени в памяти компьютера хранится только один путь - тот, который соответствует состоянию процесса вычислений. В памяти компьютера, отведенной под рекурсивные вычисления, хранятся те копии, путь через которые лежит к исполняемой. Время исполнения этого алгоритма пропорционально общему числу рекурсивных копий, Максимальная память, требуемая для хранения данных, пропорциональна длине максимального пути - от первой копии до копии нижнего уровня. Древовидная картинка наглядно показывает схему рекурсивных вычислений. На ней видно, что необходимыми являются только вычисления, стоящие в самом левом пути. Все остальные вычисления - только повторения уже проделанных. Несколько примеров рекурсивных процедур, рассмотренных в этом пункте, помогут лучшему усвоению техники применения рекурсии. Мы также увидим преимущества и недостатки рекурсивных описаний. Пример 7. Ханойские башни. Классический пример применения рекурсии для описания эффективного алгоритма - задача о ханойских башнях. Анализ и неформальное описание алгоритма. Пусть N - количество колец на стержне, I - номер кольца, с которого осуществляется перестановка и J - номер кольца, на которое кольца требуется переставить. HanojTower(N, I, J) - процедура, переставляющая N колец с I-того стержня на J-тый.
Step(I, J) - процедура, переставляющая одно кольцо с I-того стержня на J-тый. (Если I и J - номера 2-стержней, то 6-I- J - номер третьего стержня.)
Предположим, что мы переместили N-1 кольцо с I-того стержня на 6-I-J стержень. Тогда можно переместить кольцо со стержня I на J. На стержне J лежит кольцо с наибольшим диаметром, т.е. этот стержень можно использовать без нарушения ограничений, связанных с величинами диаметров. Поэтому можно теперь переставить всю пирамиду из N-1 кольца со стержня 6-I-J на J, и задача решена!
При N = 1 задача решается за один шаг - процедурой Step(I, J). Тем самым установлен базис рекурсии. Опишем теперь процедуру HanojTower(N, I, J): Procedure HanojTower(N, I, J: Integer);
Дата добавления: 2014-01-06; Просмотров: 292; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |