Reszta z dzielenia wyrazu ciągu Fibonacciego

max · Post autor: **max** » 18 paź 2006, o 16:54

Niech F(n) będzie n-tym wyrazem ciągu Fibonacciego. Wyznacz:
r = F(n) mod k,
nie obliczając wartości F(n).

Interesuje mnie nawet kwestia czy jest to w ogóle możliwe...
(Jeśli wg Moderatorów problem bardziej pasuje do analizy to przepraszam i proszę o przeniesienie go tamże)

Spykaj · Post autor: **Spykaj** » 20 paź 2006, o 21:49

Na tej opsssesji jest zadanie "Licytacja" w którym musisz własnie takie coś rozwiązać na komputerze i powiem ci, że to jest możliwe, a nawet bardzo proste potęgowanie macierzy i te sprawy, zobacz se wzór na wikipedi pod hasłem Ciąg Fibonacciego.

aktualny konkurs...

max · Post autor: **max** » 20 paź 2006, o 22:57

Widziałem wzór na wikipedii, ale do tego trzeba coś koło lg(n) operacji (w sumie niedużo, jakbym miał czas na szukanie błędów w mojej implementacji to zmieściłoby się w konkursowym limicie czasu...).

Mnie zaintereswało, czy możliwym jest wyznaczenie F(n) mod k w czasie stałym (to by było ciekawe Coś - nieprawdaż? )

W każdym razie dzięki za zainteresowanie
Pozdrawiam

Spykaj · Post autor: **Spykaj** » 21 paź 2006, o 19:14

Zauważ też, że ciąg fibonacciego modulo jakieś k po jakimś czasie zacznie się powtarzać, np. modulo 2:
1,1,0,1,1,0,1,1,0
czy modulo 3
1,1,2,0,2,2,1,0,1,1
czyli jak chcesz znaleźć fib(n)%k, wystarczy mieć tyle liczb, ile jest do pierwszego zapętlenia, no ale nie wiem czy dla dużych wartości k opłaca się szukać w ten sposób...

Szybkie potęgowanie to tylko logarytmiczna liczba mnożeń, na pewno lepszy sposób!

max · Post autor: **max** » 21 paź 2006, o 20:45

Nie opłaca się. , o ktorym piszesz, dla liczby k może wynosić do 6k, więc przy k rzędu \(\displaystyle{ 2^{31} - 1}\)... sam rozumiesz...