Encontrar la suma de los números de Fibonacci

Question

¿Cuál sería la forma más eficiente para calcular la suma de los números de Fibonacci de F(n) a F(m) donde F(n) y F(m) son enésima y mth números de Fibonacci, respectivamente, y 0 = < n < = m (con F (0) = 0, F (1) = 1).

Por ejemplo, si n=0, m=3, necesitamos encontrar F(0)+F(1)+F(2)+F(3).

Solo por fuerza bruta tardará mucho tiempo para el rango de n y m mencionado. Si se puede hacer a través de la exponenciación de la matriz, entonces, ¿cómo?

Answer 1

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

Literalmente, la suma de su m cota superior, menos la suma de su límite inferior n.

Answer 2

Dado que "la suma de los primeros n números de Fibonacci es el (n + 2) nd número de Fibonacci menos 1". (gracias, Wikipedia), puede calcular F(m + 2) - F(n + 2) - 2. Use Binet's Fibonacci number formula para calcular rápidamente F(m + 2) y F(n + 2). Me parece bastante eficiente.

Actualización: encontrado un viejo SO Post, "nth fibonacci number in sublinear time", y (debido a la precisión como mjv y Jim Lewis han señalado en los comentarios), you can't really escape an O(n) solution to calculate F(n).

Answer 3

algoritmo a través de la matriz explicación propiedad encontró here y 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

Las primeras dos respuestas (las más antiguas) son aparentemente incorrecta a mí. De acuerdo con este discussion que ya se cita en una de las respuestas, la suma de los primeros n números de Fibonacci viene dada por:

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

Ahora, vamos a definir SumFib(m, n) como la suma de los números de Fibonacci m-nincluido (como se requerido por OP). Entonces:

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

Tenga en cuenta el segundo término. Es así porque SumFib(m) incluye F[m], pero queremos suma de F[m] a F[n]inclusive. Así que restamos suma hasta F[m-1] de suma hasta F[n]. Las matemáticas simples de kínder, ¿no?:-)

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) 

Ejemplo:

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

Y mediante el uso (2) derivado anteriormente:

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

---

Bono:
Cuando m y n son grandes, es necesario eficiente algoritmos para generar números de Fibonacci. Aquí hay una muy buena article que explica una forma de hacerlo.

Answer 5

La respuesta es:

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

Ejemplo:

for n = 3 to m = 8 

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

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

Answer = 55 - 3 = 52 

Ahora para calcular el Fibonacci N-ésimo en O (logN) puede utilizar el método Exponenciación matriz

Link: - http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/