Najkrajši niz

Najkrajši niz

Avtor: Aleš Brelih

Opis problema

Mojca si je v tekstovno datoteko zapisala ducat besed s petimi črkami. Poiskati želi najkrajši niz (ki ni nujno smislena beseda), v katerem lahko najdemo vse besede.

Vnesi ime datoteke: podatki.txt Najkrajši niz je: ...nakupotepkartarok...

(Prikazan je le del rešitve, v katerem razberemo besede nakup, potep, tepka, karta, tarok.)

Ideja rešitve

Sestava rešitve (različne metode):

  • PoisciVseBesede (string imeDat) - Iz datoteke poišče vse besede. Besede se lahko nahajajo na različnih vrsticah. Ločene so lahko samo z vejicami.
  • NajkrajsaDvojica(List<string> vseBesede) - Funkcija vrne indeks besede v seznamu, ki je vsebovana v najkrajši dvojici zlepkov v tem seznamu.
  • ZdruziBesedi(string prva, string druga) - Ustrezno združi besedi, ki ji imamo v parametru. In vrne zlepek oziroma niz.
  • PoisciNajkrajsiRek(List<string> vseBes) - Iz seznama besed sestavi najkrajši niz. Uporabim jo kot pomožno metodo metodi PoisciNajkrajsi.
  • PoisciNajkrajsi (List<string> vseBesede) - Iz seznama besed vrne najkrajši niz.

PoisciVseBesede

Funkcija na dateoteki najde vse zapisane besede. Pri iskanju besed moramo paziti, da odstranimo vse odvečne prazne znake. Pozabiti pa tudi ne smemo na primere, ko se vrstica na datoteki zaključi z vejico.

Koda - C#

PoisciVseBesede - C#

public static List<string> PoisciVseBesede(string imeDat)
        {
            StreamReader datoteka = File.OpenText(imeDat);
            List<string> sezBes = new List<string>();
            while (!datoteka.EndOfStream)
            {
                string vrstica = datoteka.ReadLine();

                string[] besede = vrstica.Split(','); //Besede so lahko v več vrsticah in tudi ločene z vejicami
                foreach (string beseda in besede)
                {
                    if (beseda.Trim().Length == 5)
                        sezBes.Add(beseda.Trim()); //ODstranimo dodatne prazne znake
                    else if (beseda.Length == 0)
                        continue;
                    else
                        throw new Exception("Napaka! " + beseda.Trim() + " ni ustrezne dolžine");
                }

            }
            datoteka.Close();
            return sezBes;
        }

NajkrajsaDvojica

Funkcija vrne indeks ene izmed besed v najkrajšem možnem zlepku dvojice besed. Potrebovali bomo dve zanki, saj moramo poskusiti paroma združiti vse besede med seboj.

V zankah torej poskušamo združiti dve besedi. Združeni niz primerjamo z najkrajšim zlepkom, ki smo ga do takrat imeli. V primeru, ko je nov niz krajši od najkrajše dvojice, zlepek in indeks ene izmed dveh besed z zlepku shranimo.

Koda - C#

NajkrajsaDvojica - C#

public static int NajkrajsaDvojica(List<string> vseBesede)
        {
            string nizTest = "***************"; //skupni niz ne bo nikoli te dolzine
            int indeksNajkrajseDvojice = 0;
            for (int i = 0; i < vseBesede.Count; i++)
            {
                string niz;
                foreach (var besedaPrilepi in vseBesede)
                {
                    if (besedaPrilepi != vseBesede[i])
                    {
                        niz = ZdruziBesedi(vseBesede[i], besedaPrilepi);
                        if (niz.Length < nizTest.Length)
                        {
                            nizTest = niz;
                            indeksNajkrajseDvojice = i; //vrnemo samo indeks, saj ga potrebujemo, da najkrajši niz preložimo na začetek seznama
                        }

                    }
                }
            }
            return indeksNajkrajseDvojice;
        }

ZdruziBesedi

Funkcija poskusi združiti besedi v parametru. Metoda deluje le, če sta obe besedi dolžine 5. Vsaki izmed besed moramo združiti na dva načina. Najprej ju združimo tako, da drugo besedo poskusimo dodati na začetek prve besede. Nato pa še na konec prve besede. Izmed teh dveh nizov izberemo krajši niz in ga vrnemo

Koda - C#

ZdruziBesedi - C#

public static string ZdruziBesedi(string prva, string druga)
        {

            int dolPrve = prva.Length;
            string zLeve = druga + prva; //najprej združimo obe besedi "normalno" (torej prva + druga oziroma druga+prva)
            string zDesne = prva + druga;

            for (int i = 4, j = 1; i > 0; i--, j++)
            {
                if (prva.Substring(0, i) == druga.Substring(j, i))
                {
                    zLeve = druga.Substring(0, j) + prva;
                    break; //zanko zaustavimo, saj začnemo z maksimalno možno združitvijo
                }
            }
            for (int i = 4, j = 1; i > 0; i--, j++)
            {
                if (prva.Substring(dolPrve - 5 + j, i) == druga.Substring(0, i))
                {
                    zDesne = prva + druga.Substring(i, j);
                    break;
                }
            }
            if (zLeve.Length < zDesne.Length) //preverimo katera združitev je najkrajša
                return zLeve;
            else
                return zDesne;

        }

PoisciNajkrajsiRek

Funkcija prejme seznam besed kot parameter. V tem seznamu vzame prvi element in poskusi poiskat najboljši (najkrajši) zlepek z ostalimi besedami v seznamu. Zlepek nato postavi na prvo mesto. Besedo s katero smo ustvarili zlepek pa odstranimo iz seznama. Funkcijo nato ponovno kličemo na prenovljenem seznamu. Zaključi se, ko je v seznamu samo še en element, ki predstavlja najkrajši niz.

Koda - C#

PoisciNajkrajsiRek - C#

public static string PoisciNajkrajsiRek(List<string> vseBes)
        {
            if (vseBes.Count == 1) //zaustavitveni pogoj
                return vseBes[0];
            else
            {
                int indeksUstreznega = 0; //indeks besede, ki jo bomo zlepili
                string skupniNiz = null;
                for (int i = 1; i < vseBes.Count(); i++) //potujemo po vseh besedah
                {
                    string zlepek = ZdruziBesedi(vseBes[0], vseBes[i]);
                    if (skupniNiz == null || zlepek.Length < skupniNiz.Length) //isčemo najkrajši zlepek
                    {
                        indeksUstreznega = i;
                        skupniNiz = zlepek;
                    }
                }
                vseBes[0] = skupniNiz; //zlepek damo na prvo mesto v seznamu
                vseBes.RemoveAt(indeksUstreznega); //odstranimo besedo, ki smo jo uporabili pri zlepku
                return PoisciNajkrajsiRek(vseBes);
            }

        }

PoisciNajkrajsi

Ta funkcija nam samo služi v pomoč pri uporabi rekurzivne funkcije, saj pri rekurzivni moramo začeti z najkrajšim zlepkom. Zato v tej funkciji najprej postavimo besedo, ki je vsebovana v najkrajšem zlepku izmed vseh na začetek seznama in nato uporabimo rekurzivno funkcijo na tem seznamu. Pri ugotavljanju indeksa te besede si pomagamo s funkcijo NajkrajsaDvojica.

Koda - C#

PoisciNajkrajsi - C#

public static string PoisciNajkrajsi(List<string> vseBesede)
        {
            int zacetekZanke = NajkrajsaDvojica(vseBesede);
            if (zacetekZanke != 0)
            {
                string zamenjajBesedo = vseBesede[zacetekZanke];
                vseBesede[zacetekZanke] = vseBesede[0];
                vseBesede[0] = zamenjajBesedo;
            }
            return PoisciNajkrajsiRek(vseBesede);
        }

Testni primeri

1.primer

nakup,tarok
potep, tepka, karta, znjaz,

Primer sem si izbral, ker je sestavljen iz več vrstic. Druga vrstica se tudi zaključi s vejico. S tem predvsem preverim delovanje funkcije, ki poišče vse besede na datoteki.

2.primer

 , ,
 , , .

Primer sem izbral, ker je datoteka sestavljena samo iz vejic in pik. Program najde samo en niz na datoteki in to je ".". Ker pika ne ustreza kriterij za iskani niz program vrne izjemo.

Wink - film

Primer uporabe

0%
0%