Algoritmusok kezdőknek – 5. rész

Több sorozathoz egy sorozat hozzárendelése:

 

1. Metszetképzés:

 

A és B halmaz (tömb) közös része.

Az A és a B tömbben nem lehet ismétlődő elem. Ha már volt a B-ben az elem, akkor ne keressen. Ha 2 vagy több azonos elem van az A-ban és a B-ben, akkor a C-ben is 2 vagy több azonos elem van.

 

A[1..N]

                                    C[1..min(N,M)](maximum)

B[1..M]

 

CDB:=0

CIKLUS I:=1-től N-ig

  CIKLUS J:=1-től M-ig

    HA A[I]=B[J] AKKOR

      CDB:=CDB+1

      C[CDB]:=A[I]

    HAVÉGE

  CVÉGE

CVÉGE

 

2. Unióképzés:

 

A és B halmaz (tömb) összege.

Azonos elemek csak egyszer kerülnek be a C halmazba.

 

A[1..N]

                                    C[1..N+M](maximum)

B[1..M]

 

CIKLUS I:=1-től N-ig

  C[I]:=A[I]

CVÉGE

CDB:=N

--- Innentől különbségképzés:

CIKLUS J:=1-től M-ig

  TALALAT:=Hamis

  CIKLUS I:=1-től N-ig

    HA B[J]=A[I] AKKOR

      TALALAT:=Igaz

    HAVÉGE

  CVÉGE

  HA NOT TALALAT AKKOR

    CDB:=CDB+1

    C[CDB]:=B[J]

  HAVÉGE

CVÉGE

 

3. Különbségképzés:

 

A-B halmaz (tömb).

 

A[1..N]

                                    C[1..N](maximum) – mivel A-B

B[1..M]

 

 

CDB:=0

CIKLUS I:=1-től N-ig

  TALALAT:=Hamis

  CIKLUS J:=1-től M-ig

    HA A[I]=B[J] AKKOR

      TALALAT:=Igaz

    HAVÉGE

  CVÉGE

--- Eddig eldöntés tétele.

  HA NOT TALALAT AKKOR

    CDB:=CDB+1

    C[CDB]:= A[I]

  HAVÉGE

CVÉGE

 

4. Összefuttatás tétele I.:

 

Minden elemet át kell tenni növekvő sorrendben (feltétel: az A és a B tömb rendezett legyen).

 

A[1..N]

                                    C[1..N+M](mindig)

B[1..M]

 

CDB:=0

I:=1

J:=1

CIKLUS amíg (I<=N) AND (J<=M)

  CDB:=CDB+1

  ELÁGAZÁS

    HA A[I]<B[J] AKKOR

      C[CDB]:=A[I]

      I:=I+1

    HA A[I]>B[J] AKKOR

      C[CDB]:=B[J]

      J:=J+1

    KÜLÖNBEN (vagyis A[I]=B[J])

      C[CDB]:=A[I]

      I:=I+1

      CDB:=CDB+1

      C[CDB]:=B[J]

      J:=J+1

    ELÁGAZÁS VÉGE

CVÉGE

CIKLUS amíg I<=N (Ha az A tömbben vannak még elemek)

  CDB:=CDB+1

  C[CDB]:=A[I]

  I:=I+1

CVÉGE

CIKLUS amíg J<=M (Ha a B tömbben vannak még elemek)

  CDB:=CDB+1

  C[CDB]:=B[I]

  J:=J+1

CVÉGE

 

5. Összefuttatás tétele II.:

 

Minden elemet át kell tenni növekvő sorrendben (feltétel, hogy az A és a B tömb rendezett legyen). Beírja a +”végtelent” (mert a +végtelen nem lehet kisebb a másik tömb egyik eleménél sem – a ciklus azon a ponton marad), így nem kell a maradékokat bemásolnia. De az N+1-dik elem legyen „végtelen”.

 

A[1..N+1]

                                    C[1..N+M+1](mindig)

B[1..M+1]

 

A[N+1]:=65535 (Mivel a számítástechnikában nincs végtelen, minél nagyobb számot válasszunk)

B[M+1]:=65535

CDB:=0

I:=1

J:=1

CIKLUS amíg (I<=N+1) VAGY (J<=M+1)

  HA A[I]<=B[J] AKKOR

    CDB:=CDB+1

    C[CDB]:=A[I]

    I:=I+1

  HAVÉGE

  HA A[I]>=B[J] AKKOR

    CDB:=CDB+1

    C[CDB]:=B[J]

    J:=J+1

  HAVÉGE

CVÉGE

 

Szűcs Tamás - szucs_t@freestart.hu