Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Реализация операций над подмножествами заданного универсума.
êUú < n U = {U1, U2, U3,…} Число элементов в универсуме не превосходит разрешающимися сети компьютера.
Подмножество А универсума U представляется двоичным кодом(машинным кодом, битовой шкалой) Ci= 1, UiÎA 0, UiÏA Пересечение А и В являются поразрядным логическим произведением кодом множеств А и В. Код объединений множеств А и В является поразрядной логической суммой кодов множеств А и В. Код дополнения множества А является инверсией кода множества А. Генерация всех подмножеств универсума. Алгоритм генерации всех подмножеств данного множества. Генерация всех подмножеств универсумов В алгоритмах часто бывает необходимо рассмотреть все подмножества заданного множества. В памяти ЭВМ целые числа представляются кодами в двоичной системе счисления, при чем 2k – 1 задается последовательностью из 1111111…11(k-раз) Двоичное представление целых чисел дает возможность сгенерировать все подмножества универсума. Алгоритм генерации всех подмножеств данного множества. Вход: n – мощность множества Выход: последовательность колов подмножеств for i from 0 to 2n – 1 do yield i end Алгоритм выдает 2n различных целых чисел, т.е. 2n различных двоичных кодов. С увеличением числа n, увеличивается количество двоичных разрядов необходимых для представления этого числа. Недостаток этого алгоритма заключается в том, что порядок генерации подмножеств никак не связан с их составом. Такое состояние(положение) не всегда удобно при рассмотрении переборных задач, наиболее удобным является случай, когда очередное рассматриваемое подмножество не сильно отличается по набору элементов от предыдущего, потому что в этом случае возможно использование информации, полученной на предыдущем шаге. несильное отличие в рассматриваемых подмножествах позволяют ускорить процесс перебора вариантов решения. Алгоритм построения бинарного кода Грея. Алгоритм генерирует все подмножества 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
Представление множеств упорядоченными списками. Представление множеств в виде битовых шкал не является эффективным с точки зрения экономии памяти. Во избежание трудностей множество удобно представлять в виде списков элементов. Поэтому для представления множеств можно использовать списки элементов. Список элементов задается записью с 2 полями: одно из которых является информационным, а второе – поле указателей. elem = record i:=info n:=elem
Если элементы в списке упорядочены, то трудоемкость операций над множествами значительно снижается. Эффект реализации операций над множествами, представленными упорядоченными списками, основан на алгоритме слияния. Алгоритм слияния просматривает параллельно 2 множества. На каждом шаге продвижение происходит на том множестве, в котором элемент оказываются меньшими. Алгоритм проверки включения. Вход: А и В – представлены упорядоченные списки Выход: 1, если АÌВ, иначе 0.
while pa¹nil and pb¹nil do if pa.i<pb.i then return 0 else if pa.i>pb.i then pb:=pb.n else pa:=pa.n pb:=pb.n endif endwhile return pa=nil. //pa.i=элемент списка pa.n=ссылка
|
||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-02-21; просмотров: 338; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.236.139.73 (0.002 с.) |