Mam orzec czy dana liczba z podanego przedziału jest elementem ciągu fibonacciego, jak zrobić to najwydajniej? Mam pomysł aby zapisać do tablicy wyniki ciągu fib. Mam sprawdzać czy dana liczba jest elementem z przedziału od 5 do 100. Puścić funkcje która zapisze w tablicy wyniki dla fib od 5 do 11. Potem funkcja która sprawdza czy w tej tablicy jet dana liczba czy nie. Jak to zrobić lepiej?
0
0
Najwydajniej było by chyba skorzystać ze wzoru ogólnego. Możliwe jednak, że byłby problem z niedokładnością liczb zmiennoprzecinkowych.
Ewentualnie, przy niewielkich przedziale liczb, które mają być sprawdzane można stworzyć lookup table z wartościami boolowskimi, czy dana liczba jest wyrazem ciągu, czy nie.
Oba te sposoby powinny mieć złożoność O(1), ale drugi ma duże zapotrzebowanie pamięciowe.
0
Ja bym zrobił to tak:
Zrobić ciąg fibonnaciego i sprawdzać czy wynik jest równy tej liczbie jeżeli tak to wypisać że jest równa i przy okazji możesz wypisać dla której liczby ciągu fibonnaciego jest równa. Jest to wg. Mnie szybsza metoda ponieważ nie korzystasz z tablic masz tylko zmienna dana, ciągu fibonnaciego oraz wynik, oraz nie liczysz tego ciągu co już jest niepotrzebne.
0
Zdecydowanie najlepiej jest stworzyć tablicę z kolejnymi liczbami fibbonaciego i wyszukiwać binarnie, czy podana liczba w niej występuje. Ciąg fibbonaciego jest dosyć szybko rosnący, więc zużycie pamięci w tym przypadku nie ma znaczenia.
http://www.wolframalpha.com/input/?i=solve+fib%28n%29+%3E+2^64