Fibonacijev podniz

Moze li mala pomoc oko zadatka:

https://petlja.org/BubbleBee/r/FibonacijeviPodnizovi

Program mi vraca WA na 7 i TLE na 3 test primera. Svaki test primer koji ja pokusam prolazi. Zbog toga mi nije jasno zasto mi vraca WA.

IDEJA:

  1. Tokom ucitavanja niza uzimam sve Fibonacijeve brojeve kao i njihove indekse i smestam ih u posebne nizove, pri cemu vodim racuna da svaki broj uzmem jednom, osim jedinice koju uzimam do 2 puta.

  2. Sortiram niz izdvojenih Fibonacijevih brojeva i sortiram niz njihovih indeksa

  3. Prolazim kroz sortiran niz Fibonacijevih brojeva i proveravam da li vazi f[i]+f[i+1]=f[i+2], gde cuvam poziciju pocetnog elementa i trenutnu duzinu za koju to vazi - tako pronalazim pocetnu poziciju i duzinu maksimalnog podniza koji stampam.

kod: https://pastebin.com/vqDTXPRb

Svestan sam da kod nije najbrzi moguci i znam gde to mogu popraviti ali me sada zanima zasto mi prijavljuje pogresne odgovore.

1 Like

(Nisam se previse udubljivao, na prvi pogled)

  1. Sto se tice WA, mislim da je greska u
poctrenutna = i + 2;

Ako je

fib[i] + fib[i + 1] != fib[i + 2]

to ne znaci da

fib[i+1] + fib[i + 2] != fib[i + 3]

tj. i + 1 moze da bude pocetna pozicija podniza, a ti preskaces postavljajuci poctrenutna na i + 2

  1. Sort koji koristis ima kvadratnu slozenost. Najbolje da iskoristis sort funkciju u C++u, ali za to ces morati da napravis strukturu. Evo ovako
struct Element {
    int fib, index;

    Element(int fib

    bool operator < (const Element& otherElement) const {
        if (fib != otherElement.fib) return fib < otherElement.fib;
        return index < otherElement.index;
   }
};

Onda mozes da kreiras niz elemenata:

elementi[brojac++] = Element(a, brojac);

I sortiras:

sort(elementi, elementi + brojac);

To bi trebalo da ti resi problem sa TLE.

Okej, mislim da mi nije jasna formulacija zadatka.Da li se trazi da se gledaju svi podnizovi koji imaju svojstvo f(n)+f(n+1)=f(n+2) ili da se izdvoje samo oni koji su podnizi Fibonacijevog niza, onog koji pored zadate rekurentne jednacine ima pocetne uslove f(1)=f(2)=1.
Dakle ukoliko su fib[i] i fib[i+1] susedni clanovi Fibonacijevog niza, a nije njima susedan clan fib[i+2] onda nema smisla gledati da li je fib[i+1]+fib[i+2]=fib[i+3], zar ne ?

Da pojasnim:

test primer je: 2 4 6 8 10 11 13 4 3 2 1 1

moj kod prvo izdvoji

1 1 2 3 8 13

Ako sam dobro razumeo, ti predlazes da nakon sto utvrdim da 2+3!=8 treba da pocnem novo proveravanje od toga da li je 3+8=13?
Dakle moje rezon je da ako utvrdim da je 2+3!=8 znam sigurno da sam preskocio neki broj iz Fibonacijevog niza i da novo proveravanje treba da pocnem od osmice umesto od trojke.

EDIT: Okej zapravo mislim da si ipak u pravu. Ovo sto sam napisao je tacno ukoliko imam vec neki podniz ali ako moji brojevi pocinju npr. kao 2 5 8 13 itd… onda zaista nakon sto utvrdim da je 2+5!=8 treba da proverim da li je 5+8=13.

U svakom slucaju ta ispravka nije popravila WA. :frowning:
Ipak, razmotricu sutra jos jednom ceo kod jer mozda postoji neki deo koji je povezan sa tim…

Sto se tice drugog dela. Hvala na pomoci! Ipak poceo sam da ucim od nule i jos nisam stigao do struktura, u svakom slucaju sam i planirao da se vratim na ovaj zadatak kada budem prosao kroz to pa ce mi ovo znaciti.

Pozdrav!

1 Like