9. Генерация всех подмножеств универсума. Алгоритм генерации всех подмножеств данного множества.
Генерация всех подмножеств универсумов
В алгоритмах часто бывает необходимо рассмотреть все подмножества заданного множества.
В памяти ЭВМ целые числа представляются кодами в двоичной системе счисления, при чем 2k – 1 задается последовательностью из 1111111…11(k-раз)
Двоичное представление целых чисел дает возможность сгенерировать все подмножества универсума.
Алгоритм генерации всех подмножеств данного множества.
Вход: n – мощность множества
Выход: последовательность колов подмножеств
for i from 0 to 2n – 1 do
yield i
end
Алгоритм выдает 2n различных целых чисел, т.е. 2n различных двоичных кодов.
С увеличением числа n, увеличивается количество двоичных разрядов необходимых для представления этого числа.
Недостаток этого алгоритма заключается в том, что порядок генерации подмножеств никак не связан с их составом.
Такое состояние(положение) не всегда удобно при рассмотрении переборных задач, наиболее удобным является случай, когда очередное рассматриваемое подмножество не сильно отличается по набору элементов от предыдущего, потому что в этом случае возможно использование информации, полученной на предыдущем шаге. несильное отличие в рассматриваемых подмножествах позволяют ускорить процесс перебора вариантов решения.
10. Алгоритм построения бинарного кода Грея.
Алгоритм генерирует все подмножества n – элементного множества, при чем каждое следующее подмножество получается из предыдущего путем добавления или удаления одного элемента.
Вход: n – мощность множества
Выход: последовательность подмножеств
В:array [1..n] of 0..1
for i from 1 to n o
B[i]=0
end for
yield B
for i from 1 to 2n – 1 do
p=Q(i)
B[p]=1-B[p]
yield B
end for/
proc Q(i)
q:=1 i:=i
while j=четное do
j=j/2; q:=q+1
endwhile
return q
endproc.
Тестирование алгоритма
n=3
|
i |
P |
B |
|
|
|
|
|
1 |
1 |
001 |
|
2 |
2 |
011 |
|
3 |
1 |
010 |
|
4 |
3 |
110 |
|
5 |
1 |
111 |
|
6 |
2 |
101 |
|
7 |
1 |
100 |
11. Представление множеств упорядоченными списками.
Представление множеств в виде битовых шкал не является эффективным с точки зрения экономии памяти.
Во избежание трудностей множество удобно представлять в виде списков элементов.
Поэтому для представления множеств можно использовать списки элементов.
Список элементов задается записью с 2 полями: одно из которых является информационным, а второе – поле указателей.
elem = record
i:=info
n:=elem
|
info |
|
|
Петров |
|
|
Иванов |
|
|
|
|
|
nil |
|
Если элементы в списке упорядочены, то трудоемкость операций над множествами значительно снижается.
Эффект реализации операций над множествами, представленными упорядоченными списками, основан на алгоритме слияния.
Алгоритм слияния просматривает параллельно 2 множества. На каждом шаге продвижение происходит на том множестве, в котором элемент оказываются меньшими.