2011.10.10.Ezen a szakkörön nem lesz új feladat, hanem az egy héttel ezelőtt elkészített megoldásokat fejlesztjük.Az előző heti feladat: Telefonszámok A "szótár" kezelését és a legrövidebb megoldás kiválasztását is végezhetjük "okosabban", ehhez két klasszikus módszert tanulunk. Hasító függvények avagy HASH-elésAz algoritmus egyik kulcslépése a lehetséges szavak hatékony keresése a megengedett szavak listájában. Mivel ez egy alapvető részfeladat a fordítóprogramok működésénél, több különböző megoldást adtak már rá.Sedgewick-Wayne: Hashing Az órai feladat megoldásához az is elegendő, ha a szótár szavait rendezzük, és bináris keresést használunk. Legrövidebb út súlyozatlan, irányítatlan gráfbanSedgewick-Wayne: Shortest Paths A minimális felbontás megtalálása átfogalmazható egy súlyozatlan gráf pontjai közötti legrövidebb út megtalálásának feladatává. Ennek részleteit a feladat megoldásánál közöljük. A legrövidebb út meghatározásának algoritmusait a következő szakkörökön részletezzük. |