2014-02-18
1246
End.
Else
End.
Else
End.
Else
Begin
End.
Begin
Else
Begin
Else
begin á Определить Sk ñ;
for у Î Sk do
begin Xk:= y; Solve(k+1) end;
end;
end;
Конкретный набор требований, которым должны удовлетворять сгенерированные векторы, определяются множествами Sk, а также правилом проверки того, что Х – решение.
1. Алгоритм генерации r-размещений с повторениями. В размещениях с повторениями на k-месте должно стоять число из набора 1,…, n независимо от чисел, стоящих на предыдущих позициях. То есть для любого k всегда будет Sk= {1, …, n }.
Пример 2.1. Пусть r = 3; n =2. Надо получить следующие векторы Х: (1 1 1), (1 1 2), (1 2 1), (1 2 2), (2 1 1), … (2 2 2).
Обозначим А[j] – номер предмета, находящегося на j-м месте, j = 1,…r. Предлагается следующий алгоритм.
Procedure Razm_P(k);
if k=r+1 then write(A[1],…A[r]);
for y:=1 to n do
begin A[k]:=y; Razm_P(k+1);
end;
end;
Razm_P(1);
Назначение процедуры Razm_P(k) – получение k-й компоненты вектора Х =(A[1],…A[r]). Если k = r+1 – это означает, что вектор полностью получен, и надо его использовать (вывести на экран). В противном случае надо получить следующую компоненту. Так как на ее месте может стоять любое число от 1 до n, то Sk = {1, … n}, перебор элементов этого множества обеспечивается циклом for y:=1 to n do
|
|
|
2. Алгоритм генерации r-размещений без повторений. Отличие данного алгоритма от предыдущего в том, что каждое из возможных значений 1, … n элементов размещений можно использовать только один раз. Поэтому в процедуре Razm_BP используется массив dop[j], j = 1,…n, в котором dop[j] = 1, если значение j не было использовано и dop[j] = 0, в противном случае. При продвижении вглубь рекурсии значение j блокируется, чтобы его нельзя было использовать повторно, а при откате – восстанавливается.
Procedure Razm_BP(k);
if k=r+1 then write(A[1],…A[r]);
for y:=1 to n do
if dop[y] > 0 then
begin A[k]:=y; dop[y]:=dop[y]-1;
Razm_BP(k+1); dop[y]:=dop[y]+1;
end;
end;
begin for i:=1 to n do dop[i]:= 1;
Razm_BP(1);
Данный алгоритм можно также использовать для генерации перестановок без повторений при r = n.
3. Алгоритм генерации перестановок с повторениями. Этот алгоритм похож на предыдущий, только первоначально dop[j]=n[j] – число повторений j-го значения, j = 1,…m. По мере использования этого значения переменная dop[j] уменьшается, пока не станет равной 0. Это будет означать, что данное значение уже нельзя использовать. Предлагается следующий алгоритм генерации перестановок из m объектов при 
.
Procedure Perest_P(k);
begin if k=n0+1 then write(P[1],…P[n0]);
for y:=1 to m do
if dop[y] > 0 then
begin P[k]:=y; dop[y]:=dop[y]-1;
Lex(k+1); dop[y]:=dop[y]+1;
end;
begin n0=0;
for j:=1 to m do
begin dop[j]:=n[j]; n0:=n0+n[j]; end;
Lex(1);
4. Алгоритм генерации r-сочетаний без повторений. Алгоритм похож на генерацию размещений без повторений, отличие в том, что в каждом сочетании не допускаются перестановки элементов, т.е. каждый следующий элемент больше предыдущего.
|
|
|
Пример 2.2. Подобные 3-сочетания из 5 выглядят так: (1 2 3), (1 2 4), (1 2 5), (1 3 4), … (1 4 5), (2 3 4), … – т.е. генерируется возрастающая последовательность 3-значных чисел.
Для обеспечения этого условия в генерации сочетаний используется цикл for y:=t to n do, а не for y:=1 to n do, как в размещениях, где переменная t подбирается по правилу if k<=1 then t:=1 else t:=А[k-1]+1.
Procedure Sochet_BP(k);
begin if k=r+1 then write(А[1],…А[r]);
begin if k<=1 then t:=1 else t:=А[k-1]+1;
for y:=t to n do
if dop[y] > 0 then
begin А[k]:=y; dop[y]:=dop[y]-1;
Sochet_BP(k+1);
dop[y]:=dop[y]+1;
end;
end;
end;
begin for i:=1 to n do dop[i]:= 1;
Sochet_BP(1);
