Pascal kihívás: Két tömb összefűzése és a duplikátumok elegáns törlése

A programozás világában az adatszerkezetek kezelése alapvető képesség, és a tömbök az egyik leggyakrabban használt gyűjteménytípusok. Gyakran előfordul, hogy több forrásból származó adatokat kell egyesítenünk, majd biztosítanunk, hogy az eredményben minden elem egyedi legyen. Bár a modern programnyelvek beépített funkciókkal teszik ezt triviálissá, egy olyan klasszikus környezetben, mint a Pascal, ez a feladat igazi kihívást jelenthet, amely próbára teszi az algoritmikus gondolkodásunkat és a programozási alapjainkat. Ez a cikk a „Pascal Kihívás” keretében járja körül, hogyan fűzhetünk össze két tömböt, és hogyan távolíthatjuk el belőlük a duplikátumokat a lehető legelegánsabban.

Miért éppen Pascal? 🤔

Sokan felvethetik a kérdést: miért foglalkozzunk egy „régi” nyelvvel, mint a Pascal, amikor a Python vagy a JavaScript mindezt egy sorban megoldja? A válasz egyszerű és mélyreható: a Pascal, Blase Pascal zsenialitásáról elnevezve, egy strukturált programozási paradigmára épülő nyelv, amely szigorú típuskezelésével és világos szintaxisával kiválóan alkalmas az alapvető programozási elvek elsajátítására. A korlátai – például a modern, beépített adatszerkezetek hiánya – arra kényszerítenek minket, hogy mélyebben megértsük az algoritmusok működését. Egy ilyen feladat Pascalban való megoldása nem csupán egy kód megírása; ez egy gondolkodási folyamat, amely során manuálisan kell megvalósítanunk azokat a mechanizmusokat, amelyek a fejlettebb nyelvekben már a motorháztető alatt rejtőznek. Ez az igazi programozási kihívás, ami fejleszti a logikus gondolkodásunkat és problémamegoldó képességünket. ✨

A Feladat Megértése: Két Lépésben az Egyedi Adatokig 🚀

A célunk két különálló tömb, mondjuk `TombA` és `TombB` elemeinek egyesítése egyetlen, `EredmenyTomb` nevű tömbbe, úgy, hogy az `EredmenyTomb` ne tartalmazzon ismétlődő elemeket. Tegyük fel, hogy mindkét forrástömb egész számokat tárol, de a módszertan általánosítható más adattípusokra is. A feladat két fő szakaszra bontható:

1. Összefűzés: Az elemek átmásolása az egyik tömbből a másikba, vagy egy harmadik, kombinált tömbbe.
2. Duplikátumok Eltávolítása: Az azonos értékek kiszűrése a kombinált tömbből, úgy, hogy minden érték csak egyszer szerepeljen.

1. szakasz: Az Összefűzés Alapjai Pascalban 🔧

Mivel a Pascal alapértelmezett tömbjei statikusak, azaz méretüket a fordítási időben kell megadni, az összefűzés előtt gondoskodnunk kell egy elegendően nagy eredménymező létrehozásáról. A legbiztonságosabb, ha az `EredmenyTomb` mérete legalább annyi, mint a két forrástömb méretének összege, így biztosan elfér benne minden lehetséges egyedi elem is.

Először egyszerűen átmásoljuk az első tömb elemeit az eredménymezőbe, majd a második tömb elemeit is. Fontos, hogy ne feledkezzünk meg arról, hogy a tömb valós elemszámát egy külön változóban (pl. `AktualisMeret`) tartsuk nyilván, hiszen a tömb deklarált mérete lehet nagyobb, mint a benne tárolt adatok száma.

TYPE
  TSzamTomb = ARRAY[1..100] OF Integer;

VAR
  TombA, TombB, EredmenyTomb: TSzamTomb;
  MeretA, MeretB, AktualisMeret: Integer;
  i: Integer;

BEGIN
  (* Példa adatok feltöltése *)
  MeretA := 5;
  TombA[1] := 10; TombA[2] := 20; TombA[3] := 30; TombA[4] := 20; TombA[5] := 40;

  MeretB := 4;
  TombB[1] := 30; TombB[2] := 50; TombB[3] := 60; TombB[4] := 10;

  (* TombA elemeinek másolása *)
  AktualisMeret := 0;
  FOR i := 1 TO MeretA DO
  BEGIN
    AktualisMeret := AktualisMeret + 1;
    EredmenyTomb[AktualisMeret] := TombA[i];
  END;

  (* TombB elemeinek másolása *)
  FOR i := 1 TO MeretB DO
  BEGIN
    AktualisMeret := AktualisMeret + 1;
    EredmenyTomb[AktualisMeret] := TombB[i];
  END;

  (* Ezen a ponton az EredmenyTomb tartalmazza mindkét tömb elemeit, duplikátumokkal. *)
END.

Ez a kezdeti összefűzés létrehoz egy tömböt, amelyben a duplikátumok még jelen vannak. A következő lépés az „elegáns” eltávolításuk.

2. szakasz: Duplikátumok Eltávolítása – Az Elegancia Kérdése 💡

A duplikátumok eltávolítására több módszer is létezik, de az „elegáns” megoldás nem csupán a cél elérését jelenti, hanem azt is, hogy az hatékony, könnyen érthető és fenntartható legyen. Pascal környezetben, ahol nincsenek beépített halmaz (set) adatszerkezetek általános típusokra, kreatívnak kell lennünk.

A) A Naiv, Kétlépcsős Megoldás: Iteráció és Törlés

Az egyik legegyszerűbb, de nem feltétlenül leghatékonyabb megközelítés az, ha az összefűzött tömbön iterálunk, és minden elemről ellenőrizzük, hogy szerepel-e már korábban. Ha igen, akkor töröljük (vagy inkább felülírjuk a rákövetkező elemekkel).

// Folytatás az előző kódrészlettől
PROCEDURE DuplikatumokTorlese(VAR Tomb: TSzamTomb; VAR Meret: Integer);
VAR
  i, j, k: Integer;
  IsmetlodesVan: Boolean;
BEGIN
  i := 1;
  WHILE i <= Meret DO
  BEGIN
    IsmetlodesVan := False;
    FOR j := 1 TO i - 1 DO // Ellenőrizzük a korábbi elemeket
    BEGIN
      IF Tomb[i] = Tomb[j] THEN
      BEGIN
        IsmetlodesVan := True;
        BREAK; // Találtunk ismétlődést, lépjünk ki a belső ciklusból
      END;
    END;

    IF IsmetlodesVan THEN
    BEGIN
      // Ha ismétlődés van, eltoljuk az elemeket balra
      FOR k := i TO Meret - 1 DO
        Tomb[k] := Tomb[k + 1];
      Meret := Meret - 1; // Csökkentjük a tömb méretét
      // Fontos: i nem növeljük, mert a következő elem került az aktuális pozícióra
    END
    ELSE
    BEGIN
      i := i + 1; // Csak akkor lépünk a következő elemre, ha nem volt ismétlődés
    END;
  END;
END;

BEGIN
  (* ... Előző összefűzési kód ... *)
  DuplikatumokTorlese(EredmenyTomb, AktualisMeret);

  (* EredmenyTomb kiíratása ellenőrzésképpen *)
  WRITELN('Eredmény tömb egyedi elemekkel:');
  FOR i := 1 TO AktualisMeret DO
    WRITE(EredmenyTomb[i], ' ');
  WRITELN;
END.

Ez a módszer működik, de a beágyazott ciklusok és az elemek folyamatos eltolása (ami egy O(N) művelet) miatt teljesítménye nem optimális. Az időkomplexitása közel O(N^2), ami nagy adathalmazok esetén jelentősen lassú lehet.

B) Az Elegánsabb Megoldás: Rendezés és Egyediség ✨

Az egyik leggyakrabban alkalmazott és legpraktikusabb módszer a duplikátumok eltávolítására, ha először rendezzük az összefűzött tömböt. Egy rendezett tömbben az azonos elemek egymás mellé kerülnek, ami rendkívül egyszerűvé teszi az egyedi elemek kinyerését.

Lépések:

1. Összefűzzük a két forrástömböt egy ideiglenes, `KombinaltTomb` nevű tömbbe (ahogy a fentebb bemutatott első szakaszban).
2. Rendezzük a `KombinaltTomb`-ot. Pascalban nincs beépített rendező függvény, így magunknak kell implementálnunk egyet, például egy egyszerű Bubble Sortot (bár hatékonyabb algoritmusok, mint a QuickSort vagy MergeSort, jobb teljesítményt nyújtanának nagyobb tömbök esetén).
3. Miután a tömb rendezett, végigmegyünk rajta, és csak azokat az elemeket másoljuk át egy új `EredmenyTomb`-ba, amelyek különböznek az előzőtől.

Rendezés (például Bubble Sorttal):

PROCEDURE BubbleSort(VAR Tomb: TSzamTomb; Meret: Integer);
VAR
  i, j, Temp: Integer;
BEGIN
  FOR i := 1 TO Meret - 1 DO
  BEGIN
    FOR j := 1 TO Meret - i DO
    BEGIN
      IF Tomb[j] > Tomb[j + 1] THEN
      BEGIN
        Temp := Tomb[j];
        Tomb[j] := Tomb[j + 1];
        Tomb[j + 1] := Temp;
      END;
    END;
  END;
END;

Egyedivé tétel rendezés után:

PROCEDURE EgyediveTeszRendezettTombot(VAR ForrasTomb: TSzamTomb; ForrasMeret: Integer;
                                    VAR CelTomb: TSzamTomb; VAR CelMeret: Integer);
VAR
  i: Integer;
BEGIN
  CelMeret := 0;
  IF ForrasMeret > 0 THEN
  BEGIN
    CelMeret := 1;
    CelTomb[1] := ForrasTomb[1]; // Az első elem mindig egyedi
    FOR i := 2 TO ForrasMeret DO
    BEGIN
      IF ForrasTomb[i]  CelTomb[CelMeret] THEN // Csak akkor adjuk hozzá, ha különbözik az előzőtől
      BEGIN
        CelMeret := CelMeret + 1;
        CelTomb[CelMeret] := ForrasTomb[i];
      END;
    END;
  END;
END;

A teljes folyamat egyben:

TYPE
  TSzamTomb = ARRAY[1..100] OF Integer;

VAR
  TombA, TombB, KombinaltTomb, EredmenyTomb: TSzamTomb;
  MeretA, MeretB, KombinaltMeret, EredmenyMeret: Integer;
  i: Integer;

(* Ide jönnek a BubbleSort és az EgyediveTeszRendezettTombot eljárások *)

BEGIN
  (* Példa adatok feltöltése *)
  MeretA := 5;
  TombA[1] := 10; TombA[2] := 20; TombA[3] := 30; TombA[4] := 20; TombA[5] := 40;

  MeretB := 4;
  TombB[1] := 30; TombB[2] := 50; TombB[3] := 60; TombB[4] := 10;

  (* 1. Lépés: Összefűzés KombinaltTomb-ba *)
  KombinaltMeret := 0;
  FOR i := 1 TO MeretA DO
  BEGIN
    KombinaltMeret := KombinaltMeret + 1;
    KombinaltTomb[KombinaltMeret] := TombA[i];
  END;

  FOR i := 1 TO MeretB DO
  BEGIN
    KombinaltMeret := KombinaltMeret + 1;
    KombinaltTomb[KombinaltMeret] := TombB[i];
  END;

  WRITELN('Kombinált tömb (duplikátumokkal):');
  FOR i := 1 TO KombinaltMeret DO
    WRITE(KombinaltTomb[i], ' ');
  WRITELN;

  (* 2. Lépés: Rendezés *)
  BubbleSort(KombinaltTomb, KombinaltMeret);

  WRITELN('Rendezett kombinált tömb:');
  FOR i := 1 TO KombinaltMeret DO
    WRITE(KombinaltTomb[i], ' ');
  WRITELN;

  (* 3. Lépés: Egyedi elemek kinyerése *)
  EgyediveTeszRendezettTombot(KombinaltTomb, KombinaltMeret, EredmenyTomb, EredmenyMeret);

  WRITELN('Eredmény tömb (egyedi elemekkel):');
  FOR i := 1 TO EredmenyMeret DO
    WRITE(EredmenyTomb[i], ' ');
  WRITELN;

END.

Ennek a megközelítésnek az időkomplexitása nagyrészt a rendezési algoritmustól függ. Egy Bubble Sort O(N^2), de egy hatékonyabb QuickSort vagy MergeSort O(N log N) komplexitású lenne. Az egyedivé tétel ezután csak O(N) lépés. Ez a módszer sokkal hatékonyabb a nagy adathalmazok esetén, mint a korábbi „iteráció és eltolás” technika, és ezért elegánsabbnak tekinthető. Az elemek eltolása helyett, ami sok memóriamozgatást igényel, itt csak egyszer sorrendbe rakjuk az adatokat, majd egyszerűen átmásoljuk az egyedi elemeket.

C) Haladóbb megközelítés: Boolean jelzőtömb (speciális eset) 📚

Ha az adatok egy szűk és ismert tartományba esnek (például 0 és 1000 közötti egész számok), akkor használhatunk egy Boolean jelzőtömböt (vagy „hash set” szimulációt) az egyediség gyors ellenőrzésére. Ez a módszer a leggyorsabb, O(N) komplexitású.

// Feltételezzük, hogy a számok 0 és MaxErtek között vannak
CONST MaxErtek = 1000;

TYPE
  TElteroTomb = ARRAY[1..100] OF Integer;
  TVoltLatva = ARRAY[0..MaxErtek] OF Boolean; // A jelzőtömb

VAR
  TombA, TombB, EredmenyTomb: TElteroTomb;
  MeretA, MeretB, EredmenyMeret: Integer;
  VoltLatva: TVoltLatva;
  i, Ertek: Integer;

BEGIN
  (* Példa adatok feltöltése *)
  MeretA := 5;
  TombA[1] := 10; TombA[2] := 20; TombA[3] := 30; TombA[4] := 20; TombA[5] := 40;

  MeretB := 4;
  TombB[1] := 30; TombB[2] := 50; TombB[3] := 60; TombB[4] := 10;

  (* VoltLatva tömb inicializálása *)
  FOR i := 0 TO MaxErtek DO
    VoltLatva[i] := False;

  EredmenyMeret := 0;

  (* TombA elemeinek feldolgozása *)
  FOR i := 1 TO MeretA DO
  BEGIN
    Ertek := TombA[i];
    IF NOT VoltLatva[Ertek] THEN // Ha még nem láttuk ezt az értéket
    BEGIN
      EredmenyMeret := EredmenyMeret + 1;
      EredmenyTomb[EredmenyMeret] := Ertek;
      VoltLatva[Ertek] := True; // Megjelöljük, hogy láttuk
    END;
  END;

  (* TombB elemeinek feldolgozása *)
  FOR i := 1 TO MeretB DO
  BEGIN
    Ertek := TombB[i];
    IF NOT VoltLatva[Ertek] THEN // Ha még nem láttuk ezt az értéket
    BEGIN
      EredmenyMeret := EredmenyMeret + 1;
      EredmenyTomb[EredmenyMeret] := Ertek;
      VoltLatva[Ertek] := True; // Megjelöljük, hogy láttuk
    END;
  END;

  WRITELN('Eredmény tömb (egyedi elemekkel, Boolean jelzőtömbbel):');
  FOR i := 1 TO EredmenyMeret DO
    WRITE(EredmenyTomb[i], ' ');
  WRITELN;
END.

Ez a technika rendkívül gyors, mivel minden elem ellenőrzése és hozzáadása állandó idő (O(1)) alatt történik. Az összkomplexitás így O(N). Hátránya, hogy csak akkor alkalmazható, ha az adatok tartománya korlátozott és ismert, mert a `VoltLatva` tömb mérete az adatok maximális értékétől függ.

Az adatszerkezetek és algoritmusok mélyreható megértése kulcsfontosságú, nem csupán az interjúk sikeres teljesítéséhez, hanem ahhoz is, hogy valóban hatékony és elegáns kódot írhassunk bármilyen környezetben. A Pascalban való küzdelem a korlátozásokkal rávilágít, hogy a „hogyan” néha sokkal fontosabb, mint a „mit”.

Véleményem a Kihívásról 🧑‍💻

Számomra, mint programozónak, a Pascal kihívások mindig is különleges élményt nyújtottak. A modern nyelvek kényelméhez szokva könnyen megfeledkezhetünk arról, hogy a mögöttes mechanizmusok milyen komplexitással bírnak. Amikor például egy Python listában meghívjuk a `set()` függvényt, vagy egy JavaScript tömbön a `filter()` és `indexOf()` kombinációját, azt gondolhatjuk, hogy ez csupán egy nyelvi sajátosság. De a valóságban ezek a funkciók optimalizált algoritmusok, amelyek a háttérben futnak.

Egy ilyen Pascal feladat megoldása – legyen szó a tömbök összefűzéséről vagy a duplikátumok törléséről – visszavisz minket az alapokhoz. Kényszerít arra, hogy magunk gondoljuk át a logikát, a memória kezelését, az indexelést, és az időkomplexitás optimalizálását. Emlékszem, amikor először próbáltam hasonló problémát megoldani egyetemen, és órákig ültem egy hiba felett, mert elfelejtettem frissíteni a tömb aktuális méretét egy törlés után. Ez az élmény, bár frusztráló volt, végül mélyebb megértéshez vezetett. Arra tanított meg, hogy ne csak a „mit” programozzam le, hanem a „hogyan” is átgondoljam minden apró részletében. Ez a fajta alapos programozás olyan alapot ad, ami később bármelyik, sokkal absztraktabb nyelven is kifizetődővé válik. Arról nem is beszélve, hogy az „elegáns” megoldások keresése – mint például a rendezés utáni egyedivé tétel – a kreativitást is fejleszti. Olyan ez, mint egy kézműves munka: nem veszel készen egy tárgyat, hanem aprólékosan, a semmiből építed fel, és minden lépésnél tanulod az anyag és az eszközök viselkedését.

Összefoglalás 📚

A Pascal kihívás, miszerint két tömböt összefűzzünk és a duplikátumokat elegánsan eltávolítsuk, egy kiváló gyakorlat a programozási alapok megerősítésére. Láthattuk, hogy több megközelítés is lehetséges, a legegyszerűbb, de kevésbé hatékony iterációtól kezdve, a rendezést alkalmazó, közepesen komplex, de jóval hatékonyabb megoldásig, egészen a speciális esetekre optimalizált Boolean jelzőtömbös technikáig. Mindegyik módszernek megvannak a maga előnyei és hátrányai a hatékonyság és az alkalmazhatóság szempontjából.

A leginkább általános és „elegáns” megoldás a rendezésen alapuló technika, mivel a legtöbb adattípusra alkalmazható, és az O(N log N) időkomplexitás megfelelő teljesítményt nyújt a legtöbb esetben. A Pascal, mint oktató nyelv, tökéletesen alkalmas arra, hogy ezeket az alapvető algoritmusokat a gyakorlatban is megértsük és implementáljuk. Ez a tudás nem évül el, hanem alapot teremt a jövőbeli, komplexebb programozási feladatok megoldásához, függetlenül attól, milyen nyelvet vagy technológiát használunk éppen. Ahogy mondani szokás: egy igazi mérnök nem a szerszámaitól, hanem a problémamegoldó képességétől profi.