[ darthskywalker @ 02.07.2012. 15:42 ] @
Pozdrav,
pokusavam da rijesim jedan zadatak u C++. Zadatak je sljedeci: napisati funkciju koja kao parametar prima vektor realnih brojeva. Funkcija treba da ispita da li elementi vektora cine niz koji se periodicno ponavlja ili ne. Npr., za vektor ciji su elementi 5 9 7 2 5 9 7 2 5 9 7, uocavamo da njegovi elementi cine niz koji se periodicno ponavlja sa duzinom perioda 4. Ukoliko elementi vektora cine periodican niz, funkcija treba da vrati kao rezultat duzinu perioda, a u suprotnom, funkcija treba da vrati nulu kao rezultat. Ja sam uspio rijesiti na jedan nacin, i program funkcionise samo u slucaju da se u jednom periodu ne desi da postoje dva ista broja. Uzeo sam prvi element niza kao referenti i uporedjivao sa svakim sljedecim, dok ne dodjem do tog istog elementa. Kad se u nizu pronadji element isti kao referentni, duzina izmedju ta 2 elementa predstavlja potencijalni period. Zatim sam na osnovu tog perioda uporedio sve ostale elemente. I to sve radi ok u slucaju da se u periodu ne pojave 2 ista broja. Da li neko ima ideju kako rijesiti problem za slucaj da su periodu 2 ista elementa. Npr. 5 3 1 5 7 | 5 3 1 5 7 | 5 3 1 5 7 ??
[ milanche @ 02.07.2012. 17:16 ] @
Promeni algoritam da njuska po nizu dok ne pronadje ne jedan nego dva broja identicna sa dva broja na trenutnoj poziciji, pa
tako nadjenu lokaciju uzmi kao potencijalno periodicnu tacku za dalju analizu.
[ glorius @ 02.07.2012. 17:52 ] @
Evo resenja koje ti moze dati ideju...
Moje resenje koristi string zato sto string klasa ima zgodnu funkciju substr koja je korisna za nalazenje ponavljanja skupa karaktera.

Code:


#include <vector>
#include <iostream>
#include <string>

int _tmain(int argc, _TCHAR* argv[])
{
    std::string niz;
    niz.push_back('5');
    niz.push_back('3');
    niz.push_back('1');
    niz.push_back('5');
    niz.push_back('7');

    niz.push_back('5');
    niz.push_back('3');
    niz.push_back('1');
    niz.push_back('5');
    niz.push_back('7');

    niz.push_back('5');
    niz.push_back('3');
    niz.push_back('1');
    niz.push_back('5');
    niz.push_back('7');

        // promenljiva u kojoj smestamo trenutni podniz
    std::string podNiz;
    std::string rezultat;

    for(int i=0;i<niz.size();i++)
    {
        // proveravamo da li drugi deo niza (pocevsi od i) sadrzi trenutni podniz
        // ako ga sadrzi proveravamo dalje sve dok ne naidjemo na slucaj da niz vise ne sadrzi isti pattern kao podniz
        // na taj nacin nalazimo najveci podniz koji se sadrzi u nizu
        if(niz.find(podNiz, i) == -1)
        {
            break;    
        }

        rezultat = podNiz;
        podNiz += niz[i];
    }

    std::cout << rezultat;

    return 0;
}



Ne znam da li ovo radi za sve varijacije nizova ali ti moze biti polazna tacka za resenje problema. Npr. mozes interno u nekoj funkciji nadjiNajveciPonavljajuciPodniz da iskoristis ovaj kod i da vektor integera stavis u string pa posle da rezultat opet vratis u vektor integera a mozes i da implementiras funkciju analognu substr koja ce raditi sa integers (sto je, po meni, bolje resenje).