1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 14
Текст из файла (страница 14)
В настоящем разделе мы приведем пример рекурсивного алгоритма и кратко опишем, как можно реализовать рекурсию на РАМ. 70 а.а. РекуРсия Рассмотрим определение прохождения двоичного дерева во внутреннем порядке, данное в равд. 2,4. При создании алгоритма, который присваивает узлам номера в соответствии с внутренним порядком, хорошо было бы отразить в нем определение прохождения во внутреннем порядке. Один из таких алгоритмов приведен ниже. Заметим, что он рекурсивно обращается к себе для нумерации поддерева. Алгоритм 2.1.
Нумерация узлов двоичного дерева в соответствии с внутренним порядком Вход. Двоичное дерево, представленное массивами ЛЕВЫЙСЫН и ПРАВЫЙСЫН. Выход. Массив, называемый НОМЕР, такой, что НОМЕР[(!в номер узла ( во внутреннем порядке. Метод. Кроме массивов ЛЕВЫЙСЫН, ПРАВЪ|ЙСЫН и НОМЕР, алгоритм использует глобальную переменную СЧЕТ, значение которой — номер очередного узла в соответствии с внутренним порядком. Начальным значением переменной СЧЕТ является 1. Параметр УЗЕЛ вначале равен корню. Процедура, изображенная на рис. 2.9, применяется рекурсивно.
Сам алгоритм таков: Ьея)п СЧЕТ+ — 1; ВНУТПОРЯДОК(КОРЕНЬ) епд П Рекурсия дает несколько преимуществ и прежде всего простоту программ. Если бы приведенный выше алгоритм не был записан рекурсивно, надо было бы строить явный механизм для прохождения дерева. Двигаться вниз по дереву нетрудно, но чтобы обеспечить возможность вернуться к предку, надо запомнить всех предков в стеке, а операторы работы со стеком усложнили бы алгоритм. ргоседнге ВНУТПОРЯДОК(УЗЕЛ): Ьед|и 1. Н ЛЕВЫЙСЫН[УЗЕЛ)„ьО 1Ьеп ВНУТПОРЯДОК(ЛЕ ВЫЙСЫН[УЗЕЛ))' 2. НОМЕР[УЗЕЛ) -СЧЕТ; 3. СЧЕТ вЂ” СЧЕТ+1; 4. Н ПРАВЫЙСЫН[УЗЕЛ)ФО (Ьеп ВНУТПОРЯДОК(ПРАВЫЙСЫН[УЗЕЛ)» епд Рнс. Е.9. Рекурсивная процедура аая яку~раннего порядка, уе гл.
я. глзглвоткл эфевктивных ллгогитмов Алгоритм 2.2. Вариант алгоритма 2.1 без рекурсии Вход. Тот же, что у алгоритма 2Л. Выход. Тот же, что у алгоритма 2.1. Метод. При прохождении дерева в стеке запоминаются все узлы, которые еще не были занумерованы и которые лежат на пути из корня в узел, рассматриваемый в данный момент. При переходе из узла о к его левому сыну узел о запоминается в стеке. После нахождения левого поддерева для о узел в нумеруется и выталкивается из стека.
Затем нумеруется правое поддерево для о. При переходе из о к его правому сыну узел о ие помещается в стек, поскольку после нумерации правого поддерева мы не хотим возвржцаться в о; более того, мы хотим вернуться к тому предку Ьеа1п СЧЕТ вЂ” 1; УЗЕЛ -КОРЕНЬ; СТЕК вЂ” пустой; тгЫ!е ЛЕВЫЙСЫН[УЗЕЛ[ чьО до Ьеп[п затолкнуть УЗЕЛ в СТЕК; УЗЕЛ вЂ” ЛЕВЫЙСЫН[УЗЕЛ[ епг[; НОМЕР[УЗЕЛ] -СЧЕТ; СЧЕТ -СЧЕТ+1; 11 ПРАВЫЙСЫН[УЗЕЛ[ -ьО [Ьеп Ьея1п УЗЕЛ -ПРАВЫЙСЫН[УЗЕЛ); до1о левый епд; 11 СТЕК не пуст 1Ьеп Ьея1п УЗЕЛ вЂ” элемент в вершине СТЕКа; иытолкнуть из СТЕКа; ио1о центр левый: центр: епб епд Рис.
2ЛО. Алгоритм беа рекурсии для виутреииего порядка. 72 Вариант того же алгоритма, не содержащий рекурсии, мог бы быть таким: т.з. РекуРсия узла п, который еще не занумерован (т. е. к ближайшему предку ги узла п, такому, что о лежит в левом поддереве для го), Этот алгоритм приведен на рис. 2.10. П Корректность варианта е рекурсией легко доказать индукцией по числу вершин в двоичном дереве. Корректность варианта без рекурсии также можно доказать, ио здесь предположение индукции не столь прозрачно и возникают дополнительные трудности в связи с работой со стеком и правильным прохождением двоичного дерева.
С другой стороны, платой за рекурсию может оказаться увеличение постоянных множителей у временной и емкостной сложностей. Естественно выяснить теперь, как перевести алгоритмы с ре- курсией в команды РАМ. В свете теоремы !.2 достаточно рассмот- реть построение РАСП-программы, так как РАСП можно модели- ровать с помощью РАМ с замедлением не более чем в постоянное число раз.
Обсудим довольно прямолинейный способ реализации рекурсии. Он пригоден для всех программ, о которых идет речь в этой книге, но ие охватывает всех случаев, которые могут встре- титься. В основе реализации процедуры а рекурсией лежит стек, где хранятся данные, участвующие во всех вызовах процедуры, при которых она еще не завершила свою работу. Иными словами, в сте- ке находятся все неглобальные данные.
Стек разбит на фрагменты стека, представляющие собой блоки последовательных ячеек (ре- гистров). Каждый вызов процедуры использует фрагмент стека, длина которого зависит от вызываемой процедуры. Пусть сейчас выполняется процедура А, а стек выглядит, как на рис. 2.! 1. Если А вызывает процедуру В, происходит следующее: 1.
В вершину стека помещается фрагмент стека нужного раз- мера. В него входят в порядке, известном процедуре В, (а) указатели фактических параметров этого вызова процедуры В '), (б) пустое место для локальных переменных, участвующих в процедуре В, (в) адрес РАСП-команды в подпрограмме А, которую следует выполнить после того, как данный вызов В кончит работу (адрес возаралш) '). Если  — функция, вырабатывающая некоторое значение, то во фрагмент стека для В также помещается указатель ячейки во фрагменте стека для А, в которую надлежит поместить это значение (адрес значения).
г) Если фактическим параметром является выражение, го его значение вы- числяется во фрагменте стека процедуры А, а указатель помещается во фрагмент для В. Если фактическим параметром является структура (например, массив), то достаточно будет указателя на ее первое слово. Я) Мы берем здесь РАСП в качестве модели именно из-за этих скачков к адресам возврата, доставляющих нам неудобства (хотя, конечно, преодолимые) прн использовании РАМ. уз гл.
з. ялзвквоткд эооиктивных длгоритмов ВЕРШИНА- Рис. 2Л!. Стек ддя вызовов рекурсивной процедуры. 2. Управление переходит к первой команде процедуры В, Адрес значения любого параметра или локального идентификатора, принадлежащего В, разыскивается с помощью индексации во фрагменте стека для В. 3. Когда процедура В кончает работу, управление передастся процедуре А с помощью такой последовательности шагов: (а) адрес возврата извлекается из вершины стека, (б) если  — функция, то значение, обозначенное выражением из ге[пгп-оператора, запоминается в ячейке, предписанной адресом значения в стеке, (в) фрагмент стека процедуры В выталкивается из стека (это ставит в вершину стека фрагмент процедуры А), (г) выполнение процедуры А возобновляется в ячейке, указан- ной в адресе возврата. Пример 2.5.
Рассмотрим процедуру ВНУТПОРЯДОК из алгоритма 2.1. Когда, например, она вызывает себя с фактическим параметром ЛЕВЫЙСЫН[УЗЕЛ), она запоминает в стеке адрес нового значения параметра УЗЕЛ вместе с адресом возврата, указывающим, что по окончании работы этого вызова выполнение программы продолжается со строки 2. Таким образом, переменная УЗЕЛ эффективно заменяется на ЛЕВЫЙСЫН[УЗЕЛ), где бы ни входил УЗЕЛ в это определение процедуры.
Описанную выше реализацию моделирует в некотором смысле соответствующий вариант без рекурсии (алгорнтм 2.2). Однако там мы сделали так, что окончание выполнения вызова ВНУТПОРЯДОК с фактическим параметром ПРАВЫЙСЫН[УЗЕЛ) завершает выполнение и самой вызывающей процедуры. Поэтому нам не обяза- 74 хк елздзлян и вллствгп тельно теперь хранить адрес возврата или УЗЕЛ в стеке, если фактическим параметром является ПРАВЪ|ЙСЫН(УЗЕЛ).
С) Время, требуемое для вызова процедуры, пропорционально времени, требуемому для вычисления значений фактических параметров и запоминания указателей их значений в стеке. Время возвращения, разумеется, не превосходит этого времени. При подсчете времени, затрачиваемого несколькими рекурсивными процедурами, обычно легче всего оценить вес вызова процедуры, осуществляющей этот вызов. Тогда можно оценить сверху как функцию от размера входа разность времени, затрачиваемого на вызов каждой процедуры, и времени, затрачиваемого теми процедурами, которые она вызывает. Суммируя эти оценки по всем вызовам процедур, получаем верхнюю границу общего затраченного времени.
Для подсчета времени работы алгоритма с рекурсией применяются рекуррентные уравнения. С 1-й процедурой связывается функция Т,(л), обозначающая время выполнения (-й процедуры кэк функцию некоторого параметра л рассматриваемого входа. Обычно рекуррентное уравнение для Т,(л) можно записать в терминах времен выполнения процедур, вызываемых процедурой 1. Затем полученная система рекуррентных уравнений решается. Часто в алгоритме фигурирует только одна процедура, и Т(п) зависит лишь от значений Т(т) для конечного числа аргументов т, меньших а.
В следующем разделе мы изучим решения некоторых часто встречающихся систем рекуррентных уравнений. Напомним, что здесь, как и в других местах, весь анализ сложности (веса) основан на равномерной весовой функции. Если брать логарифмическую весовую функцию, то на анализе временной сложности может сказаться длина стека, используемого для реализации процедур с рекурсией. 2.6.
РАЗДЕЛЯЙ И ВЛАСТВУЙ Для решения той или иной задачи ее часто разбивают на части, находят их решения и затем нз них получают решение всей задачи. Этот прием„особенно если его применять рекурсивно, часто приводит к эффективному решению задачи, подзадачи которой представляют собой ее меньшие версии. Проиллюстрируем эту технику на двух примерах, сопровождаемых анализом получающихся рекуррентных уравнений. Рассмотрим задачу о нахождении наибольшего и наименьшего элементов множества 3, содержащего и элементов. Для простоты будем считать, что а есть степень числа 2. Очевидный путь поиска наибольшего и наименьшего элементов состоит в том, чтобы искать нх по отдельности. Например, следующая процедура находит наибольший элементмножества 5, произведя л — 1 сравнений его эле- ГЛ. З.
РАЗРАВОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ ментов: Ьей!и МАХ вЂ” произвольный элемент нз 5; 1ог все другие элементы х нз 5 бо 11 х)МАХ 1)зеп МАХ -х епд Аналогично можно найти наименьший нз остальных л — 1 элементов, произведя л — 2 сравнений. Итак, видим, что для нахождення наибольшего н наименьшего элементов прн а)2 потребуется 2а — 3 сравнений. Применяя прием "разделяй н властвуй", мы разбили бы множество 5 на два подмножества 5, н 5, по п/2 элементов в каждом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
