Imprimer les n premiers nombres de Fibonacci en utilisant la formule directe

Dans cet article, nous allons résoudre le problème de l'impression des n premiers nombres de Fibonacci en utilisant une formule directe.

En mathématiques, les nombres de Fibonacci sont souvent représentés par Fn (pour le nième nombre de Fibonacci), formant une séquence dans laquelle chaque nombre est égal à la somme des deux nombres précédents. Le nième nombre de Fibonacci peut être exprimé comme suit -

$$mathrm{Fn:=:F_{n-1}:+:F_{n-2}}$$

La série commence par 0 et 1. Les premières valeurs de la séquence de Fibonacci commençant par 0 et 1 sont -

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

Donc, dans ce problème, on nous donnera un nombre N et nous devons imprimer les N premiers nombres de Fibonacci en utilisant la formule directe.

Exemple

Entrez  : 4

Sortie : 0 1 1 2

Entrez  : 8

Sortie : 0 1 1 2 3 5 8 13

Pour cette question, nous devons comprendre le concept de la formule de Binet, qui donne une formule directe pour obtenir le nième nombre de Fibonacci, qui sera discutée en détail dans la section algorithme.

Algorithme

Selon la formule $mathrm{Fn:=:F_{n-1}:+:F_{n-2}}$ nous avons besoin du (n-1)ème élément et du (n- 2)ème et ajoutez-les à obtenez le nième élément. Parce que dans ce problème, nous devrions imprimer les n premiers nombres de Fibonacci en utilisant une formule directe pour obtenir le nième nombre de Fibonacci.

Pour obtenir le nième nombre de Fibonacci dans la séquence de Fibonacci, vous pouvez appliquer une formule explicite appelée Formule de Binet. Il a été créé par le mathématicien Jacques Philippe Marie Binet.

Formule

Si $mathrm{Fn}$ représente le nième nombre de Fibonacci dans la séquence de Fibonacci, il peut être exprimé comme

$$mathrm{F_n:=:frac{1}{sqrt5}((frac{1+{sqrt5}}{2})^n:-:(frac{ 1-{sqrt5}}{2})^n )}$$

REMARQUE - Cette formule donne la séquence de Fibonacci commençant par 1 et 1. Pour obtenir la séquence de Fibonacci commençant à 0 et 1, utilisez n-1 pour obtenir le nième nombre de Fibonacci.

Nous pouvons dériver cette formule en utilisant le concept d'équations quadratiques. Nous utiliserons cette formule pour imprimer chaque nombre de Fibonacci jusqu'au nième nombre de Fibonacci pour imprimer les n premiers nombres de Fibonacci.

Méthode

• Nous utiliserons une boucle for pour imprimer tous les N nombres de Fibonacci de 0 à n itérations puisque nous considérons la séquence de Fibonacci commençant par 0 et 1.

• Initialisez la variable avec un nombre de Fibonacci et stockez le i-ème nombre de Fibonacci en utilisant la formule ci-dessus à chaque itération jusqu'à ce que i

• Continuez à imprimer les nombres de Fibonacci à chaque itération, ce qui nous donnera les N premiers nombres de Fibonacci.

Exemple

Ce qui suit est l'implémentation de la méthode ci-dessus en C++ -

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void fibonacci(long long int N){ //function to print first N fibonacci numbers
   long long int fibonacci; //to store ith fibonacci number
   
   for(int i=0;i<N;i++) { //using for loop to print all N fibonacci numbers
      //using direct formula to print every fibonacci number until n
      fibonacci = 1/sqrt(5)*(pow((1+sqrt(5))/2,i) - (pow((1-sqrt(5))/2,i)));
      cout<<fibonacci<<" ";
   }
   cout<<endl;
}

//Driver Code
int main(){
   long long int N=10;
   fibonacci(N);
   N=6;
   fibonacci(N);
   return 0;
}

Sortie

0 1 1 2 3 5 8 13 21 34
0 1 1 2 3 5

Complexité temporelle : O(n), car la boucle for s'exécute jusqu'à ce que i soit inférieur à n.

Complexité spatiale : O(1), car il n'utilise aucun espace supplémentaire.

Conclusion

Dans cet article, nous avons appris à imprimer les N premiers nombres de Fibonacci en utilisant une formule directe au lieu d'utiliser la récursion. Nous avons également appris la formule de Binet, qui permet d'obtenir directement le nième nombre de Fibonacci dans la séquence de Fibonacci.

J'espère que cet article vous a aidé à clarifier tous les concepts sur ce sujet.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!