Структуры данных и алгоритмы (1021739), страница 18
Текст из файла (страница 18)
Таким образом, извлекая активационную запись из стека,для последнеговызова процедуры Р, можно управлять возвратом к точке в программе, из которой Рвызывалась (эта точка, называемая адресом возврата, помещается в активационнуюзапись процедуры Р при вызове этой процедуры).Рекурсивные вызовы процедур упрощают структуру многих программ. Но в некоторых языках программирования процедурные вызовы более "дорогие" (по времени выполнения), чем непосредственное выполнение операторов, поэтому программа можетработать быстрее, если из нее исключить рекурсивные процедуры. Здесь мы не выступаем в поддержку обязательного исключения рекурсивных или каких-либо иных процедур, очень часто структурная простота программы важна не менее, чем ее малое время выполнения.
На практике бывают ситуации, когда после реализации части программного проекта возникает необходимость исключить рекурсию, и основная цельэтого обсуждения заключается только в том, чтобы подвести к вопросу о том, как можно преобразовать рекурсивную процедуру в нерекурсивную с помощью стеков.Пример 2.3. Рассмотрим рекурсивное и нерекурсивное решения упрощенной версии классической задачи о ранце, где мы имеем целевое значение t и конечное множество положительных целых весов wlt u>2, •••, и>„. Необходимо определить, можноли из множества весов выбрать такой их набор, чтобы их сумма точно равнялась величине t. Например, если t = 10 и множество весов составляют числа 7, 5, 4, 4 и 1,то можно выбрать второй, третий и пятый веса, поскольку 5 + 4 + 1 = 10.В листинге 2.14 представлена функция knapsack (ранец), работающая с массивомвесов weights: аггау[1..п] of integer.
Функция knapsack(s,i) определяет, существуетли набор весов из множества весов от weights[i] до weights[ri], сумма которых равна s,и если есть, то печатает этот набор весов. В частном случае, когда s = 0, пустое множество весов считается решением. Если s < 0 или i > п (выход за заданное множество весов), то считаем, что решение не существует или не найдено (функция knapsackвозвращает значение false).Если ни один из перечисленных случаев к текущей ситуации не применим, то сновавызывается knapsack(s - ш„ i + 1), чтобы посмотреть, существует ли решение, котороевключает вес w,.
Если в этом случае решение существует, то оно является и решениемисходной задачи; это решение, включая wt, распечатывается. Если решения нет, то вызывается функция knapsack(s, i + 1) для поиска решения без участия веса wt. П2.6. СТЕКИ И РЕКУРСИВНЫЕ ПРОЦЕДУРЫ69•'•''р"...•'•'•.-И.?:'''''.'•'- .-.ГЛистинг 2.14.
Рекурсивное решение задачи о ранце(1)(2)(3)(4)(5)(6)(7)(8)/'^tV'-','!"function knapsack ( target: integer; candidate: integer) :.boolean;beginif target:= 0 thenreturn(true)else if (target < 0) or (candidate > л) thenreturn(false)else { ищется решение с и без candidate }if knapsack(target-weights[candidate], Candidate+1)thenbeginwriteln(weights[Candidate]);return(true)endelse { возможное решение без candidate }return(knapsack(target, candidate +1))end; { knapsack }Исключение „концевых" рекурсийЧасто можно чисто механически исключить последний вызов процедуры самойсебя.
Если процедура Р(х) на последнем шаге вызывает Р(у), то этот вызов можнозаменить оператором присваивания х := у и последующим переходом в начало кодапроцедуры Р. Здесь у может быть выражением, а х должно принимать значение, т.е.это значение хранится в локальной переменной. Если процедура имеет несколько параметров, то с ними надо поступить точно так же, как описано для х и у.Описанная схема вызывает повторное выполнение процедуры Р с новым значением параметра х с точно таким же конечным эффектом, какой был бы при рекурсивном вызове Р(у) и возврате из этого вызова.
Отметим, что тот факт, что некоторые локальные переменные процедуры Р принимают новые значения, не имеет последствий, поскольку процедура уже не должна использовать старых значенийэтих переменных.Подобный вариант исключения рекурсивного вызова можно проиллюстрироватьна примере листинга 2.14, где последний шаг функции knapsack возвращает результат рекурсивного вызова без параметров.
В такой ситуации также можно заменитьвызов операторами присваивания значений параметрам и переходом в начало кодафункции. В данном случае строку (8) в листинге 2.14 можно заменить следующимиоператорами:Candidate:= candidate + 1;goto beginningгде beginning (начало) — метка на оператор строки (1). Отметим, что параметрtarget не переприсваивается, так как сохраняет старое значение. Поэтому проверкиего значения в строках (1) и (3) фактически не нужны, необходимо только проверитьусловие, что candidate > п в строке (3).Полное исключение рекурсийОписанная выше техника исключения рекурсивных вызовов полностью удаляетрекурсии только тогда, когда рекурсивные вызовы находятся в конце процедур и вызов осуществляется в форме, позволяющей его исключить.
Существует более общийподход, позволяющий преобразовать любую рекурсивную процедуру (или функцию)в нерекурсивную, но этот подход вводит определяемые пользователем стеки. В общемслучае этот стек хранит следующее.1.70Текущие значения параметров процедуры.ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХ2.3.Текущие значения всех локальных переменных процедуры.Адрес возврата, т.е. адрес места, куда должно перейти управление после завершения процедуры.В случае функции knapsack положение упрощается.
Во-первых, заметим, что привсех вызовах (при этом происходит вставка записи в стек) параметр candidate увеличивается на единицу. Поэтому мы можем хранить значение candidate как глобальную переменную, значение которой увеличивается на единицу при вставке записи встек и уменьшается на единицу при извлечении записи из стека.Во-вторых, следующее упрощение можно сделать, если в стеке хранить модифицированный адрес возврата. Отметим, что адрес возврата для этой функции можетнаходиться или в другой процедуре, вызвавшей knapsack, или в строке (5), или встроке (8).
Можно представить эти три возможности с помощью "статуса", которыйможет принимать три значения.1.2.попе (нет). Показывает, что вызов осуществлен из внешней процедуры.included (включенный). Указывает на вызов из строки (5), которая включает весweights[candidate] в возможное решение.3. excluded (исключенный). Указывает на вызов из строки (8), которая исключаетвес weights[candidatc] из возможного решения.Если мы сохраним статус как адрес возврата, то сможем рассматривать target какглобальную переменную. При изменении статуса с попе на included мы вычитаем весweights[candidate] из target и прибавляем его обратно при изменении статуса сincluded на excluded. Чтобы показать, что рекурсивно вызываемой knapsack найденорешение, используем глобальную переменную winflag (флаг победы).
Получив одинраз значение true, winflag сохраняет это значение, из стека извлекаются записи, и тевеса, которые имеют статус included, распечатываются. В описанной ситуации стекможно объявить как список статусов (statuses) следующим способом:typestatuses = (поле, included, excluded);STACK = { подходящее объявление стека }В листинге 2.15 приведена нерекурсивная процедура knapsack, оперирующая смассивом весов weights. Хотя эта процедура может выполняться быстрее, чем исходная рекурсивная функция knapsack, но видно, что код ее длиннее и она труднее дляпонимания.
Поэтому исключение рекурсий следует применять только тогда, когдаскорость выполнения программы является решающим фактором.Листинг 2.15. Нерекурсивная процедура knapsackprocedure knapsack ( target: integer ) ;varcandidate: integer;winflag: boolean;S: STACK;begincandidate— 1;winflag:= false;MAKENULL(S);PUSH(none, S);{ инициализация стека для рассмотрения weights[l] }repeatif winflag then begin{ извлечение записи из стека ипечать весов, входящих в решение }if TOP(S) = included then2.6. СТЕКИ И РЕКУРСИВНЫЕ ПРОЦЕДУРЫ71.writeln(weights[candidate]) ;candidate:- candidate - 1;POP(S)endelse if target = 0 then begin { решение найдено }winflag-.= true;candidate:= candidate - 1;POP(S)endelse if (((target < 0) and (TOP(S) = none))or (candidate > n)) then begin { решения нет }Candidate:= candidate - 1;POP (S)endelse { решения пока нет,рассматривается статус текущего кандидата }if TOP(S) = none then begin{ первая попытка включить кандидата }target:= target - weights[candidate];candidates candidate + 1;POP(S); PUSH(included, S); PUSH(none, S)endelse if TOP(S) = included then begin{ попытка исключить кандидата }target:= target + weights[Candidate] -,candidate:= candidate + 1;POP(S); PUSH(excluded, S); PUSH(поле, S)endelse begin { TOP(S) = excluded;отказ от текущего выбора }POP;(S);candidate:= candidate - 1enduntil EMPTY(S)end; { knapsack""}Упражнения2.1.2.2.2.3.Напишите с помощью операторов списка программу печати элементов списка.Напишите программы вставки, удаления и поиска элементов отсортированногосписка, используя для реализации спискаа) массив;б) указатели;в) курсоры.Каково время выполнения каждой из этих программ?Напишите программу для слиянияа) двух отсортированных списков;б) и отсортированных списков.2.4.Напишите программу объединения списков в один список.2.5.Рассмотрим многочлены вида р(х) = q*' + с2х' +•••+ с„х'-, где et > е2 > ...
> е„ >0.Такой многочлен можно представить в виде связанного списка, где каждаяячейка имеет три поля: одно — для коэффициента с(, второе — для показателя721гГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХ2.6.*2.7.степени eit третье — для указателя на следующую ячейку. Для описанногопредставления многочленов напишите программу их дифференцирования.Напишите программу сложения и умножения многочленов, используя ихпредставление, описанное в упражнении 2.5.Пусть ячейки объявлены следующим образом:typeсе11type = recordbit: 0..1;next: T celltypeend;Двоичное число bib2...bn, где каждое bt = О, 1 имеет десятичное значениеR2.8.*2.9.^Ь^"'1 . Это число можно представить в виде списка bi, Ьг, ..., Ьп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
