Az I. 662. feladat (2025. április)

I. 662. Nagy méretű táblázatokban adatok elhelyezésére és gyors keresésére sok esetben hash-, vagy más néven hasítófüggvényeket alkalmaznak. Az eljárás egy lehetséges módja a következő: a legföljebb \(\displaystyle N\) számú adatnak \(\displaystyle N+M\) méretű tömböt foglalunk le, majd megadunk egy olyan hash-függvényt, amely az adat tulajdonságai alapján kijelöl egy helyet az \(\displaystyle N+M\) méretű sorozatban. A függvény nem kölcsönösen egyértelmű. Ugyanakkor minél kevesebbszer fordul elő, hogy a függvény két adathoz azonos helyet rendel (hash-ütközés), annál hatékonyabb a tárolás és utána a keresés. Amennyiben az adatok beírásakor ütközés lép fel, úgy a már foglalt hely utáni első üres helyre tesszük az adatot.

Készítsünk programot, amely modellezi és vizsgálja a fent leírt hasítótábla működését. Először vegyünk föl egy \(\displaystyle N+M\) méretű tömböt, amelynek minden elemét jelöljük kezdetben üresnek, tehát egyik sem tartalmaz adatot. Ezután töltsük fel a tömböt az \(\displaystyle N\) számú adattal egy hash-függvényt alkalmazva: ha egy adat számára kijelölt hely szabad, akkor tegyük oda, ha nem szabad, akkor a függvény által kijelölt helyet követő első üres helyre. A tömb utolsó eleme után a tömb első eleme következzen. Az adatok elhelyezése során számoljuk meg, hogy hány esetben (\(\displaystyle T\)) nem sikerült egy elemet a hasítófüggvény által jelölt helyre tenni, illetve összesen hány lépést kellett tenni (\(\displaystyle L\)), hogy az adatoknak üres helyet találjunk. A \(\displaystyle T\) és \(\displaystyle L\) szám jól jellemzi a módszer hatékonyságát, és természetesen függ a hash-függvénytől, valamint \(\displaystyle N\) és \(\displaystyle M\) értékétől.

A program hozzon létre \(\displaystyle N\) számú adatot, amelyek mindegyike egy véletlenszerűen választott szó. A szavakat a word5000.txt szöveges állományból vegyük, minden szót legföljebb egyszer válasszunk ki. A honlapunkról letölthető állományban soronként egy angol szó szerepel. Ezt követően találjunk ki egy hash-függvényt, amely minden szóhoz egy \(\displaystyle 0\) és \(\displaystyle N+M-1\) közötti egész számot rendel, és végezzük el a szavak elhelyezését a kezdetben üres tömbbe úgy, hogy közben kiszámítjuk \(\displaystyle T\) és \(\displaystyle L\) értékét.

A program standard bemenetének első sorában a szavak \(\displaystyle N\) száma (\(\displaystyle 30\leq N\leq 3000\)) és a tömb \(\displaystyle N\)-et meghaladó celláinak \(\displaystyle M\) száma (\(\displaystyle 0\leq M\leq 3000\)) szerepel. A program a standard kimenet egy sorába írja ki \(\displaystyle T\) és \(\displaystyle L\) értékét, valamint a hashtab.txt szöveges állományba a hash-tábla tartalmát: soronként egy szót, üres helyek esetén a ,,—'' karaktersorozatot.

Példa (a várható kimenet a hash-függvénytől és véletlentől függő érték):

Beküldendő egy tömörített i662.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható, illetve röviden bemutatja a programban alkalmazott hasítófüggvényt.

Letölthető állomány: word5000.txt

(10 pont)

A beküldési határidő 2025. május 15-én LEJÁRT.

Statisztika:

Az I. 662. feladat értékelése még nem fejeződött be.

A KöMaL 2025. áprilisi informatika feladatai