Доведення теоретико-математичних тотожностей і тверджень (стр. 3 из 5)
інакше: записати в кінці масива С елементи А, які залишились нерозглянуті; кінець.
Крок 6.
,к=к+1; с 
= 
,і=і+1, J=j+1 ;Крок 7. Провірити умову: 
оr 
(Чи існують іще нерозглянуті елементи множини А чи В);якщо так, то перехід на крок 2. Інакше : якщо і>n і j<m, то записати в кінці масиву С елементи В, які не були розглянені; кінець.якщо і <nij >m, то записати в кінці масиву С елементи А , які залишились ерозглянуті.Kiнець
2.5.2.4. Блок-схема.
Мал.3. Блок-схема процедури OBED
2.5.3. Опис процедури PERET
2.5.3.1. Постановка задачі.
Задані дві множини: A={а
,а 
,..,а 
}В={b
,b ,..,b }, які упорядковані.Потрібно отримати множину С=А ÇB
2.5.3.2. Математична модель
Перетин визначається наступним чином С=А ÇВ={С,С
А і С В}2.5.3.4. Алгоритмвирішеннязадачі
Алгоритм вирішення задачі базується на методі злиття двох множин, тому ми можемо допустити, не порушуючи загальності, що множини А і В вже відсортували. Задається у відсортованому вигляді. Приведемо загальний опис вирішення алгоритму задачі.
На кожному кроці основного циклу можлива одна з трьох ситуацій: поточний елемент множини А менше, чи більше, чи дорівнює поточному елементу множини В.
· у першому випадку поточний елемент множини А не належить перетинанню, він пропускається і відбувається просування в цій множині;
· у другому випадку теж саме виконується з множиною ;
· у третьому випадку знайдені співпадаючі елементи, один екземпляр елементу додається в результат і відбувається просування відразу в обох множинах.
Алгоритм перетину:
Призначений для перетину двох відсортованих множин А і В з використанням методу злиття.
Крок 0. Ініціалізація: задання множин А і В:
А={а
}, 
;В={b
}, 
;Присвоїти 
, j=1
Крок 1. Перевірити
. Якщо так, то: і=і+1. Перехід на Крок4.Крок 3. Перевірити
,якщо так, то: j=j+1. Перехід на Крок 4.Крок 4. Виконати Крок2 і Крок3 при (
)оr( ) .Крок 5. Кінець.
Блок-схема.
Мал.3. Блок-схема процедури PERET
2.5.4. Опис процедури RIZ.
2.5.4.1. Постановка задачі
Задані дві множини A={а
,а 
,..,а } і В={b ,b ,..,b }, які упорядковані.Потрібно отримати множину С=А \B.
2.5.4.2. Математична модель
Різниця визначається наступним чином С=А \В={с,сÎА і сÏВ}
2.5.4.3. Алгоритмвирішення задачі
Алгоритм вирішення задачі базується на методі злиття двох множин, тому ми можемо допустити не порушуючи загальності, що множини А і В вже відсортували. Приведемо загальний опис вирішення алгоритму задачі.
На кожному кроці основного циклу можлива одна з трьох ситуацій: поточний елемент множини А менше, чи більше, чи дорівнює поточному елементу множини В.
· у першому випадку поточний елемент множини А записується в результат С і розглядається наступний елемент множини А;
· у другому випадку поточний елемент множини А не належить різниці і розглядається наступний елемент множини В;
· у третьому випадку поточний елемент А не належить результату і розглядаються наступні елементи множин А і В.
Після закінчення основного циклу ті елементи множини А, які не були розглянуті, записуються в кінець списку С без перевірки.
АЛГОРИТМ RIZ. Призначений для знаходження різниці двох відсортованих множин А і В з використанням методу злиття.
Крок 0. Задання множин А і В: А={а
}, 
;В={b }, ;Присвоїти , 
,
.Крок 1. Перевірити
. Якщо так, то: 
, 
, 
. Перехід на Крок3.Крок 2. Перевірити
. Якщо так, то: , 
, перехід на Крок 3. Інакше: .Крок3. Виконати Крок1 і Крок2 поки (
)оr( ) .Крок 4. Визначити: якщо залишились нерозглянуті елементи множини А, то записати їх без перевірки в кінець списку С.
Крок 5. Кінець.
Приведемо загальний опис вирішення задачі.
 |
 |
3
 | ||
 |
 |
Мал.3. Блок-схема процедури RIZ
2.6. Результат
Текст програми:
Programproga;
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('}');