Властивості операції над множинами

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 4Следующая ⇒

Назва властивості	Варіант №1	Варіант №2
Іденпотентність
Комутативність
Асоціативність
Дистрибутивність
Поглинання
Властивість нуля
Властивість одиниці
Інволюнтивність
Закон де Моргана
Властивість доповнення
Властивість для різності

Завдання 2.1

Розробити алгоритм та написати програму обчислення множини:

Проектування рішення задачі

Проект рішення задачі представляється в формі принципової блок-схеми.

	Обчислення: Вхід: А Вихід: М1
	Обчислення: = M4 Вхід: M1, M3 Вихід: M4

Мал.1.Принципова блок-схема обчислення множин

Примітка: При розробці алгоритму даної задачі ми вводимо множини А, В,  D вже в упорядкованому вигляді, але ми нижче приводимо опис методу впорядкування множин методом простого включення.

Організація структури прграми

Для обчислення операцій  використовують метод, який базується на методі злиття. Він пропонує, що вихідні множини повинні бути відсортованими. Тому в програмі для сортування вихідних масивів будемо користуватись процедурою SYS (сортування методом простого виключення).

Представимо структуру програми у вигляді наступної блок-схеми (для програми обрано модульний принцип організації програми):

	Ввід А,В (невідсортовані)
	Процедура RIZ

Мал.2.Принципова блок-схема програми

У програмі вирішення даної задачі ми використовуємо наступні процедури:

1. SYS- призначена для сортування цілих додаткових чисел;

2. ОBED- призначена для організації виконання операцій об’єднання двох відсортуваних множин;

3. PERET- призначена для організації виконання операцій перетину двох відсортуваних множин;

4. RIZ- призначена для організації виконання операцій різниці двох відсортуваних множин.

Опис процедур

Опис процедури SYS.

Постановка задачі.

Задана послідовність чисел A = {a_і, а₂, а₃, …,а_n }.

Необхідно упорядкувати її елементи по зростанню, тобто створити послідовність чисел В={ }, такий, щоб , .

 Задачу вирішимо методом простого виключення.

Математична модель

Як математичну модель представимо логічну схему роботи методом простого включення. Описуємо суть методу.

Побудуємо таблицю з 3 стовбців:

1-й стовбець предначений для вказування ітерацій методу.

2-й —для несортованої послідовності (А).

3-й —для відсортованої послідовності (В).

На першому кроці ітерацій 1-й елемент з А вставляється в В, потім цей елемент видаляється з А. Далі на кожному кроці ітерацій 1-й елемент з поточної невідсортованої послідовності А вставляється в відповідне йому місце відсортованої послідовності В; потім він удаляєть з послідовності А. Покажемо роботу методу простого виключення на прикладі:

А= .

Алгоритм рішення задачі.

Алгоритм процедури SYS.

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

Вхід: А- масив невідсортуваних даних;

n- кількість елементів масиву.

Вихід: В- масив відсортуваних даних. 

 Трудоємність алгоритма .

Крок 1: Визначити перші два елемента масива В.

Крок 2: Організувати цикл по , .

Крок 3: Провірити умови  Якщо умова виконується, то .

Перехід на крок 6.

Крок 4: Організувати цикл по , де  (для індексації решти елементів масива В).

Крок 5: Провірити умови . Якщо вона виконується, то елементи масива В зміщуються на один розряд вправо з  до . Присвоїти .

Крок 6: Завершення циклу по .

Крок 7: Кінець.

Блок-схема.

                  так

                                                             ні

                        так

Мал.3. Блок-схема процедури SYS.

Опис процедури OBED.

Постановка задачі.

Задані дві множини A={а ,а ,..,а }, В={b ,b ,..,b }.

Потрібно отримати множину С=А В.

Математична модель

Об’єднання визначається наступним чином .

Алгоритм рішення задачі.

Алгоритм вирішення задачі базується на методі злиття двох множин. Приведемо загальний опис вирішення алгоритму задачі.

1

2      

3      

4      

Блок 1:використовуємо Procedure SYS,яка описана в лабораторній pоботі №1.

Блок 2,3: не відсортовані масиви; відсортовані масиви.

Блок 4: алгоритм OBED

Алгоритм OBED:

Призначений для об ’ єднання двох відсортованих множин А і В з використанням методу злиття.

Крок 1. Присвоїти , j=1, ;

Крок 2. Перевірити умову : якщо так, то: к=к+1,с =  ,і=і+1;

Крок 3. Перевірити умову ; якщо так, то перехід на крок 2;

інакше: записати в кінці масиву С елементи масиву В,

які залишились нерозглянуті; кінець.

Якщо  ,то перехід на крок 4;

Крок 4. Перевірити ;якщо так, то: к=к+1, с =b ,j=j+1

Крок 5. Перевірити умову j ; якщо так, то перехід на крок 2;

інакше: записати в кінці масива С елементи А, які залишились нерозглянуті; кінець.

Крок 6. ,к=к+1; с = ,і=і+1, J=j+1;

Крок 7. Провірити умову: о r  ( Чи існують іще нерозглянуті елементи множини А чи В);якщо так, то перехід на крок 2. Інакше: якщо і>n і j<m, то записати в кінці масиву С елементи В, які не були розглянені; кінець. якщо і <n i j >m, то записати в кінці масиву С елементи А, які залишились ерозглянуті. Ki нець

Блок-схема.

Мал.3. Блок-схема процедури OBED

Опис процедури PERET

Постановка задачі.

Задані дві множини: A={а ,а ,..,а }

В={b ,b ,..,b }, які упорядковані.

Потрібно отримати множину С=А ÇB

Математична модель

Перетин визначається наступним чином  С=А ÇВ={С,С А і С В}

Алгоритм вирішення задачі

Алгоритм вирішення задачі базується на методі злиття двох множин, тому ми можемо допустити, не порушуючи загальності, що множини А і В вже відсортували. Задається у відсортованому вигляді. Приведемо загальний опис вирішення алгоритму задачі.

На кожному кроці основного циклу можлива одна з трьох ситуацій: поточний елемент множини А менше, чи більше, чи дорівнює поточному елементу множини В.

· у першому випадку поточний елемент множини А не належить перетинанню, він пропускається і відбувається просування в цій множині;

· у другому випадку теж саме виконується з множиною;

· у третьому випадку знайдені співпадаючі елементи, один екземпляр елементу додається в результат і відбувається просування відразу в обох множинах.

Алгоритм перетину:

Призначений для перетину двох відсортованих множин А і В з використанням методу злиття.

Крок 0. Ініціалізація: задання множин А і В:

А={а }, ;

В={b }, ;

Присвоїти , j =1

Крок 1. Перевірити . Якщо так, то: і=і+1. Перехід на Крок4.

Крок 3. Перевірити ,якщо так, то: j=j+1. Перехід на Крок 4.

Крок 4. Виконати Крок2 і Крок3 при (  )оr (  ).

Крок 5. Кінець.

Блок-схема.

Мал.3. Блок-схема процедури PERET

Опис процедури RIZ.

Постановка задачі

Задані дві множини A={а ,а ,..,а } і В={b ,b ,..,b }, які упорядковані.

Потрібно отримати множину С=А \B.

Математична модель

Різниця визначається наступним чином  С=А \В={с, сÎА і сÏВ}

Алгоритм вирішення задачі

Алгоритм вирішення задачі базується на методі злиття двох множин, тому ми можемо допустити не порушуючи загальності, що множини А і В вже відсортували. Приведемо загальний опис вирішення алгоритму задачі.

На кожному кроці основного циклу можлива одна з трьох ситуацій: поточний елемент множини А менше, чи більше, чи дорівнює поточному елементу множини В.

· у першому випадку поточний елемент множини А записується в результат С і розглядається наступний елемент множини А;

· у другому випадку поточний елемент множини А не належить різниці і розглядається наступний елемент множини В;

· у третьому випадку поточний елемент А не належить результату і розглядаються наступні елементи множин А і В.

Після закінчення основного циклу ті елементи множини А, які не були розглянуті, записуються в кінець списку С без перевірки.

АЛГОРИТМ RIZ. Призначений для знаходження різниці двох відсортованих множин А і В з використанням методу злиття.

Крок 0. Задання множин А і В: А={а }, ;В={b }, ;

Присвоїти , , .

Крок 1. Перевірити . Якщо так, то: , , . Перехід на Крок3.

Крок 2. Перевірити . Якщо так, то: , , перехід на Крок 3. Інакше: .

Крок 3. Виконати Крок1 і Крок2 поки (  )оr (  ).

Крок 4. Визначити: якщо залишились нерозглянуті елементи множини А, то записати їх без перевірки в кінець списку С.

Крок 5. Кінець.

Приведемо загальний опис вирішення задачі.

	Ввід А = , B = А,В – невідсортовані множини

1

Виклик SYS (а, А, n) Вихід А- відсортовані

2

3

	Виклик RIZNICA(A,B,m,n,D)           SYS (B). Вихід D = A\B

4

	5

SYS – procedure для відсортування масиву

RIZNICA- procedure для обчислення С = А \ В

Блок-схема

Мал.3. Блок-схема процедури RIZ

2.6. Результат

Текст програми:

Program proga;

type ar=array [1..50] of integer;

Var A,B,C,D,BK1,BK2,Bk3,Bk4,Bk5,Bk6,M,U:ar;

i,j,k,nk1,nk2,nk3,nk4,nk5,nk6,nm,na,nb,nc,nd:integer;

Procedure OBED(Var pa:ar;Var pb:ar;Var pc:ar;Var pn1, pn2,pk:integer);{вхід:A,B; вихід C}{програма для об’єднання множин}

var

i,j,k,l:integer;

begin

i:=1;j:=1;k:=0;

repeat

if pA[i]<pB[j] then

begin k:=k+1;pC[k]:=pA[i];i:=i+1; end;

if pA[i]>pB[j] then

begin k:=k+1;pC[k]:=pb[j];j:=j+1; end;

if pA[i]=pB[j] then

begin k:=k+1;pC[k]:=pA[i];i:=i+1;j:=j+1; end;

until (i>pn1) or (j>pn2);

if (i>pn1)and(j<pn2) then

for l:=j to pn2 do

begin k:=k+1; pC[k]:=pB[l];end;

if (i<pn1) and (j>pn2)then

for L:=i to pn1 do

begin k:=k+1;pC[k]:=pA[l];end;

write(' A={'); for i:=1 to pn1 do write(pa[i]:3); writeln('}');

write(' B={'); for i:=1 to pn2 do write(pB[i]:3); writeln('}');

write(' C={'); for i:=1 to k do write(pC[i]:3); write('}');

pk:=k;

readln;

end;

Procedure RIZ(Var pa:ar;Var pb:ar;Var pc:ar;Var pn1, pn2,pk:integer); {вхід:A,B; вихід C}{програма для обчислення різниці множин}

{const n=5;m=6;}

var

i,j,k,l:integer;

begin

i:=1;j:=1; k:=0;

repeat

if pa[i]<pb[j] then begin k:=k+1; pC[K]:=pa[i]; i:=i+1; end

else begin if pa[i]=pb[j] then

begin i:=i+1; j:=j+1; end

else j:=j+1; end;

until (i>pn1)or(j>pn2);

if (i<pn1)and(j>pn2) then

begin for l:=i to pn1 do

begin k:=k+1; pc[k]:=pa[l]; end;

end;

if k=0 then

begin

write(' A={'); for i:=1 to pn1 do write(pa[i]:3); writeln('}');

write(' B={'); for i:=1 to pn2 do write(pb[i]:3); writeln('}');

write(' C={'); for i:=1 to k do write(pc[i]:3); writeln('}');

end

else

begin

write(' A={'); for i:=1 to pn1 do write(pa[i]:3); writeln('}');

write(' B={'); for i:=1 to pn2 do write(pb[i]:3); writeln('}');

write(' C={'); for i:=1 to k do write(pc[i]:3); writeln('}');

end;

pk:=k;

readln;

readln;

end; Procedure PERET(Var pa:ar;Var pb:ar;Var pc:ar;Var pn1, pn2,pk:integer); {вхід:A,B; вихід C}{програма для перетину множин}

{const n=10; m=7;}

var

i,j,k,l:integer;

begin

i:=1;j:=1;k:=0;

repeat

if pA[i]<pB[j] then i:=i+1;

if pA[i]>pB[j] then j:=j+1;

if pA[i]=pB[j] then

begin k:=k+1; pC[k]:=pA[i]; i:=i+1;j:=j+1;end;

until (i>pn1) or (j>pn2);

if k = 0 then

begin

write(' A={'); for i:=1 to pn1 do write(pa[i]:3); writeln('}');

write(' B={'); for i:=1 to pn2 do write(pB[i]:3); writeln('}');

write(' C={'); for i:=1 to k do write(pC[i]:3); write('}');

end

else

begin

write(' A={'); for i:=1 to pn1 do write(pa[i]:3); writeln('}');

write(' B={'); for i:=1 to pn2 do write(pB[i]:3); writeln('}');

write(' C={'); for i:=1 to k do write(pC[i]:3); write('}');

end;

writeln;

pk:=k;

readln;

end;

Begin {тіло програми}

k:=15;

For i:=1 to k do U[i]:=i;

Write ('Задайте множину A та ii границю');

write(' na=');REadln (na);

For i:=1 to na do begin write ('A[',i,']= '); Readln(a[i]); end;

Write ('Задайте множину В та ii границю');

write(' nb='); Readln (nb);

For i:=1 to nb do begin write ('B[',i,']= '); Readln(b[i]); end;

Write ('Задайте множину С та ii границю');

write(' nc='); Readln (nc);

For i:=1 to nc do begin write ('C[',i,']= '); Readln(C[i]); end;

Write ('Задайте множину D та ii границю');

write(' nd='); Readln (nd);

For i:=1 to nd do begin write ('D[',i,']= '); Readln(D[i]); end;

peret(A,B,bk1,na,nb,nk1);

riz(U,bk1,bk2,k,nk1,nk2);

riz(U,C,bk3,k,nc,nk3);

riz(U,D,bk4,k,nD,nk4);

peret(bk3,bk4,bk5,nk3,nk4,nk5);

riz(U,bk5,bk6,k,nk5,nk6);

obed(bk2,bk6,M,nk2,nk6,nm);

end.

Результати:

Вхідні данні:

A={2,3,5,8}, na=4

B={1,2,5,11}, nb=4

C={12,14,15}, nc=3

D={3,9,10,11,12}, nd=5

Отримані данні:

М₁₌ {2,5}

М₂₌ {1,3,4,6,7,8,9,10,11,12,13,14,15}

М₃₌ {1,2,3,4,5,6,7,8,9,10,11,13}

М₄₌{1,2,4,5,6,7,8,13,14,15}

М₅₌ {1,2,4,5,6,7,8,13}

М₆₌{3,9,10,11,12,14,15}

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров