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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

25
Подмножества множества
Порождение подмножеств множества (a
1
,a
2
,…,a
n
) эквивалентно
порождению n - разрядных двоичных наборов: a
i
принадлежит
подмножеству, если и только если i-й разряд равен единице. Таким
образом, задача порождения всех подмножеств множества сводит-
ся к задаче порождения всех возможных двоичных последователь-
ностей длины n.
Следующий алгоритм описывает эту процедуру:
Листинг 6.4
Алгоритм генерации подмножеств множества.
for i=0 to n do b
i
←
0;
while b
n
≠
1 do
begin
вывести (b
n-1
b
n-2
…b
0
);
i
←
0;
while b
i
=1 do
begin
b
i
←
0;
i
←
i+1;
end;
b
i
←
1;
end.

Страницы