# Problem sa zadatkom Fibonacijevi podnizovi

**URL:** <https://algora.petlja.org/t/problem-sa-zadatkom-fibonacijevi-podnizovi/3104>\
**Category:** Pitanja i problemi\
**Created:** [September 22, 2019, 8:23pm UTC](https://algora.petlja.org/t/problem-sa-zadatkom-fibonacijevi-podnizovi/3104 "2019-09-22T20:23:45Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![Mita04](https://algora.petlja.org/user_avatar/algora.petlja.org/mita04/32/716_2.png) [@Mita04](https://algora.petlja.org/u/Mita04)\
**Post date:** [September 22, 2019, 8:23pm UTC](https://algora.petlja.org/t/problem-sa-zadatkom-fibonacijevi-podnizovi/3104/1 "2019-09-22T20:23:45Z")

</div>

Nemam ideju kako mogu da resim ovaj zadatak [https://petlja.org/biblioteka/r/FibonacijeviPodnizovi](https://petlja.org/biblioteka/r/FibonacijeviPodnizovi)

---

<div class="post-metadata">

**Author:** ![dd](https://algora.petlja.org/user_avatar/algora.petlja.org/dd/32/421_2.png) [@dd](https://algora.petlja.org/u/dd)\
**Post date:** [September 25, 2019, 2:21pm UTC](https://algora.petlja.org/t/problem-sa-zadatkom-fibonacijevi-podnizovi/3104/2 "2019-09-25T14:21:14Z")

</div>

Koliko shvatam tekst, na ulazu moze biti mnogo brojeva (N je veliko), ali nema velikih vrednosti – najveca moguca vrednost je samo M = 10000. Da bi izbegli cuvanje svih N brojeva i mogli brzo da proverimo da li je neki broj na raspolaganju, mozemo u niz sacuvati "da li ulaz sadrzi broj i" (posto se na izlazu traze i indeksi, dobro bi bilo sacuvati i prvi indeks gde se i pojavljuje).

Sada mozemo da probamo svaki moguci par prvih elemenata niza (njih M^2) i redom racunamo naredni element dok god ne naidjemo na neki koji se ne nalazi u ulazu (tj. nije markiran u nizu). Iako ovo naizgled deluje kao spor algoritam, sa tri ugnjezdene petlje i samim tim mozda \mathcal{O}(N^3), slozenost je u stvari primetno bolja jer vrednosti Fibonacijevog niza rastu brzo, tako da se treca petlja (koja racuna elemente niza) nece izvrsavati dugo.

Malo bolja analiza slozenosti (nebitna za resavanje zadatka): elementi fibonacijevog niza rastu eksponencijalno (za pocetne clanove 1, 1, n-ti clan je srazmeran sa \phi^n, gde je \phi zlatni presek). Samim tim, vrednost koju racunamo u unutrasnjoj petlji ce preci M u \mathcal{O}(\log M) koraka, tako da je ukupna slozenost \mathcal{O}(M^2 \log M).