Непейвода Н.Н. Программирование. Раздел 3

Непейвода Н.Н. Программирование. Страница 367

Рекуррентные соотношения, определяющие функции, практически без затруднений могут быть использованы при составлении рекурсивных про­грамм.

Предупреждение

Буквальное следование рекуррентному определению почти всегда таит в себе опасность повторного счета и фантастической потери эффективности вычислений.

Следующие примеры демонстрируют такую опасность.

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

В самом деле, вычисление Р(5) требует вычислить Р(4) и Р(3), которые затем складываются. Каждое из них есть вызов Р без передачи какойлибо информации об истории вычислений. В результате Р(3) считается дважды: сначала в рамках вычисления Р(4), т. е. в первом аргументе выражения Р ( N 1 ) + Р ( N 2 ), а затем повторно в ходе вычисления Р(5) при вы­числении второго аргумента этого же выражения. В свою очередь, Р(2) вы­числяется уже три раза: дважды при каждом вызове Р(3) и еще один раз в ходе вычисления Р(4). Здесь повторный счет возник в связи с тем, что ал­горитм не предусматривает сохранения информации о ранее вычисленных значениях Р(К), 1 ^ К <N.

Таким образом, вычисление чисел Фибоначчи, буквально следующее определяющему рекуррентному соотношению, приводит к неэффективно­сти. Для обучаемых рекомендуется выполнить упражнения 14. Конец примера 8.7.1.

На примере функции Р легко видеть, что в комплекте локальных данных подпрограммы должна запоминаться точка возврата: в зависимости от то­го, вызвана функция как первый или второй операнд сложения, требуется обеспечить тот или иной корректный возврат при завершении экземпляра.

Пример 8.7.2. Вычисление наибольшего общего делителя (НОД) двух не­отрицательных чисел. НОД(х, у) определяется как максимальное целое, ко­торое делит безостатка х и у. Алгоритм основан на следующихсво йствах

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета &quot;Ангара-А5В&quot; в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие &quot;Крокодилы&quot;

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама