Générateur de Fibonacci

La suite de Fibonacci est une série où chaque nombre est la somme des deux précédents : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... Nommée d'après Leonardo de Pise (Fibonacci), qui l'a introduite dans les mathématiques européennes en 1202 via son livre Liber Abaci. La suite apparaît dans la nature : la disposition en spirale des graines de tournesol, les écailles de pomme de pin, la phyllotaxie des feuilles, les coquilles de nautile et la ramification des arbres.

Le nombre d'or (φ ≈ 1,6180339887...) est la limite de F(n+1)/F(n) quand n tend vers l'infini. La valeur exacte est (1 + √5) / 2. Deux quantités sont dans le rapport doré si leur rapport est le même que le rapport de leur somme à la plus grande quantité : (a+b)/a = a/b = φ. Le nombre d'or apparaît dans la géométrie euclidienne, l'art, l'architecture (Parthénon) et fascine les mathématiciens depuis longtemps. Il est également lié au pentagone régulier et à l'icosaèdre.

Le nombre de spirales dans les tournesols, les pommes de pin et les ananas sont des nombres de Fibonacci consécutifs (typiquement 21 et 34, ou 34 et 55). Le nombre de pétales de nombreuses fleurs est un nombre de Fibonacci (3, 5, 8, 13). Les arrangements de feuilles sur les tiges suivent les fractions de Fibonacci pour maximiser l'exposition au soleil. Le modèle de population de lapins que Fibonacci a utilisé pour introduire la suite : si une paire de lapins produit une nouvelle paire chaque mois, à partir du deuxième mois, la population croît selon la suite de Fibonacci.

Récursion naïve : O(2^n) — temps exponentiel. Récursion mémoïsée ou itération : O(n). Exponentiation matricielle : O(log n). Formule de Binet en forme fermée : F(n) = (φ^n − ψ^n) / √5 où ψ = (1−√5)/2 — théoriquement O(1) mais perd en précision pour les grands n en raison des erreurs virgule flottante. Pour les grands nombres de Fibonacci exacts, utilisez l'arithmétique entière à précision arbitraire (int de Python, BigInteger de Java). F(100) a 21 chiffres ; F(1000) en a 209.

Les tas de Fibonacci (utilisés dans l'algorithme de Dijkstra), la recherche de Fibonacci (alternative à la recherche binaire), les générateurs de nombres pseudo-aléatoires, le théorème de Zeckendorf (chaque entier positif est uniquement représentable comme somme de nombres de Fibonacci non consécutifs), le codage de Fibonacci (code universel pour la compression d'entiers), la génération de niveaux aléatoires pour les listes de saut, et l'analyse des entrées dans le pire cas pour certains algorithmes comme l'algorithme PGCD d'Euclide.