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

 

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

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

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

for k := k to N do begin
V [Ie] := k; Handle ( V, Ie );
if Ie < N then SelectF( Ie + 1, 1 );
{if k < N then SelectF( Ie, k + 1 ); — Этот оператор исчезает!}
К сожалению, небольшое повышение эффективности, которое достигается при такой модификации, сниает наглядность программы: вместе со вторым рекурсивнм вызовом исчезает явно показанное в пренем тексте представление о принятом упорядочивании. Это следствие плохой совместимости рекурсий и циклов! Таким образом, данную модификацию можно рекомендавать лиь в тех случаях, когда требуется особая забота об эффективности. рограмма 11.3.3 легко мо ет быть преобразована так, чтобы в результируих кортеах не появлялись повторяиеся элементы. ля этого в нее мо но встроить фильтраци : проверку повторения элемента, которая будет экранировать присваивание значения k элементу массива V[Ie] и первый рекурсивный вызов. В Pascal^ это достигается с помощью использования мно ества задействованнх индексов: var Ma: set of 1..N;
В результате получается программа 11.3.4.
end;
656
11. ,
Программа 11.3.4
procedure SelectF1( Ie, k : Integer); begin
if not (k in Ma) then begin
Ma := Ma + [k]; V [Ie] := k; Handle ( V, Ie );
if Ie < N then SelectF( Ie + 1, 1 ); Ma := Ma - [k];
end
if k < N then SelectF( Ie, k + 1 ); end;
роверка, добавление и удаление элемента мно ества — бстрые операции при представлении малых множеств (см. п. 9.3.5), принятом в языке Pascal. Поэтому получается практически чистый выигрыш в эффективности, и во многих случаях такое прямое преобразование можно рекомендавать. Если это не так, то требуется более точно (или поро более грубо, но более просто; необходимо соблюдение баланса между сложностью проверки и слож-ность повторнх вызовов) определить порядок корте ей, не имеих повторений. спользование мно еств мо ет бть рекомендовано для реения еще одной переборной задачи, подобной только что рассмотренной: для построения мно еств неповторяихся индексов (упранение 3).
Все приведенные реения (а так е другие реения, оставленные для самостоятельного рассмотрения) демонстриру т ситуаци , в которой контексты рекурсий содерат суественну дол вычисляемых результатов. Именно здесь обычно хорошо работает метод перебора/генерации. В сущности он представляет собой неявное задание отноения полного порядка на даннх, который согласован с естественным частичнм порядком. То, что такое доопределение чае всего не является однозначнм, понятно. Результат реения, а так е его эффективность обычно суественно зависят от того, как именно произведено доопределение порядка.
редставленные программы корректн с точки зрения конечности вчи-слений. днако их анализ показвает, что все они не явля тся сильно корректными, и, соотвественно, вызывают повторный счет. Это хорошо видно из схемы на рис. 11.4: окончания кортежей для разных значений ie-того элемента оказываются одинаковыми. Для данной задачи повторный счет не очень
11.3.
657
велик, но в других случаях он мо ет оказаться значительным. В связи с этим мы покажем метод, с помощью которого можно подменять повторный счет запоминанием результатов. Суть метода в переходе к рекурсивным структурам данных, которе естественно сочета тся с рекурсивными методами в программировании, а возмо ность его применения показвает схема на рис. 11.5, на которой специальными стрелками выделены требуеме связи
ie-ый
Рис. 11.5. Схема упорядочивания с общими окончаниями кортежей
меду составляими разбиения даннх для обсу даемой задачи.
Программная структура, которая в состоянии обеспечить такие связи — список, которй заменяет массив V (точнее, содеримое этого массива, меняющееся в динамике вычислений). Для перехода от массива к списку нужно пополнить общий контекст программы описаниями типов, определяющих нову структуру данных:
type PL =ЛТ1_;
TL = record inf: Integer; down, right: PL;
end;
где inf — поле для размеения индекса, а down и right — поля ссылок на следуий элемент в вертикальном и горизонтальном направлениях. ере-менная, которая будет указывать на список в целом, описывается как: var Sta : PL;
В новой программе у рекурсивной процедуры SelectF2 появляется дополнительный параметр co, которй показвает номер в горизонтальном направлении (ранее он был бы излиним из-за его совпадения с индексом Ie).
658
11. ,
алгоритме процедур вместо присваивания k элементу массива генерируется новый элемент списка. Первый рекурсивный вызов аналогичен такому же вызову в прежней программе. Если мы переделаем и второй рекурсивный вызов в подобной манере, то получится реение, отличие которого от SelectF будет лиь в том, что следы вчисления корте ей сохраняться в списке.
ля искл чения повторного счета вместо этого надо встроить генераци серии элементов вертикального направления с общей ссылкой на Окончание. В этом построении неизбежно теряется одно качество прежнего решения: теперь нельзя совместить обработку (вывод) с формированием списка. Это вполне понятно, поскольку дополнительный просмотр только что построенных элементов вертикального направления с ну ными для обработки просмотрами по горизонтальному направлению лишает всех преимуществ решение о слиянии Окончаний. Следующая программа реализует процедуру SelectF2, обладающую указанными свойствами.
Предыдущая << 1 .. 223 224 225 226 227 228 < 229 > 230 231 232 233 234 235 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100