Zaprojektuj algorytm

Question

Witam,
Jestem nowym użytkownikiem na forum i z góry przepraszam jeżeli moje zadanie powędrowało do złego działu. 
Oto one:

Z góry dziękuję za każdą wskazówkę!

Comments

Po co algorytm O(log n), skoro można w O(1)? 

https://www.wolframalpha.com/input/?i=g%28n%29%3Dg%28n-1%29%2Bg%28n-2%29%2Bg%28n-3%29%2C+g%280%29%3D0%2C+g%281%29%3D1%2C+g%282%29%3D1

Answer 1

Krótko poszukałem w Google'ach i znalazłem rozwiązanie z potęgowaniem macierzy. Tutaj jest wyjaśnione wszystko krok po kroku (po angielsku).