Somme des nombres fibonacci pairs

Question

Ceci est un problème de Project Euler. Si vous ne voulez pas voir les solutions candidates, ne regardez pas ici.

Bonjour à tous! Je développe une application qui va trouver la somme de tous les termes pairs de la séquence fibonacci. Le dernier terme de cette séquence est 4 000 000. Il y a quelque chose qui ne va pas dans mon code mais je n'arrive pas à trouver le problème car cela a du sens pour moi. Pouvez-vous m'aider s'il vous plaît?

using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      long[] arr = new long [1000000] ; 
      long i= 2; 
      arr[i-2]=1; 
      arr[i-1]=2; 
      long n= arr[i]; 

      long s=0; 
      for (i=2 ; n <= 4000000; i++) 
      {      
       arr[i] = arr[(i - 1)] + arr[(i - 2)]; 
      } 
      for (long f = 0; f <= arr.Length - 1; f++) 
      { 
       if (arr[f] % 2 == 0) 
        s += arr[f]; 
      } 
      Console.Write(s); 
      Console.Read();     
     } 
    } 
} 

Answer 1

Modifier la première boucle for à ceci:

for (i = 2; arr[i - 1] < 4000000; i++) 

Answer 2

Dans cette section:

 long n= arr[i]; 

     long s=0; 
     for (i=2 ; n <= 4000000; i++) 
     { 

      arr[i] = arr[(i - 1)] + arr[(i - 2)]; 
     } 

Vous avez seulement attribué n une fois; n ne se met jamais à jour, donc votre boucle ne se terminera jamais.

n n'est pas lié à i; n est définie sur arr[2] car i était 2 à ce stade. Donc, i sera 3 à partir de la première itération de la boucle pour toujours.

Pour résoudre ce problème, une approche serait de se débarrasser de n tout à fait et rendre votre condition de boucle

for (i = 2; arr[i] <= 4000000; i++) 

Answer 3

Utilisez ceci: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

identité Troisième Cette identité a légèrement différentes formes pour Fj, selon que j est impair ou pair. La somme des premiers nombres de Fibonacci n-1, Fj, tels que j est impair, est le (2n) nombre de Fibonacci.

La somme des nombres premiers n Fibonacci, Fj, tel que j est pair, est la (2n + 1) ième nombre de Fibonacci moins 1.

[16]

Le seul problème est potentiel perte de précision lorsque vous augmentez phi à la (2n + 1) e puissance.

Answer 4

essayez ceci (et l'utiliser pour vos grands besoins en entier: http://intx.codeplex.com/Wikipage):

using System; 
using System.Collections; 
using System.Linq; 
using System.Collections.Generic; 

using Oyster.Math; 

namespace Application 
{ 


public class Test 
{ 

    public static void Main() 
    {  
     IntX even = 0; 
     Console.WriteLine("Sum of even fibonacci {0}\n", 
      Fibonacci(20).Where(x => x % 2 == 0).Sum()); 
     Console.WriteLine("Sum of odd fibonacci {0}", 
      Fibonacci(20).Where(x => x % 2 == 1).Sum()); 

     Console.Write("\nFibonacci samples"); 
     foreach (IntX i in Fibonacci(20)) 
      Console.Write(" {0}", i); 

     Console.ReadLine(); 

    } 

    public static IEnumerable<IntX> Fibonacci(int range) 
    { 
     int i = 0; 

     IntX very = 0;  
     yield return very; 
     ++i; 

     IntX old = 1;  
     yield return old; 
     ++i; 

     IntX fib = 0; 
     while (i < range) 
     { 
      fib = very + old; 
      yield return fib; 
      ++i; 

      very = old; 
      old = fib;     
     } 

    } 
} 


public static class Helper 
{ 
    public static IntX Sum(this IEnumerable<IntX> v) 
    { 
     int s = 0; 
     foreach (int i in v) s += i; 
     return s; 
    } 
} 

} 

Exemple de sortie:

Sum of even fibonacci 3382 

Sum of odd fibonacci 7563 

Fibonacci samples 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 

Answer 5

Je vais admettre que je le ferais entièrement différemment. J'utiliserais probablement la séquence appariée des nombres de Lucas et de Fibonacci, plus les formules simples

F (n + a) = (F (a) * L (n) + L (a) * F (n))/2

L (n + a) = (5 * F (a) * F (n) + L (a) * L (n))/2

Notez que seulement chaque troisième nombre de Fibonacci est encore .Donc, puisque F (3) = 2 et L (3) = 4, nous obtenons

F (n + 3) = L (n) + 2 * F (n)

L (n + 3) = 5 * F (n) + 2 * L (n)

Maintenant il suffit de faire la somme des termes. (Edit: Il existe une solution encore plus simple, qui repose sur une certaine sophistication mathématique pour dériver, ou une certaine connaissance de la séquence et des identités de Fibonacci pour cette séquence, ou peut-être une recherche dans l'encyclopédie de séquences entières. Malheureusement, plus que cette indication ne semble pas appropriée pour un problème d'EP, je vais donc laisser cette solution dans les marges de cette note, donc la somme des premiers k nombres de Fibonacci est ...)