Adatbázis és szoftverfejlesztés gyakorlat - KÖZÉPSZINTŰ KÖVETELMÉNYEK - Programozási nyelv „A”
3. TÖBB SOROZATHOZ EGY SOROZATOT RENDELŐ TÉTELEK
3.1 Metszetképzés tétele
3.1.1 Kitűzés
Adott két sorozat, a sorozatokon belül egy-egy elem csak egyszer szerepel.
Feladat: Határozzuk meg azt a sorozatot, amely a két sorozat közös elemeit tartalmazza.
3.1.2 Specifikáció
A,B:Tömb[1..Max]:H
N,M:egész / A és B elemszáma
C:Tömb[1..Max]:H
L: egész / C elemszáma
Ef.: A,B adott, elemeik egyediek; 0<=N<=Max , 0<=M<=Max
Uf: C tartalmazza A és B közös elemeit, 0<=L<=Min(A,B) /a metszet legfeljebb annyi elemet tartalmaz, mint a kisebb elemszámú sorozat/
3.1.3 Algoritmus
Elve: minden A-beli elemet keresünk a B tömbben. Ha egy A-beli megtalálható a B-ben, akkor felvesszük a közös elemek közé, a C-be.
Eljárás Metszet:
L:=0;
Ciklus I:=1-től N-ig
J:=1; / A[I] keresése B-ben
Ciklus amíg J<=M és A[I]<>B[J]
J:=J+1
Ciklus vége
Ha J<=M / Ha A[I] megtalálható B-ben
akkor
L:=L+1
C[L]:=A[I]
Elágazás vége
Ciklus vége
Eljárás vége
3.2 Unióképzés tétele
3.2.1 Kitűzés
Adott két sorozat, a sorozatokon belül egy-egy elem csak egyszer szerepel.
Feladat: Határozzuk meg azt a sorozatot, amely minden olyan elemet tartalmaz, amely legalább az egyiknek eleme.
3.2.2 Specifikáció
A,B:Tömb[1..Max]:H
N,M:egész / A és B elemszáma
C:Tömb[1..2*Max]:H
L: egész / C elemszáma
Ef.: A, B adott; elemeik egyediek; 0<=N<=Max , 0<=M<=Max
Uf: C tartalmazza az A és B sorozatok unióját, Max(A,B)<=L<=M+N
Megjegyzés: a kimenő sorozat elemszáma legrosszabb esetben 2*Max, ez akkor áll elő, ha A és B is Max elemet tartalmaz, és nincsen közös elemük.
3.2.3 Algoritmus
Elve: először A összes elemét átmásoljuk C-be. Majd B elemeit sorra vesszük, és mindazokat, amelyek nem szerepelnek az A tömbben, szintén C-be másoljuk.
Eljárás Unió:
Ciklus I:=1-től N-ig / A elemeinek másolása C-be
C[I]:=A[I]
Ciklus vége
L:=N
Ciklus J:=1-től M-ig
I:=1 / B[J] keresése A-ban
Ciklus I<=N és B[J]<>A[I]
I:=I+1
Ciklus vége
Ha (I>N) / Ha B[J] nem szerepel A-ban
akkor
L:=L+1
C[L]:=B[J]
Elágazás vége
Ciklus vége
Eljárás vége
