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

 

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

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

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 220 221 222 223 224 225 < 226 > 227 228 229 230 231 232 .. 316 >> Следующая

ейся только за счет первого внутреннего вызова процедуры, ока ется равной 500, а значит одновременно будет существовать соответствующее число экземпляров процедур (из-за других рекурсивнх взовов это число ока-
ется ее болье).
Если удастся сократить рекурсию, то возможности применения процедуры возрастут за счет снижения требований к памяти. Такое сокращение воз-мо но. остаточно заметить, например, что для одного из направлений мо -но заменить два рекурсивных взова (вверх и вниз или влево и вправо) на два цикла заполнения новм цветом соответствуей полосы области. ри такой замене нужно еще позаботиться о переходах к соседям по другому направлению . Это можно сделать разными путями, но, вообще говоря, для продол-ения процесса без запоминания в стеке или рекурсии точек-соседей полосы (что, как у е говорилось, одно и то е) здесь не обойтись, что видно, в частности, из рисунка 11.2а. Если первой внутренней точкой будет указана точка А, направление циклов горизонтальное, а после заполнения полосы в качестве соседей для перехода к следующей полосе выбираются только верхние и ниние соседи точки А, то верхние треугольники области, отделенные гори-зонтальнми триховми линиями, окаутся не закраенными. апротив, для областей другой формы такой путь вполне правомерен (см. рис. 11.2б), но это уже нарушение условия задачи. Читателю предлагается самостоятельно выяснить вопрос о том, когда можно, а когда нельзя ограничиваться выбором соседей для продол ения процесса только теми точками, которые окру а т
11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ
645
первоначальную текущую. Будут полезны при этом и программные эксперименты.
а) область не закрасится б) область закрасится
Рис. 11.2. ллстрация реения задачи о закраске области
ри реении данной задачи мы смогли убедиться в том, что то или иное выстраивание разбиений даннх приводит к различнм алгоритмам. Так, когда для выбора рекурсивного вызова мы ограничивались лишь соседями, это приводило к неоправданно больой глубине рекурсии, а когда м перели к рассмотрени направлений, появилась опасность некорректного реения.
ло ность разбиения действий для выбранного разбиения даннх различна.
ля простого соседства ничего, кроме явного указания ну нх параметров и совместного (а не последовательного, как приходится делать, используя традиционные языки!) выполнения четырех рекурсивных действий, не требовалось. о алуй, это самй простой случай рекурсии. Следуий, чуть более сло нй, класс случаев был рассмотрен, когда мы сопоставляли рекурсивную и итеративную схемы (см. п. 8.7.1). Здесь вся сложность прямо связано со сложностью и с избыточностью рекуррентного соотношения.
ринципиально более сло ными явля тся рекурсивные алгоритмы, ко-торе использу тся для перебора и генерации вариантов. етод организации таких программ обсуждаются в следующем параграфе.
§11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ
В практике программирования зачасту приходится реать задачи, в которых необходимо организовать перебор вариантов. Простейший случай пе-
646
11. ,
ребора — это цикл, кадая итерация которого выделяет вариант даннх для конкретной обработки. Вложенные циклы позволяют выделять все пары, тройки и тому подобные группы данных. Так, для массива A [1..N] в цикле for i := 1 to N do for j := 1 to N do for k := 1 to N do ...
индексы i, j, и k могут быть использованы, чтобы задать вычисления для всех троек (A [i], A [j], A [k]), причем каждая позиция в тройке пробегает все элементы массива A. Для перебора элементов без их повторения целесообразно использовать цикл
for i := 1 to N - 2 do for j := i + 1 to N - 1 do for k := j + 1 to N do ...
днако циклическая схема далеко не всегда применима. апример, для генерации последовательностей кортежей 1 ^ j ^ N,
(A
(A A [i2]),
(A [i1],A[i2], A [im])
не получится воспользоваться вложенными циклами, поскольку здесь глубина вло енности цикла, поро даего отдельнй корте , не мо ет бть определена статически. е работает циклическая схема и тогда, когда не удается алгоритмически явно сформулировать условия окончания циклов.
11.3.1. Перебор/генерация вариантов с возвратами
ля реения переборнх задач, подобнх только что представленной, можно воспользоваться методом перебора/генерации вариантов с возвратами. уть его состоит в следуем. пределяется мно ество возмо нх, но не обязательно окончательных, вариантов, для которого можно задать переход от одного варианта к другим. Это мно ество просматривается с отсеиванием неудовлетворительных вариантов. ри нахо дении неудачного варианта происходит возврат к преддуему варианту и поптка перейти от него к следуему. Если все возмо не следуие варианты для данного варианта оказываются неудовлетворительными, то он отвергается и происходит
11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ
647
возврат к тому варианту, из которого он получен. Таким образом обеспечивается рекурсивный просмотр всех вариантов.
Все задачи, для которых оправдано практическое применение метода, можно разделить на два вида, в зависимости от того, подготовлены или нет просматриваемые варианты до выполнения алгоритма, реализуего метод. В первом случае метод становится переборным, а во втором — генерационным. Однако для применения метода это не очень существенно, поскольку в любом случае можно говорить о подпрограмме-поставщике просматриваемых вариантов, осуествляей доступ либо к готовым, либо к генерируемм вариантам. менно это обстоятельство отра ено в названии метода
Предыдущая << 1 .. 220 221 222 223 224 225 < 226 > 227 228 229 230 231 232 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100