Série Fibonacci en Java

1. Vue d'ensemble

Dans ce didacticiel, nous examinerons la série Fibonacci.

Plus précisément, nous allons implémenter trois façons de calculer le nième terme de la série de Fibonacci, la dernière étant une solution à temps constant.

2. Série Fibonacci

La série de Fibonacci est une série de nombres dans laquelle chaque terme est la somme des deux termes précédents . Ses deux premiers termes sont 0 et 1 .

Par exemple, les 11 premiers termes de la série sont 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 et 55 .

En termes mathématiques, la séquence S n des nombres de Fibonacci est définie par la relation de récurrence:

S(n) = S(n-1) + S(n-2), with S(0) = 0 and S(1) = 1

Voyons maintenant comment calculer le nième terme de la série de Fibonacci. Les trois méthodes sur lesquelles nous allons nous concentrer sont récursives, itératives et utilisant la formule de Binet.

2.1. Méthode récursive

Pour notre première solution, exprimons simplement la relation de récurrence directement en Java:

public static int nthFibonacciTerm(int n) { if (n == 1 || n == 0) { return n; } return nthFibonacciTerm(n-1) + nthFibonacciTerm(n-2); }

Comme nous pouvons le voir, nous vérifions si n est égal à 0 ou 1. Si c'est vrai, nous retournons cette valeur. Dans tous les autres cas, nous appelons récursivement la fonction pour calculer le (n-1) ème terme et le (n-2) ème terme et renvoyer leur somme.

Bien que la méthode récursive soit simple à implémenter, nous voyons que cette méthode fait beaucoup de calculs répétés. Par exemple, afin de calculer le 6e terme, nous faisons des appels pour calculer le 5e et le 4e terme. De plus, l'appel au calcul du 5e terme appelle à recalculer le 4e terme. De ce fait, la méthode récursive fait beaucoup de travail redondant.

Il s'avère que cela rend sa complexité temporelle exponentielle; O (Φn) pour être exact.

2.2. Méthode itérative

Dans la méthode itérative, nous pouvons éviter les calculs répétés effectués dans la méthode récursive. Au lieu de cela, nous calculons les termes de la série et stockons les deux termes précédents pour calculer le suivant.

Jetons un coup d'œil à sa mise en œuvre:

public static int nthFibonacciTerm(int n) { if(n == 0 || n == 1) { return n; } int n0 = 0, n1 = 1; int tempNthTerm; for (int i = 2; i <= n; i++) { tempNthTerm = n0 + n1; n0 = n1; n1 = tempNthTerm; } return n1; }

Tout d'abord, nous vérifions si le terme à calculer est le 0e terme ou le 1er terme. Si tel est le cas, nous renvoyons les valeurs initiales. Sinon, nous calculons le 2ème terme en utilisant n0 et n1 . Ensuite, nous modifions les valeurs des variables n0 et n1 pour stocker respectivement le 1er et le 2ème terme. Nous continuons à itérer jusqu'à ce que nous ayons calculé le terme requis.

La méthode itérative évite les travaux répétitifs en stockant les deux derniers termes de Fibonacci dans des variables. La complexité temporelle et spatiale de la méthode itérative est respectivement O (n) et O (1) .

2.3. La formule de Binet

Nous n'avons défini le nième nombre de Fibonacci qu'en fonction des deux précédents. Maintenant, nous allons regarder la formule de Binet pour calculer le nième nombre de Fibonacci en temps constant.

Les termes de Fibonacci maintiennent un rapport appelé nombre d' or noté Φ , le caractère grec prononcé «phi» .

Voyons d'abord comment le nombre d' or est calculé:

Φ = ( 1 + √5 )/2 = 1.6180339887...

Maintenant, regardons la formule de Binet :

Sn = Φⁿ–(– Φ⁻ⁿ)/√5

En fait, cela signifie que nous devrions être en mesure d'obtenir le nième nombre de Fibonacci avec juste un peu d'arithmétique.

Exprimons cela en Java:

public static int nthFibonacciTerm(int n) { double squareRootOf5 = Math.sqrt(5); double phi = (1 + squareRootOf5)/2; int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5); return nthTerm; }

Nous calculons d'abord le squareRootof5 et phi et les stockons dans des variables. Plus tard, nous appliquons la formule de Binet pour obtenir le terme requis.

Puisque nous avons affaire à des nombres irrationnels ici, nous n'obtiendrons qu'une approximation. Par conséquent, nous devrons conserver plus de décimales pour les nombres de Fibonacci plus élevés afin de tenir compte de l'erreur d'arrondi.

On voit que la méthode ci-dessus calcule le nième terme de Fibonacci en temps constant, ou O (1).

3. Conclusion

Dans ce bref article, nous avons examiné la série Fibonacci. Nous avons examiné une solution récursive et itérative. Ensuite, nous avons appliqué la formule de Binet pour créer une solution à temps constant.

Comme toujours, le code source complet des exemples de travail est disponible à l'adresse over sur GitHub.