Problème #2 du project Euler

Mona Lisa and Fibonacci
Michæl Paukner

« Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. »

Afin de résoudre ce problème du projet Euler, il est important, dans un premier temps, de se consacrer à l’appréhension de ce que ce sont les séquences Fibonacci. En mathématiques, la séquence Fibonacci se définit comme une séquence dans laquelle chaque nombre est obtenu en effectuant la somme des deux termes précédents.

La formule mathématique associée est donc la suivante : F(n) = F(n-1) + F(n-2) avec F(0) = 0 et F(1) = 1. On appelle F(0) et F(1) les termes initiaux de cette suite logique, ceux qui permettent d’en déduire les nombres suivants. Les nombres Fibonacci constituent la séquence A000045 sur The On-line Encyclopedia of Integer Sequences. Ci-dessous sont représentés les vingt premiers termes de la séquence Fibonacci.

F(0) F(1) F(2) F(3) F(4)
0 1 1 2 3
F(5) F(6) F(7) F(8) F(9)
5 8 13 21 34
F(10) F(11) F(12) F(13) F(14)
55 89 144 233 377
F(15) F(16) F(17) F(18) F(19)
610 987 1 597 2 584 4 181

L’énoncé du problème #2 du projet Euler nous propose de trouver la somme de toutes les valeurs paires n’excédant pas 4 000 000. Il s’agit donc de considérer la séquence Fibonacci, de telle sorte qu’à chaque nouveau terme étant pair, celui-ci est ajouté à une variable sum, dont la valeur ne cessera d’augmenter que lorsque l’on aura atteint la limite proposée, égale à 4 000 000.

Les deux termes initiaux de la séquence Fibonacci sont représentés ci-dessous par les variables x et y respectivement égales à 0 et à 1. Ces variables possèdent une valeur croissante dans le temps à la condition que la variable y, représentant systématiquement le deuxième terme à un instant t, ne dépasse jamais la limite imposée. Une variable intermédiaire temp calcule le troisième terme créé à partir de la somme de x et y. x, premier terme de la séquence à un instant t, devient alors égal à y, qui lui-même prend la valeur de temp. À chaque nouvelle itération, on ajoute à la variable sum la valeur de la variable y si celle-ci est paire.

function problem2(){
  var limit = 4000000,
      sum = 0,
      x = 0,
      y = 1;

  while(y < limit){
    if(y%2==0) sum += y;
    var temp = x + y;
    x = y;
    y = temp;
  }
  return sum;
}

problem2();

En clair, lors de la première itération de cette boucle, on a : x = F(0) et y = F(1). temp représente d'abord F(2) et est donc égal à F(0) + F(1), soit x +y. x prend ensuite la valeur de y donc x = F(1) = 1 ; y prend la valeur de temp donc y = F(2) = 1.

Lors de la deuxième itération de la boucle, on a donc : x = F(1) et y = F(2). temp va représenter F(3), et donc être égal à F(1) + F(2), soit x +y. x prend ensuite la valeur de y donc x = F(2) = 1 ; y prend la valeur de temp donc y = F(3) = 2.

À la troisième itération de cette boucle, y étant égal à 2, chiffre pair, sera ajouté à sum. Et ainsi de suite, jusqu'à ce que y dépasse 4 000 000.

La fonction présente ci-dessus s'exécute en 0.12 milliseconde.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *