Лекции по дискретной математике. Ч.II. Комбинаторика, разостные уравнения, алгоритмы на графах. Гайдамака Ю.В - 24 стр.

UptoLike

ВУЗ: 

РУДН | Москва

Составители: 

Рубрика: 

Разбиения чисел
Рассмотрим задачу генерации разбиений натурального числа n
в последовательность неотрицательных целых чисел (p
1
,…,p
k
), так
что p
1
+…+p
k
=n и порядок чисел p
i
не важен. Т.о. не делается раз-
личий между 1+1+2, 1+2+1, 2+1+1.
Разбиения числа n на l компонентов можно генерировать в воз-
растающем лексикографическом порядке, начиная с p
1
=p
2
=…
=p
l-1
=1, и продолжая процесс следующим образом. Для получения
следующего разбиения из текущего просматриваем элементы
справа налево, останавливаясь на самом правом p
i
, таком, что
p
l
-p
i
≥
2. Заменяем затем p
j
на p
i+1
для j=i,i+1,…,l-1 и после этого
заменяем p
l
на .
∑
−
=
−
1l
1j
j
pn
Например, если n=12 и l=5, а разбиение имеет вид (11334), то 4
на 2 больше самой правой 1, и следующее разбиение будет иметь
вид (12225).
Когда ни один из элементов разбиения не отличается от по-
следнего больше, чем на единицу, то процедура заканчивается.
Следующий алгоритм реализует эту процедуру:
Листинг 6.3
Алгоритм генерации разбиения чисел.
l
←
1;
p
1
←
n;
p
0
←
-1;
while l
≤
n do
begin
вывести (p
1
,…,p
l
);
i
←
l-1;
while p
l
-p
i
<2 do i
←
i-1;
if i
≠
0 then for j=l-1 to i by –1 do p
j
←
p
i+1;
else for j=1 to l do p
j
←
1;
l
←
l+1;
p
l
←
n- ;
∑
−
=
1l
1j
j
p
end.
24

Страницы