Лабораторная работа: Лабораторная работа №1 по дискретной математике

Распознанный текст из изображения:

2 .Определение всех подмножеств универсума

Содержание работы:

1.Разработка алгоритма решения задачи о нахождении всех подмножеств множества.

2,Разработка алгоритма построения бинарного кода Грея.

3.Разработка и отладка программы лля заданного множества.

Подмножество А универсума () представляется кодом (машинным словом или битовой шкалой)

а, в котором:

1, если ц(1) ц А,

О, если ц(1) ЯА,

а(1) =

Этот алгоритм программируется с использованием рекуррентных процедур.

Возможен другой подход. Этот алгоритм предлагает следующий вычислительный процесс:

1Создать два набора х и у, каждый из т нулей и единиц. Первоначально х=у = ( 0,....,0) .

2На каждой итерации прибавлять 1 к числу, для которого х является двоичным разложением.

ЗФиксировать позицию к, в которой нуль сменяется единицей.

4Изменить к-ю компоненту в наборе у: ук:=1-ук.5Выдать набор у как результат итерации

Множество, содержащее т элементов, имеет 2 "' подмножеств. Так как существует

взаимооднозначное соответствие между числами из 0: 2" -1 и наборами 0-1 векторов, нужно

взять число О и его представление 0,.....,0, а дальше прибавлять по единице, имитируя это на

текущем наборе, до тех пор, пока не получится набор 1,....,1. Переход от набора к номеру и

от номера к набору — это соответственно переход от двоичного представления числа к его

значению и от значения к двоичному представлению.

Например, множество А=( 1,2,3) содержит такие подмножества:

000 (0)

001 (3)

010 (2)

011 (2,3)

100 (1)

101 (1, 3)

110 (1,2)

111 (1,2,3)

Однако, при таком просмотре 0-1 наборов очередное прибавление единицы может вызвать

сильное изменение набора (например, 01011! -011000). Иногда желательно, чтобы

перебирались наборы, похожие друг на друга; например, в случае 0-1 наборов можно

потребовать, чтобы на каждом шаге менялось значение только одной компоненты.

Существующий алгоритм бинарного кода Грея приведен в (1).

Принципиальная схема такого перебора основана на идее рекурсии. Чтобы перебрать все

наборы длины ш, зафиксируем нулевое значение у т-й компоненты и переберем все наборы

длины ш-1 для оставшихся компонент. Перебрав их, сменим значение ш-й компоненты на 1

(на этом шаге, номер которого 2"" меняется именно эта единственная компонента) и снова

переберем наборы длины т-1, но уже в обратном порядке. В таблице приведен перебор для

б 4 1с б

Распознанный текст из изображения:

Лабораторная работа Х 1

Нахождение множеств по операциям

1. Операции над множествами

Содержание работы.'

1.Разработка программы для выполнения операций над множествами.

2.Разработка н отладка программы для нахождения заданного множества.

Освоение операций над множествами

обьединение:

А О В;= [х) х н Аь' хе В);

пересечение;

А("~В:=[х~хе АесхеВ)

разность;

А) В:= [ х) хе Айх 1 В )

симметрическая разность:

АА В:=[ [А ~ ~ В)) (А Г3 В) );

дополнение:

А:= [ х~х)6А)

Пример:

1. Дано: Универсум 1)= 1,2,3,4,5,6,7,8,9,10

А= 1,3,5,7

В= 5,б,7,8,10

С= 1,2,7,9

Найти: Множество С1= А А ВГ3 С;

С2= Аг3 В~ ~С;

СЗ=А~ )ВАС;

С4 =А1В~ >С1.

С5=Аг3 В Сб=А~.гВ С7=А~ ~В С8=Аг) В

Содержание отчета:

1. Текст программы на С- -ь или Паскале,

2. Результаты выполнения программы для различных значений исходных данных,

Пример:

ргоогат взпо3есчо;

сопвп п=1;

час а,Ь,с,с1,е: еес об 1..200; ),х,у;Ьупе;

Ьейзп а:=[1р Ь:=[3,5,8); с)с=[1,3,6); е:=[1,3,8) р

бог 3:=1 Со 5 с)о

Ьеятп

геас)1п[х) з

а:=а+[х)

епс);

с: =а-Ь-с)-е;

аког х:=1 Со 200 с)о

18[х тп с)

ЬЬеп

иг1се1п[х);

геа61п;

епс) .