найти сумму чисел Фибоначчи

Question

Что будет наиболее эффективным способом для вычисления суммы чисел Фибоначчи от F(n) к F(m) где F(n) и F(m) являются п-й и MTH чисел Фибоначчи соответственно и 0 = < п < = м (с F (0) = 0, F (1) = 1).

Например, если n=0, m=3, мы должны найти F(0)+F(1)+F(2)+F(3).

Просто с грубой силой это займет много времени для диапазона n и m. Если это можно сделать с помощью экспоненции матрицы, то как?

Answer 1

F(m+2) - F(n+2) - 2 (discussion)

Буквально, сумма вашего верхней границы м, минус сумма вашего нижней границы п.

Answer 2

Учитывая, что «сумма первых n чисел Фибоначчи является (n + 2) nd числом Фибоначчи минус 1." (спасибо, Wikipedia), вы можете рассчитать F(m + 2) - F(n + 2) - 2. Используйте Binet's Fibonacci number formula для быстрого расчета F(m + 2) и F(n + 2). Кажется довольно эффективным для меня.

Update: нашел старый SO отправить, "nth fibonacci number in sublinear time", и (из-за точности как mjv и Jim Lewis указали в комментариях), you can't really escape an O(n) solution to calculate F(n).

Answer 3

Алгоритм с помощью матрицы собственности объяснения найдено here и here

class Program 
{ 
    static int FibMatrix(int n, int i, int h, int j, int k) 
    { 
     int t = 0; 

     while (n > 0) 
     { 
      if (n % 2 == 1) 
      { 
       t = j * h; 
       j = i * h + j * k + t; 
       i = i * k + t; 
      } 
      t = h * h; 
      h = 2 * k * h + t; 
      k = k * k + t; 
      n = n/2; 
     } 

     return j;    
    } 

    static int FibSum(int n, int m) 
    { 
     int sum = Program.FibMatrix(n, 1, 1, 0, 0); 

     while (n + 1 <= m) 
     { 
      sum += Program.FibMatrix(n + 1, 1, 1, 0, 0); 
      n++; 
     } 

     return sum; 
    } 

    static void Main(string[] args) 
    { 
     // Output : 4 
     Console.WriteLine(Program.FibSum(0, 4).ToString()); 

     Console.ReadLine(); 
    } 
} 

Answer 4

Первых два ответа (старых из них), казалось бы, некорректной мне. В соответствии с этим discussion, который уже цитированной в одном из ответов, сумма первых n чисел Фибоначчи определяется по формуле:

SumFib(n) = F[n+2] - 1       (1) 

Теперь, позволяет определить SumFib(m, n) как сумма чисел Фибоначчи от m до nвключительно (как требуемый OP). Итак:

SumFib(m, n) = SumFib(n) - SumFib(m-1) 

Обратите внимание на второй термин. Это потому, что SumFib(m) включает F[m], но мы хотим, чтобы сумма была от F[m] до F[n]включительно. Поэтому мы вычитаем сумму до F[m-1] от суммы до F[n]. Простые детские сады, не так ли?:-)

SumFib(m, n) = SumFib(n) - SumFib(m-1) 
      = (F[n+2] - 1) - (F[m-1 + 2] - 1) [using eq(1)] 
      = F[n+2] - 1 - F[m+1] + 1 
      = F[n+2] - F[m+1] 

Therefore, SumFib(m, n) = F[n+2] - F[m+1]     (2) 

Пример:

m = 3, n = 7 
Sum = F[3] + F[4] + F[5] + F[6] + F[7] 
    = 2 + 3 + 5 + 8 + 13 
    = 31 

И с помощью (2) Выведенная выше:

SumFib(3, 7) = F[7+2] - F[3+1] 
      = F[9] - F[4] 
      = 34 - 3 
      = 31 

---

Бонус:
Когда m и n велики, что вам нужно эфф алгоритмов генерации чисел Фибоначчи. Вот очень хороший article, который объясняет один из способов сделать это.

Answer 5

Ответ:

f(m+2)-f(n+1) 

Пример:

for n = 3 to m = 8 

Ans1 = f(m+2) = f(10) = 55 

Ans2 = f(n+1) = f(4) = 3 

Answer = 55 - 3 = 52 

Теперь рассчитать Nth Фибоначчи в O (LogN) вы можете использовать матричный метод Возведение

Ссылка: - http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/