ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      26 Jul 2001  22:44:26
 To : Serge Kanilo
 Subject : Числа фибоначи
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Serge Kanilo to All:
 
  SK> Побаловался немного с числами Фибоначи и сделал алгоритмик
  SK> сложности ln(N) для поиска N-го числа Фибоначи.
  SK> Известен ли подобный алгоритм в литературе?
  SK> Hе очень сложно, но в инете никаких ссылок на подобное не нашел.
 
 Это ничего не значит.
 Пусть F(0) = 1, F(1) = 1, ..., F(n) = F(n-1) + F(n-2), ... - последовательность 
 Фибоначчи. Доопределим F(-1)=0. Тогда для всех натуральных n справедливо
 следующее матричное соотношение:
 
                                n
  / F(n)   F(n-1) \     / 1 1 \ 
 (                 ) = (       )
  \ F(n-1) F(n-2) /     \ 1 0 /
 
 Используешь дихотомичное возведение в степень и получаешь как раз сложность
 порядка ln(n).
 Это всего лишь один из возможных способов.
 
  SK> Обычно считают в лоб.
 
 Кто тебе такую глупость сказал?
 
 Regards,      ш.ш
         Max    ~
 
 --- OS/2 Uptime:  0d 6h 45m 38s 937ms
  * Origin: Bugs come in through open Windows. (2:5015/60)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Числа фибоначи   Serge Kanilo   26 Jul 2001 18:46:05   Числа фибоначи   Max Alekseyev   26 Jul 2001 22:44:26   Re: Числа фибоначи   Serge Kanilo   27 Jul 2001 01:46:54   Re: Числа фибоначи   Serge Kanilo   27 Jul 2001 01:54:59   Re: Числа фибоначи   Maxim Korshunov   28 Jul 2001 16:47:19