Koliko sam ja upoznat, zadatke mozes resiti na taj nacin ukoliko uspes da nadjes neku rekurentnu vezu. Naravno rekurentna jednacina koju dobijes mora biti homogena.. Ispravite me ako gresim.

ok.Hvala ti.
Ipak je potrebno da se pozabavim time malo vise..

Na z-treningu su ti z-orasi bas dobar primer navedene tehnike

znao bi njih da uradim posto se isto rade kao i z-funkcija..
Ali , opet , meni nije bas jasan princip po kome taj stepen otkriva resenje.
Evo jos jednog zadatka za koji je potreban stepen matrice , TourCounting sa TopCodera..

Aha...znaci tebi nije jasno zasto i kako to radi?

Pa evo na prostom primeru ...

Znaci zelis da izracunas n-ti finonacijev broj....

Znamo da se fibonacijevi brojevi racunaju po formuli

E takodje imamo prva dva clana finonacijevog niza a to su i .

Sada zelimo da ta dva clana smestimo u jedan vektor tj. u matricu dimenzija 2 x 1. To bi izgledalo ovako:



Sada zelimo da napravimo neku matricu tako da ako je pomnozimo sa tim vektorom dobijemo sledeca dva clana fib. niza odnosno drugi i treci.

Ukoliko bi matricu pomnozili sa prethodnim vektorom dobili bi upravo vektor sa drugim i trecim clanom, zato sto 0*1 + 1*1 = 1 nam daje drugi clan a 1*1 + 1*1 = 2 (primeti da je ovo upravo formula fibonacijevog niza) nam daje treci clan.

Znaci imamo

* = .

E sad ukoliko bi zeleli da dobijemo treci i cetvrti clan pomnozicemo matricu sa novodobijenim vektorom:

* = * * = * =

Sada je jasno da ako zelimo da dobijemo vektor sa . i . clanom trebamo samo da pocetnu matricu dignemo na stepen i pomnozimo je sa pocetnim vektorom. Odnosno:

* =


Poenta zadataka gde se ovo moze primeniti je da uocimo neku rekurentnu vezu koja mora biti homogena a zatim konstruisemo matricu mnozenja (upravo sam je tako nazvao:) ).

Recimo da je rekurentna formula koju smo uocili a pocetni vektor je .

Matrica mnozenja bi izgledala ovako


Nadam se da ti je ovo pomoglo

zaista sam ti mnogo zahvalan.
Mnogo mi je pomoglo.
Skontao sam sve sto si mi napisao.

Mislim da je ovo pitanje bilo primerenije forumu za matematiku. Tamo bi dobio bogatije, detaljnije i potpunije odgovore.

Shta fali Nemanjinom odgovoru? Objasnio je choveku, svaka mu chast :)

Ne kažem da nešto fali, već samo da bi na forumu za matematiku dobio više. Javilo bi se još ljudi, dali bi još primera itd.

Ma ok je i ovo.
Nije meni forum glavni izvor informacija..
Bar ne bi trebao da bude..
Ovo me je samo malo uputilo i sasvim mi je dovoljno..
Hvala jos jednom.

Nema na cemu :)