Programozás‎ > ‎Feladatok‎ > ‎Telefonszámok‎ > ‎

Megoldás

Algoritmus

Ezen az órán - szándékosan - csak a "nyers erő" módszerét alkalmaztuk: visszalépéses kereséssel előállítottuk a megadott telefonszám összes olyan felbontását, amely szótárbeli szavakhoz rendelt számsorozatokból képezhető. Ehhez egyszerűen minden lehetséges állapotban megnéztük, hogy a még előállítandó karakterlánc kezdőszeletére melyik szótárbeli szó kódja illeszkedik, mindegyik megfelelő kezdőszeletet ki is próbáltuk, majd a megmaradt részre rekurzív meghívtuk eljárásunkat. Ha a teljes karakterláncot lefedtük, azt a rekurzió vizsgálja, és kezeli: például kiírja a talált megoldást, illetve minimumkiválasztást végez.

Kódok

Lipták Bence (pascal): lb_telefon.pas
Ódor Gergő (c++): og_phone.cpp

Hatékonyabb algoritmus

A feladatot átfogalmazhatjuk. Csak azzal a részproblémával foglalkozunk, hogy egy karakterláncot hogyan lehet minimális számú, rögzített szótárból választott karakterlánc összefűzéseként előállítani. Legyen a megadott karakterlánc N hosszú (karakterei c[1], c[2], ...,c[N]) és feleltessünk meg neki egy N+1 csúcsú gráfot a következő módon:
  • a 0. csúcs speciális, az 1., 2., ..., N. csúcs pedig karakterlánc karaktereinek felel meg
  • az i. és j. (i<j) csúcs között akkor megy i->j irányított él, ha a c[i+1]c[i+2]...c[j] szó szerepel a szótárban
Ekkor a minimális szóból álló felbontás megfelel a gráfban egy legrövidebb 0 -> N útnak. Itt az út hossza a benne szereplő élek száma. Használhatjuk a szélességi bejárást, vagy a Disjkstra-algoritmust is, de a gráf egyszerű szerkezete miatt (és mert nincs túl sok csúcs), egy szimpla "négyzetes" algoritmus is célravezető:

d[0] := 0
d[1..N] := végtelen
Ciklus i := 0-tól (N-1)-ig
    Ha d[i] < végtelen akkor
        Ciklus j := (i+1)-től N-ig
            Ha van_él(i,j) és d[j] > d[i]+1 akkor
                d[j] := d[i] + 1
                //itt érdemes feljegyezni azt, hogy melyik szó felel meg az élnek
            Elágazás vége
        Ciklus vége
    Elágazás vége
Ciklus vége

Hatékonyabb kód

Ódor Gergő (c++): og_phone2.cpp
Mikó Péter (pascal): mp_telefon2.pas