Последовательность Фибоначчи быстрее, но с разными начальными числами (F [n] = F [n-1] + F [n-2]) - PullRequest
Новая
       39

Последовательность Фибоначчи быстрее, но с разными начальными числами (F [n] = F [n-1] + F [n-2])

0 голосов
/ 20 мая 2018

(здесь новичок)

Я хочу знать, как найти n-й номер последовательности F [n] = F [n-1] + F [n-2].

Ввод: 

F[0] =  a;
F[1] =  b;
a,b < 101
N < 1000000001 
M < 8; M=10^M;

a и b - начальные порядковые номера.

n - это n-й номер последовательности, которую мне нужно найти.

M по модулю, число быстро становится очень большим, поэтому F [n] = F [n]% 10 ^ M, мы находим остаток, потому что нужны только последние цифры n-го числа

Рекурсивный подход слишком медленный: 

int fib(int n)
{
   if (n <= 1)
      return n;
   return fib(n-1) + fib(n-2);
}

Решение динамического программирования, которое занимает время O (n), также слишком медленное: 

f[i] = f[i-1] + f[i-2];

Хотя есть решения о том, как найти n-й номер быстрее, если первые числа последовательности равны 0 и 1 (n-й номер можно найти в O (log n)), используя следующую формулу: 

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

(ссылка на формулу и реализацию кодас этим: https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)

Но эта формула не работает, если начальные числа что-то вроде 25 и 60. И рекурсивный подход слишком медленный.

Поэтому я хочу знать, как я могунайдите n-й номер последовательности быстрее, чем O (n). Неполный код будет полезен.

Спасибо.

1 Ответ

0 голосов
/ 20 мая 2018

Эта матрица: 

A = / 1  1 \
    \ 1  0 /

При умножении на вектор столбца (f n + 1 , f n ), где f n - это n-е число в последовательности Фибоначчи, которое даст вам вектор столбца (f n + 2 , f n + 1 ), то есть оно продвинет вас на один шаг вперед.Это работает независимо от того, какими были начальные элементы последовательности.

Например: 

/ 1  1 \ / 8 \  =  / 13 \
\ 1  0 / \ 5 /     \ 8  /

Таким образом, n-е число Фибоначчи является первым элементом A n-1 v, где v - вектор-столбец, содержащий f 1 и f 0 , первые два числа в вашей последовательности.

Поэтому, если вы можете быстро вычислить A n-1 по модулю некоторого числа, это даст вам f n .Это можно сделать, используя Вычисление в квадрате , которое работает в O (logn).Просто убедитесь, что выполняете модуль по модулю после каждого умножения и сложения, чтобы числа не становились слишком большими.

...