Qu'est-ce que la Somme de Même des Termes De Fibonacci (<4 millions)? [Grande Valeur De Type De Données De La Confusion]

Pour plus de sécurité, utiliser le "long" type de données, la norme exige que pour tenir au moins 4 milliards de dollars, mais sur la plupart des machines, 'int' organisera également des 4 milliards de dollars.

enum { MAX_VALUE = 4000000 };
int sum  = 0;
int f_n0 = 0;
int f_n1 = 1;
int f_n2;

while ((f_n2 = f_n0 + f_n1) < MAX_VALUE)
{
    if (f_n2 % 2 == 0)
        sum += f_n2;
    f_n0 = f_n1;
    f_n1 = f_n2;
}
printf("%d\n", sum);

OriginalL'auteur Jonathan Leffler

Je ne suis pas un programmeur, mais voici une adaptation de Leffler du code sans le SI-critère. Il doit travailler pour MAX_VALUES au-dessus de 2 (donné qu'il n'existe pas d'erreurs dans la syntaxe de programmation), basé sur un modèle que j'ai trouvé dans le même-seulement la suite de fibonacci: 0,2,8,34,144,610,2584... donc il est intéressant de noter: f_n2 = 4*f_n1 + f_n0. Cela signifie aussi ce programme a besoin seulement de 1/3ème de calculs, car il n'a même pas envisager/calculer l'impair de nombres de fibonacci.

enum { MAX_VALUE = 4000000 };
int sum  = 2;
int f_n0 = 0;
int f_n1 = 2;
int f_n2 = 8;

while (f_n2 < MAX_VALUE)
{
    sum += f_n2;
    f_n0 = f_n1;
    f_n1 = f_n2;
    f_n2 = 4*f_n1 + f_n0;
}
printf("%d\n", sum);

OriginalL'auteur user12656

Utilisation BigInt.

Puis de nouveau, unsigned int stocke les valeurs jusqu'à plus de 4 milliards de dollars, de sorte que vous ne devriez pas avoir de problèmes, même avec "la somme de tous les nombres de fibonacci jusqu'à 4 millions de dollars" (ce qui, évidemment, doit être de moins de 8 mil)?

OriginalL'auteur Dunya Degirmenci

Votre programme imprime F_1 + ..+ F_limit et pas F_1 + ... F_n avec F_n < limite comme vous l'avez décrit.

Vérifier l'article de Wikipédia sur Nombres De Fibonacci et Sloane A000045: la suite de Fibonacci croît de façon exponentielle. La vérification de cette table F_48 = 4807526976 qui dépasse int. F_100 est 354224848179261915075 qui a certainement déborde même int64_t (la pile n'est pas, cependant).

OriginalL'auteur Alexandru

Une drôle de solution est d'utiliser la forme fermée pour les séquences de Fibonacci et la forme fermée pour les progressions géométriques. La fin de la solution ressemble à ceci:

  sum = ( (1-pow(phi_cb, N+1)) / (1-phi_cb) - (1-pow(onephi_cb,N+1)) / (1-onephi_cb)) / sqrt(5);

où

  double phi       = 0.5 + 0.5 * sqrt(5);
  double phi_cb    = pow(phi, 3.0);
  double onephi_cb = pow(1.0 - phi, 3.0);
  unsigned N = floor( log(4000000.0 * sqrt(5) + 0.5) / log(phi) );
  N = N / 3;

avec toutes les mises en garde concernant le double, int-conversions de type de cours.

OriginalL'auteur micans

Voici mon programme:

#include <iostream>

long int even_sum_fibonacci(int n){
    int i = 8;
    int previous_i = 2;
    int next_i = 0;
    long int sum = previous_i + i;;
    while(n>next_i){
        next_i = i*4 + previous_i;
        previous_i = i;
        i = next_i;
        sum = sum + i;
    }
    return sum - next_i; //now next_i and i are both the bigger number which
                         //exceeds 4 million, but we counted next_i into sum
                         //so we'll need to substract it from sum
}



int main()
{
   std::cout << even_sum_fibonacci(4000000) << std::endl; 

   return 0;
}

Parce que si vous regardez la suite de fibonacci (lors de la première quelques-uns même des numéros)
2 8 34 144 610 2584 ... vous verrez qu'il correspond au modèle que
next_number = current_number * 4 + previous_number.

C'est l'une des solutions. Si le résultat est 4613732

OriginalL'auteur anicicn

Vous pouvez utiliser le code ci-dessus.

import numpy as np
M = [[0,1],[1,1]]
F = [[0],[1]]
s = 0
while(F[1][0] < 4000000):
 F = np.matmul(M, F)
 if not F[0][0]%2:
   s+=F[0][0]

print(s)

Nous pouvons faire mieux que cela en O(log n) fois. En outre, une 2 × 2 de la matrice et d'un vecteur à deux dimensions peuvent être multipliés à nouveau en O(1) fois. Donc il suffit de calculer Mⁿ.
Le récursive de l'algorithme calcule Mⁿ

1. Si n = 0, retour I₂
2. Si n = 1, le retour de M.
3. Si n = 2m.
4. De façon récursive de calcul N = M^m, et P = N².
5. Si n = 2m+1, P = PM.
6. Retour P.
   Nous avons T(n) = T(n/2) + O(1), et par le maître du théorème T(n) = O(log n)

Vous pouvez également utiliser la récurrence de Même de la suite de Fibonacci est:
EFn = 4EFn-1 + EFn-2
avec des valeurs de départ
EF0 = 0 et EF1 = 2.

OriginalL'auteur danish_imam