Finden der Summe der Fibonacci-Zahlen

Question

Was der effizienteste Weg sein würde, die Summe der Fibonacci-Zahlen von F(n) zu F(m) wo F(n) und F(m) sind n-ten und mth Fibonacci-Zahlen berechnen jeweils und 0 = < n < = m (mit F (0) = 0, F (1) = 1).

Zum Beispiel, wenn n=0, m=3, müssen wir F(0)+F(1)+F(2)+F(3) finden.

Nur durch rohe Gewalt wird es lange dauern für den Bereich von n und m genannten. Wenn es über Matrix Exponentiation getan werden kann, wie?

Answer 1

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

wahrsten Sinne des Wortes, wobei die Summe des oberen Grenze m, abzüglich der Summe des unteren Grenze n.

Answer 2

Vorausgesetzt, dass "die Summe der ersten n Fibonacci-Zahlen die (n + 2) nd Fibonacci-Zahl minus 1 ist." (Danke, Wikipedia), können Sie F(m + 2) - F(n + 2) - 2 berechnen. Verwenden Sie Binet's Fibonacci number formula, um schnell F(m + 2) und F(n + 2) zu berechnen. Scheint ziemlich effizient für mich.

Update: fand einen alten SO posten, "nth fibonacci number in sublinear time" und (aufgrund der Genauigkeit als mjv und Jim Lewis haben in den Kommentaren darauf hingewiesen), you can't really escape an O(n) solution to calculate F(n).

Answer 3

Algorithmus über Matrix gefunden Eigenschaft Erklärung here und 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

Die ersten beiden Antworten (ältesten) sind scheinbar falsche mir. Gemäß dieser discussion, die bereits in einer der Antworten zitiert wird, wird durch Summe der ersten n Fibonacci-Zahlen gegeben:

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

Nun lässt m-ninklusiveSumFib(m, n) als Summe der Fibonacci-Zahlen definieren (wie benötigt von OP). Also:

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

Beachten Sie den zweiten Begriff. Es ist so, weil SumFib(m)F[m] enthält, aber wir wollen Summe von F[m] bis F[n]einschließlich. Also subtrahieren wir die Summe bis F[m-1] von der Summe bis F[n]. Einfacher Kindergarten Mathe, nicht wahr?:-)

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) 

Beispiel:

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

Und durch die Verwendung (2) oben abgeleitet:

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

---

Bonus:
Wenn m und n groß sind, benötigen Sie eine effiziente Algorithmen zur Erzeugung von Fibonacci-Zahlen. Hier ist eine sehr gute article, die eine Möglichkeit erklärt, es zu tun.

Answer 5

Die Antwort lautet:

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

Beispiel:

for n = 3 to m = 8 

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

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

Answer = 55 - 3 = 52 

nun die n-te Fibonacci in O (log N) Sie Matrix Potenzierung Methode

Link verwenden, können zu berechnen: - http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/