28_tétel

Metszet

(Algoritmus, használati lehetőségek, példák a használatra)

A metszetképzés tétele
       Közös jellemzők: Két halmaz közös részét keressük. A halmazok
elemeit valamilyen sorozatban helyezzük el. Az első halmaz elemeit
egyenként végigkeressük a másodikban. Találat esetén az elemet egy harmadik
sorozatba másoljuk.

Írj programot, mely két adott számsorozatot vizsgálva megkeresi a
mindkettőben          megtalálható számokat!
|Feladatvizsgálat:                                                       |
|1. Bemenő adatok:                                                       |
|adb, bdb: a két adott tömb elemszáma, byte típusúak.                    |
|a, b: a két adott tömb, itt integer típusú elemeket tartalmaznak.       |
|2. Kimenő adatok:                                                       |
|cdb: az új tömb elemszáma, byte típusú.                                 |
|c: a kapott metszettömb, elemeinek típusa megegyezik a bemenő tömbelemek|
|típusával.                                                              |
|3. Matematikai eszközök: halmazok metszete.                             |
|4. Belső változók:                                                      |
|i, j: futóváltozók a két bemenő tömbben, byte típusú.                   |
|5. A program logikája: a bemenő tömböknél feltételeztük, hogy elemeik   |
|különbözőek, így halmazként is felfoghatók. Az első halmaz elemeit végig|
|keressük a második tömbben. Ha egy elemet ott is megtalálunk, akkor     |
|bemásolju az új tömb soron következő elemébe.                           |
|Folyamatábra:                                                           |
|[pic]                                                                   |
|Program:                                                                |
|                                                                        |
|procedure metszet_10(adb,bdb:byte; a,b:tomb; var cdb:byte; var c:tomb); |
|                                                                        |
|var i,j:byte;                                                           |
|begin                                                                   |
|    {Feltételezzük, hogy a tömbökön belül a számok nem ismétlődnek, így |
|                                                                        |
|      halmazként is felfoghatók. Két halmaz közös részét másoljuk az új |
|tömbbe.}                                                                |
|  cdb:=0;                                                               |
|  for i:=1 to adb do                                                    |
|  begin                                                                 |
|    j:=1;                                                               |
|    while (j<=bdb) and (a[i]<>b[j]) do inc(j);                          |
|    if (j<=bdb) then begin inc(cdb); c[cdb]:=a[i]; end;                 |
|  end;                                                                  |
|end;                                                                    |
|                                                                        |

Példa: Adott két számsorozat X: 12, 34, 2, 5, 16, 8 és Y: 2, 34, 7, 3, 5.
Gyűjtsük ki a sorozatok közös elemeit Z-be! A közöselemek keresését úgy
végezzük el, hogy rendre egymás után vesszük mondjuk az X sorozat elemeit
és megnézzük, hogy az Y sorozatban megtalálhatók-e. Amennyiben Y-nak is
eleme, akkor behelyezzük Z-be. A feladat megoldása során Z elemszámát X
illetve Y sorozat elemszámainak minimumának kell megválasztanunk. Hiszen ha
a legkisebb elemszámú sorozat minden elemét megtaláltuk a másik sorozatban
- részhalmaz -, akkor több közös elem már nem lehet. Ha a sorozatok
metszők, akkor még kevesebb, ha diszjunktak, akkor egyáltalán nem lesz
eleme a Z sorozatnak.
Legyen: I az X sorozat indexe, J az Y sorozat indexe, K a Z sorozat indexe.

Megjegyzés: A feladat általános megoldásakor a sorozatok elemeinek típusát
nem ismerjük, ezért az X, Y, Z sorozatok deklarálásakor a példában
bemutatott egész típus helyet általános elemtíoust kell választanunk.
|  |Leíró nyelven megfogalmazva      |Pascal nyelven megfogalmazva     |
|[p|Algoritmus                       |Program Metszet;                 |
|ic| Konstans                        |Const                            |
|] |  X:tömb[1..6]                   |  X:array[1..6]of byte=          |
|  |egész=(12,34,2,5,16,8)           |    (12,34,2,5,16,8);            |
|  |  Y:tömb[1..5]   egész=(2,34,7,3,|  Y:array[1..6]of byte=          |
|  |5)                               |    (2,34,7,3,5);                |
|  | Változó                         |Var                              |
|  |       Z:tömb[1..5]   egész      | Z:array[1..6] of byte;          |
|  |       I, J, K : egész           | I, J, K : byte;                 |
|[p|  K:=0                           |Begin                            |
|ic|  {Az Y tömb elemei vesszük      | K:=0                            |
|] |sorra}                           | J:=1;                           |
|  |  J:=1                           | While J<=5 do                   |
|  |  Ismételd mialatt J<=5          | Begin                           |
|  |    {Megnézzük, hogy van-e X-ben |   I:=1;                         |
|  |ilyen elem}                      |   While (J<=6) And (Y[J]<>X[I]) |
|  |     I:=1                        |do                               |
|  |     Ismételd mialatt            |      I:=I+1;                    |
|  |(I<=6)És(Y[J]<>X[I])             |   If  I<=6Then                  |
|  |        I :=I+1                  |   Begin                         |
|  |     Ismétlés vége               |       K:=K+1;                   |
|  |     {Ha van az elemet Z-be      |       Z[K]:=Y[J];               |
|  |tesszük}                         |   End;                          |
|  |     Ha I<=6 akkor               |   J:=J+1;                       |
|  |          K:=:K+1                | End;                            |
|  |          Z[K]:=Y[J]             |End.                             |
|  |     Elágazás vége               |                                 |
|  |     J:=J+1                      |                                 |
|  |   Ismétlés vége                 |                                 |
|  | Ismétlés vége                   |                                 |
|  |Algoritmus vége                  |                                 |