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

 

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

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

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

Variants [1] := 1; Select (Variants, 1 )
ервая версия процедуры Select является некорректной.
Программа 11.3.1
procedure Select ( V : TVariants; K : Integer ); begin
Handle( V, K ); if V [ K ] < N
then begin V [ K ] := V [ K ] + 1; Select ( V, K );
end
else if K < N
then begin K := K + 1;
V [ K ] := 1; Select ( V, K); {*}
end
end;
11.3.
651
на не учитвает, что после увеличения длин кортеа и просмотра всех расширенных кортежей нужно довести до конца процесс просмотра для кортежа меньшей длины (см. строку {*}). В результате выполнения процедуры будут напечатаны не все вариант :
1 2 3 4
41 42 43 44 441
равильная версия, представленная ни е, избавлена от оибки с помо-ь другого порядка следования корте ей. ри постановке реаемой задачи этот порядок не был фиксирован, а потому разработчик алгоритма может выбирать его по своему усмотрению.
Программа 11.3.2
procedure Select (V : TVariants; K : Integer); begin
Handle( V, K ); if K < N
then begin V [ K + 1 ] := 1;
Select ( V, K + 1 ); end; ifV[K]<N
then begin V [ K ] := V [ K ] + 1;
Select ( V, K ); end;
end;
Необходимо заметить, что для порядка перебора вариантов, выбранного в данной версии процедур Select, передача параметра V как значения — расточительное реение. но приводит к избточному дублировани массивов, тогда как в данном случае этого легко избеать: достаточно увидеть,
652
11. ,
что при рекурсивных вызовах мо но передавать только изменения вариантов и восстанавливать их после возвратов. Это довольно характерный прием для обсуждаемого метода. Однако в общем случае без запоминания всей информации о варианте не обойтись. оэтому в тексте процедуры Select бло реено сохранить полное запоминание, а соответствуее преобразование предоставить читател .
Способы сокращения запоминаемых сведений о вариантах следует рассматривать как оптимизацию алгоритма. При оптимизации решения обсу-даемой задачи для запоминания вариантов достаточно сохранять лиь длины корте ей (т. е. оставить только второй параметр процедуры). ыбор порядка перебора корте ей позволяет не заботиться о передаче изменений вариантов и о восстановлении. Понятно, что от порядка перебора вариантов зависит и порядок вывода порождаемых кортежей. Для приводимой процедур рост индексов по мере вывода происходит справа налево:
1
1 1
1 1 1
1 1 1 1
1 1 1 2
1 1 1 3
1 1 1 4
1 1 2
1 1 2 1
1 1 2 2
1 1 2 3
1 1 2 4
1 1 3
1 1 3 1
1 1 3 2
редставленное реение демонстрирует подход, который мо но считать типичным для стиля структурного программирования. Он характеризуется тем, что разбиение даннх и действий исходит из понятия обстановки вчи-слений, а реение об обраении к рекурсии принимается на основе анализа елаемых преобразований даннх обстановки. В качестве альтернативы этому подходу мо но указать на разбиение данных и действий, основанные на анализе результатов в целом, которые должны быть получены при решении.
11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ
653
Такой подход более функционален по сути, чем операционное манипулирование элементами обстановки вычислений. На нашей задаче он может быть продемонстрирован следующим образом.
но ество корте ей, которое долно быть построено, мо ет быть упорядочено так, как это схематически показано нарис. 11.4. Схема явно выделяет два направления упорядоченности: горизонтальное, соответствующее наращиванию размеров кортежей, и вертикальное, отражающее порядок между группами кортежей, которые имеют совпадающее начало и различаются значением ie-того элемента.
дея нового реения закл чается в том, чтобы явно использовать эти направления в алгоритме. В соответствии с этой идеей рекурсивная процедура SelectF имеет два параметра-аргумента, отвечающие за горизонтальное (Ie) и вертикальное (k) направления, Ie, k Є {1,..., N}. Здесь уже учтено, что передача процедуре в качестве параметра такого элемента обстановки как массив V, не требуется. Процесс порождения нового кортежа из предыдущего есть присваивание значения k элементу массива V[Ie]. H азначение следую -щих кортежей, соответствующих текущему началу и различающихся окончаниями — вызов SelectF( Ie + 1, 1), а смена текущего Ie-символа — SelectF( Ie, k + 1 ). В результате этих рассуждений получается программа 11.3.3, которая по существу от предыдущей отличается только тем, как задается Ie-символ.
Программа 11.3.3
procedure SelectF( Ie, k : Integer); begin
V [Ie] := k; Handle ( V, Ie );
if Ie < N then SelectF( Ie + 1, 1 ); if k < N then SelectF( Ie, k + 1 );
Стоит обратить внимание на то, что порядок рекурсивнх вызовов суестве-нен. Так, при N = 2 в указанном порядке строится последовательность кортежей
end;
1 1 1 2
1 2
654
11. ,
Номера элементов в кортежах
1 ie-1 ie ie+1 . . . N
Начало ¦ ¦ 1 1 1
ie-ый элемент
Рис. 11.4. Схема упорядочивания кортежей
11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ
655
2 2
1
2
При обратном порядке некоторые кортежи пропадают, другие — повторяются:
1 2
21 22 21 22
Причина тому понятна: направления упорядоченности не независимы! з приведенной программы видно, что второй рекурсивный вызов мо но преобразовать в цикл. тогда тело процедуры превраается в:
Предыдущая << 1 .. 222 223 224 225 226 227 < 228 > 229 230 231 232 233 234 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100