Nombres pairs de Fibonacci - Correction

Nombres pairs de Fibonacci - Exercice corrigé en JavaScript

Problème :

Chaque nouveau terme de la séquence de Fibonacci est généré en ajoutant les deux termes précédents. En commençant par 1 et 2, les 10 premiers termes seront :

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

En considérant les termes de la séquence de Fibonacci dont les valeurs ne dépassent pas n, trouvez la somme des termes pairs.

Solution:

Etape 1 : Nombre de Fibonacci

Chaque nouveau terme de la séquence de Fibonacci est généré en ajoutant les deux termes précédents. En commençant par 1 et 2, les 10 premiers termes seront :
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

D'après cette explication, notre fonction de Fibonacci retourne la somme des deux termes précédent donc :

fib3 = fib2 + fib1

De plus, elle commence par 1 et 2. Donc

fib1 = 1
fib2 = 2

Ainsi, nous la fonction de Fibonacci correpondant à notre problème est :

function fibonacci(n){
  if(n <= 0) return 0;
  let fib1 = 1,
      fib2 = 2,
      fibn = 2;
  for(let i=2; i < n; i++){
    fibn = fib2 + fib1
    fib1 = fib2
    fib2 = fibn
  }
  return fibn
}

Etape 2 : La somme des termes paires

En considérant les termes de la séquence de Fibonacci dont les valeurs ne dépassent pas n, trouvez la somme des termes pairs.

On nous fait comprendre que les valeurs de la séquences de Fibonacci ne doivent pas dépasser n (le nombre dont nous souhaitons connaitre la somme de Fibonacci). En modifiant notre fonction précédente, on a:

function fiboEvenSum(n){
  if(n <= 0) return 0;
  let fib1 = 1,
      fib2 = 2,
      fibn = 2;
  for(let i=2; i < n; i++){
    if(fibn > n) break // Arrêter la boucle dès qu'une valeur dépasse n
    fibn = fib2 + fib1
    fib1 = fib2
    fib2 = fibn
  }
  return fibn
}

Maintenant, déterminons la somme des termes pairs.

function fiboEvenSum(n){
  if(n <= 0) return 0;
  let sum = 0
  let fib1 = 1,
      fib2 = 2,
      fibn = 2;
  for(let i=2; i < n; i++){
    if(fibn > n) break // Arrêter la boucle dès qu'une valeur dépasse n
    if(fibn%2==0) sum +=fibn
    fibn = fib2 + fib1
    fib1 = fib2
    fib2 = fibn
  }
  return sum
}

La ligne if(fibn%2==0) sum +=fibn est placé au dessus de la ligne fibn = fib2 + fib1 pour nous empêcher de sommer un terme impair ou supérieur à n !

Etape 3 : Optimiser le code

Maintenant que notre programme résout le problème posé, il est temps de le rendre optimal. Pour ce problème, nous allons utiliser la destructuration. Cela nous permettra de nous passer de la variable fib2 et de simplifier la taille de notre code !
De plus, nous pouvons modifier la boucle for de façon à élimer la ligne if(fibn > n) break

function fiboEvenSum(n){
  if(n <= 0) return 0;
  let sum  = 0,
  	  fib1 = 1,
      fibn = 2;
  for(let i=2; fibn < n; i++){
    if(fibn%2==0) sum +=fibn
    [fib1, fibn] = [fibn, fib1 + fibn] 
  }
  return sum
}

Pour aller plus loin !

pour exercer vos neurones, il serait intéressant d'utiliser une approche récursive pour résourdre ce problème. Toutefois, sachez que la complexité serait augmentée.

LK Core