Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 165

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 159 160 161 162 163 164 < 165 > 166 167 168 169 170 171 .. 316 >> Следующая

Рекуррентные соотноения, определяие функции, практически без затруднений могут быть использованы при составлении рекурсивных программ.
Предупреждение
Буквальное следование рекуррентному определению почти всегда таит в себе опасность повторного счета и фантастической потери эффективности вычислений.
Следующие примеры демонстрируют такую опасность.
Пример 8.7.1. Пусть требуется вычислить N-ое число Фибоначчи, определяемое соотноением:
Ф(1) = Ф(2) = 1;
<1>(N) = <1>(N — 1) + <3>(N — 2), при N > 1.
ункци
8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ
467
Программа 8.7.2
function F(N: Integer): Integer; begin if N < 2
then F := 1
else F := F ( N - 1 ) + F ( N - 2 )
end;
заданну в точном соответствии с рекуррентным соотноением, нельзя признать удовлетворительной.
В самом деле, вычисление F(5) требует вычислить F(4) и F(3), которые затем складываются. Каждое из них есть вызов F без передачи какой-либо информации об истории вчислений. В результате F(3) считается двады: сначала в рамках вчисления F(4), т. е. в первом аргументе вра ения F ( N -1) + F(N-2), а затем повторно в ходе вычисления F(5) при вычислении второго аргумента этого е вра ения. В сво очередь, F(2) вычисляется уже три раза: дважды при каждом вызове F(3) и еще один раз в ходе вычисления F(4). Здесь повторный счет возник в связи с тем, что алгоритм не предусматривает сохранения информации о ранее вчисленных значениях F(K), 1 < K < N.
Таким образом, вычисление чисел Фибоначчи, буквально следующее определяющему рекуррентному соотношению, приводит к неэффективности. Для обучаемых рекомендуется выполнить упражнения 1-4. Конец примера 8.7.1.
а примере функции F легко видеть, что в комплекте локальнх данных подпрограммы должна запоминаться точка возврата: в зависимости от того, вызвана функция как первый или второй операнд сложения, требуется обеспечить тот или иной корректнй возврат при заверении экземпляра.
риер 8.7.2. Вычисление наибольего обего делителя ( ) двух неотрицательных чисел. НОД(х, у) определяется как максимальное целое, которое делит без остатка x и у. Алгоритм основан на следующих свойствах функции :
( x, x) = x;
( x, у ) = ( x, у — x ) , если у > x.
468
ГЛАВА 8. ПОДПРОГРАММЫ
Программа 8.7.3
procedure MCD (x,y : Integer 0..MAXINT; var R : Integer); begin
if x = y
then R := x
else if x > y
then MCD ( y, x, R ) {*}
else MCD (x, y - x, R)
end;
C
void MCD ( int x, y, *int R) { if (x==y) &R = x;
else if (x>y) MCD (y, x, &R); else MCD (x, y - x, &R);
}
Замечания к процедуре MCD:
1. Приведенный алгоритм содержит ошибку: при вызове процедуры с первым или вторым параметром, равным нулю, произойдет 'бесконечное' порождение экземпляров (почему?). Обучаемым предлагается исправить программу, например, с учетом того, что для любого x НОД(0, x) = НОД(х, о) = x.
2. Программа может быть улучшена за счет замены оператора MCD (y,x,R) в строке { * } на MCD (y,x - y,R) .Предлагается определить отличие двух вариантов вычислений.
3. ля углубления понимания механизма рекурсии полезно проследить, какие изменения процесса вычислений вызовет объявление x и y как параметров-переменных.
4. Как вы думаете, почему в этой программе, внешне схожей с процедурой вычисления чисел ибоначчи, не происходит повторнй счет?
егко показать, что если некоторая функция для всех поло ительнх целых x и y обладает указанными свойствами, то она является функцией, вычисляющей наибольший общий делитель двух чисел. Таким образом, с точностью
8.7.
469
до ошибки, отмеченной в замечании 1, процедура MCD корректно решает задачу.
Конец примера 8.7.2.
8.7.2. Рекурсия через параметры
Понятие рекурсивной процедуры возникает в связи с осуществимостью и полезностью применения в практике программирования приема, когда в ходе вычислений одновременно суествует несколько экземпляров одной и той же программной единицы (см. п. 8.4.3). Как правило, различаются явная рекурсия — вызов процедуры в ней самой, и взаимная (опосредованная) рекурсия — в тексте программы представлена последовательность процедур, вызывающих друг друга и в конечном итоге вызывающих первую из процедур последовательности.
тличительной особенность всех таких случаев рекурсии является то, что она всегда мо ет бть выявлена путем анализа текстов самих подпрограмм. ри взаимной рекурсии этот анализ довольно сло ен, но, тем не менее, вполне осуществим (обучаемым предлагается построить соответствую-ий алгоритм).
В практике программирования встречается ее один способ задания рекурсивных алгоритмов, который не всегда мо ет распознаваться на основании только такой информации. Этот случай связан с заданием рекурсии через параметры. В языках со строгой типизацией (например, в Pascal, где для повышения надежности программирования вводится ограничение: в параметрах-функциях и параметрах-процедурах не допуска тся ине параметры, кроме параметров, передаваемых по значени ) такая рекурсия невозмо на.
о если соответствуие ограничения на параметризаци не накладыва т-ся, появляется возможность задавать процедуры, становящиеся рекурсивными через параметр .
Предыдущая << 1 .. 159 160 161 162 163 164 < 165 > 166 167 168 169 170 171 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100