On retrouve le Nième nombre de Fibonacci de trois manières en un temps raisonnable : les bases de la programmation dynamique. Nombres de Fibonacci : boucle et récursion Récursion de Fibonacci c

Très souvent, lors de diverses olympiades, des problèmes comme celui-ci surviennent, qui, à première vue, peuvent être résolus à l'aide d'une simple recherche. Mais si on compte le nombre options possibles, alors on sera immédiatement convaincu de l'inefficacité de cette approche : par exemple, la fonction récursive simple donnée ci-dessous consommera déjà des ressources importantes au 30ème nombre de Fibonacci, alors que dans les Olympiades, le temps de résolution est souvent limité à 1-5 secondes .

Int fibo (int n) (if (n == 1 || n == 2) (retour 1;) else (retour fibo (n - 1) + fibo (n - 2);))

Réfléchissons à pourquoi cela se produit. Par exemple, pour calculer fibo (30), on calcule d'abord fibo (29) et fibo (28). Mais en même temps, notre programme "oublie" que fibo (28) nous déjà compris lors de la recherche de fibo (29).

La principale erreur de cette approche "frontale" est que les mêmes valeurs des arguments de la fonction sont calculées plusieurs fois - et ce sont des opérations très gourmandes en ressources. Pour se débarrasser des calculs répétitifs, la méthode va nous aider programmation dynamique- il s'agit d'une technique, lors de son utilisation, le problème est divisé en sous-tâches générales et répétitives, dont chacune n'est résolue qu'une seule fois - cela augmente considérablement l'efficacité du programme. Cette méthode est décrite en détail dans, il existe également des exemples de résolution d'autres problèmes.

Le moyen le plus simple d'améliorer notre fonction est de se souvenir des valeurs que nous avons déjà calculées. Pour ce faire, nous devons introduire un tableau supplémentaire, qui servira en quelque sorte de "cache" pour nos calculs : avant de calculer une nouvelle valeur, nous vérifierons si nous l'avons déjà calculé. Si nous avons calculé, nous prendrons la valeur finie du tableau, et si nous ne l'avons pas calculée, nous devrons la calculer en fonction des précédentes et la mémoriser pour l'avenir :

Cache entier ; int fibo (int n) (if (cache [n] == 0) (if (n == 1 || n == 2) (cache [n] = 1;) else (cache [n] = fibo (n - 1) + fibo (n - 2);)) cache de retour [n];)

Étant donné que dans cette tâche, pour calculer la Nième valeur, nous avons la garantie d'avoir besoin de (N-1) -ième, il ne sera pas difficile de réécrire la formule sous forme itérative - nous allons simplement remplir notre tableau d'affilée jusqu'à ce que nous atteignions le cellule souhaitée :

<= n; i++) { cache[i] = cache + cache; } cout << cache;

Maintenant, nous pouvons remarquer que lorsque nous calculons la valeur de F (N), alors la valeur de F (N-3) nous est déjà garantie jamais n'aura pas besoin. C'est-à-dire que nous n'avons besoin de stocker que deux valeurs en mémoire - F (N-1) et F (N-2). De plus, dès que l'on a calculé F (N), le stockage de F (N-2) perd tout sens. Essayons d'écrire ces pensées sous forme de code :

// Deux valeurs précédentes : int cache1 = 1; int cache2 = 1 ; // Nouvelle valeur int cache3; pour (int i = 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>Après itération, cache2 perdra sa pertinence, c'est-à-dire il devrait devenir cache1 // En d'autres termes, cache1 - f (n-2), cache2 - f (n-1), cache3 - f (n). // Soit N = n + 1 (le nombre que l'on calcule à l'itération suivante). Alors n-2 = N-3, n-1 = N-2, n = N-1. // Conformément aux nouvelles réalités, nous réécrivons les valeurs de nos variables : cache1 = cache2; cache2 = cache3; ) cout<< cache3;

Un programmeur expérimenté comprend que le code ci-dessus est, en général, un non-sens, puisque le cache3 n'est jamais utilisé (il est immédiatement écrit dans le cache2), et l'itération entière peut être réécrite en utilisant une seule expression :

Cache = 1 ; cache = 1 ; pour (int i = 2; i<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;

Pour ceux qui ne peuvent pas comprendre comment fonctionne la magie avec le reste de la division, ou qui veulent simplement voir une formule plus non évidente, il existe une autre solution :

Int x = 1 ; entier y = 1; pour (int i = 2; i< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;

Essayez de suivre l'exécution de ce programme : vous serez convaincu de la justesse de l'algorithme.

P.S. En général, il existe une seule formule pour calculer tout nombre de Fibonacci qui ne nécessite aucune itération ou récursivité :

Const double SQRT5 = sqrt (5) ; const double PHI = (SQRT5 + 1) / 2; int fibo (int n) (retour int (pow (PHI, n) / SQRT5 + 0.5);)

Mais, comme vous pouvez le deviner, le hic, c'est que le coût du calcul des puissances des non-entiers est assez élevé, tout comme leur erreur.

nombres de Fibonacci Est une suite de nombres dans laquelle chaque nombre suivant est égal à la somme des deux précédents : 1, 1, 2, 3, 5, 8, 13, .... Parfois la ligne commence à zéro : 0, 1, 1, 2, 3, 5, .... Dans ce cas, nous nous en tiendrons à la première option.

Formule:

F 1 = 1
F 2 = 1
Fn = Fn-1 + Fn-2

Exemple de calcul :

F 3 = F 2 + F 1 = 1 + 1 = 2
F 4 = F 3 + F 2 = 2 + 1 = 3
F 5 = F 4 + F 3 = 3 + 2 = 5
F 6 = F 5 + F 4 = 5 + 3 = 8
...

Calcul du nième nombre d'une série de Fibonacci à l'aide d'une boucle while

1. Affectez aux variables fib1 et fib2 les valeurs des deux premiers éléments de la ligne, c'est-à-dire affectez des unités aux variables.
2. Demander à l'utilisateur le numéro de l'élément dont il souhaite obtenir la valeur. Attribuez un numéro à la variable n.
3. Effectuez les étapes suivantes n - 2 fois, puisque les deux premiers éléments ont déjà été pris en compte :
   1. Ajoutez fib1 et fib2, en affectant le résultat à une variable de stockage temporaire, telle que fib_sum.
   2. Définissez la variable fib1 sur fib2.
   3. Définissez la variable fib2 sur fib_sum.
4. Affichez la valeur fib2.

Noter. Si l'utilisateur entre 1 ou 2, le corps de la boucle n'est jamais exécuté, la valeur d'origine de fib2 est affichée.

fib1 = 1 fib2 = 1 n = entrée () n = int (n) i = 0 tandis que i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)

Version compacte du code :

fib1 = fib2 = 1 n = int (entrée ( "Numéro d'élément de la série de Fibonacci :")) - 2 tant que n> 0 : fib1, fib2 = fib2, fib1 + fib2 n - = 1 print (fib2)

Sortie des nombres de Fibonacci avec une boucle for

Dans ce cas, non seulement la valeur de l'élément souhaité de la série de Fibonacci est affichée, mais également tous les nombres jusqu'à et y compris celui-ci. Pour ce faire, la sortie de la valeur fib2 est placée dans une boucle.

fib1 = fib2 = 1 n = int (entrée ()) si n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()

Exemple d'exécution :

10 1 1 2 3 5 8 13 21 34 55

Calcul récursif du nième nombre de la série de Fibonacci

1. Si n = 1 ou n = 2, retournez un à la branche appelante, puisque les premier et deuxième éléments de la série de Fibonacci sont égaux à un.
2. Dans tous les autres cas, appelez la même fonction avec les arguments n - 1 et n - 2. Ajoutez le résultat des deux appels et renvoyez-le à la branche du programme appelant.

def fibonacci (n) : si n dans (1, 2) : renvoie 1 renvoie fibonacci (n - 1) + fibonacci (n - 2) imprime (fibonacci (10))

Disons n = 4. Cela appellera récursivement fibonacci (3) et fibonacci (2). Le second en renverra un, et le premier entraînera deux autres appels de fonction : fibonacci (2) et fibonacci (1). Les deux appels en renverront un, pour un total de deux. Ainsi, l'appel à fibonacci (3) renvoie le numéro 2, qui s'ajoute au numéro 1 de l'appel à fibonacci (2). Le résultat 3 est renvoyé à la branche principale. Le quatrième élément de la série de Fibonacci est égal à trois : 1 1 2 3.

Les programmeurs devraient en avoir marre des nombres de Fibonacci maintenant. Des exemples de leur calcul sont utilisés partout. C'est parce que ces nombres fournissent l'exemple le plus simple de récursivité. Ils sont également un bon exemple de programmation dynamique. Mais est-il nécessaire de les calculer ainsi dans un projet réel ? Ne pas. Ni la récursivité ni la programmation dynamique ne sont des options idéales. Et pas une formule fermée utilisant des nombres à virgule flottante. Maintenant, je vais vous dire comment le faire correctement. Mais d'abord, passons en revue toutes les solutions connues.

Le code est pour Python 3, bien qu'il devrait également aller pour Python 2.

Pour commencer, permettez-moi de vous rappeler la définition :

Fn = Fn-1 + Fn-2

Et F 1 = F 2 = 1.

Formule fermée

Sautons les détails, mais ceux qui le souhaitent peuvent se familiariser avec la dérivation de la formule. L'idée est de supposer qu'il existe un certain x pour lequel F n = x n, puis de trouver x.

Qu'est-ce que

Réduire x n-2

On résout l'équation quadratique :

Où se développe la « section dorée » à partir de ϕ = (1 + √5) / 2. En remplaçant les valeurs initiales et en effectuant quelques calculs supplémentaires, nous obtenons :

C'est ce que nous utilisons pour calculer F n.

De __future__ import division import math def fib (n): SQRT5 = math.sqrt (5) PHI = (SQRT5 + 1) / 2 return int (PHI ** n / SQRT5 + 0.5)

Bon:
Rapide et facile pour les petits n
Mauvais:
Opérations en virgule flottante requises. Un grand n demandera plus de précision.
Mal:
Utiliser des nombres complexes pour calculer F n est beau d'un point de vue mathématique, mais laid d'un point de vue informatique.

Récursivité

La solution la plus évidente, que vous avez déjà vue plusieurs fois, est très probablement un exemple de ce qu'est la récursivité. Je vais le répéter encore une fois, pour être complet. En Python, il peut être écrit sur une seule ligne :

Fib = lambda n : fib (n - 1) + fib (n - 2) si n> 2 sinon 1

Bon:
Implémentation très simple reprenant la définition mathématique
Mauvais:
Temps d'exécution exponentiel. Très lent pour les grands n
Mal:
Débordement de pile

Mémorisation

La solution récursive a un gros problème : les calculs d'intersection. Lorsque fib (n) est appelé, fib (n-1) et fib (n-2) sont comptés. Mais lorsque fib (n-1) est compté, il comptera à nouveau indépendamment fib (n-2) - c'est-à-dire que fib (n-2) sera compté deux fois. Si on continue le raisonnement, on verra que fib (n-3) sera compté trois fois, et ainsi de suite. Il y a trop de carrefours.

Il vous suffit donc de mémoriser les résultats pour ne plus les compter. Le temps et la mémoire pour cette solution sont consommés de manière linéaire. J'utilise un dictionnaire dans la solution, mais un simple tableau aurait également pu être utilisé.

M = (0 : 0, 1 : 1) def fib (n) : si n dans M : return M [n] M [n] = fib (n - 1) + fib (n - 2) return M [n]

(En Python, cela peut également être fait avec le décorateur, functools.lru_cache.)

Bon:
Il suffit de transformer la récursivité en une solution de mémorisation. Convertit le temps d'exécution exponentiel en temps linéaire, ce qui consomme plus de mémoire.
Mauvais:
Gâche beaucoup de mémoire
Mal:
Débordement de pile possible, comme la récursivité

Programmation dynamique

Après la décision avec rappel, il devient clair que nous n'avons pas besoin de tous les résultats précédents, mais seulement des deux derniers. Alternativement, au lieu de commencer à fib (n) et de marcher en arrière, vous pouvez commencer à fib (0) et marcher en avant. Le code suivant a un temps d'exécution linéaire et une utilisation mémoire fixe. En pratique, la vitesse de la solution sera encore plus élevée, puisqu'il n'y a pas d'appels de fonction récursifs et le travail associé. Et le code a l'air plus simple.

Cette solution est souvent citée comme exemple de programmation dynamique.

Def fib (n) : a = 0 b = 1 pour __ dans la plage (n) : a, b = b, a + b renvoie a

Bon:
Fonctionne rapidement pour les petits n, code simple
Mauvais:
Durée d'exécution toujours linéaire
Mal:
Rien de spécial.

Algèbre matricielle

Et, enfin, la solution la moins éclairée, mais la plus correcte, utilisant à bon escient à la fois le temps et la mémoire. Elle peut également être étendue à toute séquence linéaire homogène. L'idée est d'utiliser des matrices. Il suffit de voir que

Une généralisation de ceci suggère que

Les deux valeurs de x que nous avons obtenues précédemment, dont l'une était le nombre d'or, sont les valeurs propres de la matrice. Par conséquent, une autre façon de dériver une formule fermée consiste à utiliser une équation matricielle et une algèbre linéaire.

Alors pourquoi une telle formulation est-elle utile ? Le fait que l'exponentiation puisse se faire en temps logarithmique. Cela se fait par équarrissage. L'essentiel est que

Où la première expression est utilisée pour pair A, la seconde pour impair. Il ne reste plus qu'à organiser la multiplication matricielle, et le tour est joué. Il s'avère que le code suivant. J'ai organisé une implémentation récursive de pow car c'est plus facile à comprendre. Voir la version itérative ici.

Def pow (x, n, I, mult): "" "Renvoie x à la puissance n. Suppose que I est la matrice identité qui est multipliée par mult et n est un entier positif" "" si n == 0: return I elif n == 1 : return x else : y = pow (x, n // 2, I, mult) y = mult (y, y) if n% 2 : y = mult (x, y) return y def Identity_matrix (n): "" "Renvoie la matrice d'identité n-par-n" "" r = list (range (n)) return [for j in r] def matrix_multiply (A, B): BT = list (zip ( * B) ) return [for row_a in A] def fib (n): F = pow ([,], n, identity_matrix (2), matrix_multiply) return F

Bon:
Mémoire fixe, temps logarithmique
Mauvais:
Code plus complexe
Mal:
Nous devons travailler avec des matrices, même si elles ne sont pas si mauvaises

Comparaison des performances

Cela vaut seulement la peine de comparer la variante de programmation dynamique et la matrice. Si nous les comparons par le nombre de chiffres du nombre n, il s'avère que la solution matricielle est linéaire et que la solution avec la programmation dynamique est exponentielle. Un exemple pratique est le calcul de fib (10 ** 6), un nombre qui aura plus de deux cent mille caractères.

N = 10 ** 6
Calculer fib_matrix : fib (n) a 208988 chiffres au total, le calcul a pris 0,24993 seconde.
Calculer fib_dynamic : fib (n) a 208988 chiffres au total, il a fallu 11,83377 secondes pour calculer.

Remarques théoriques

Ne touchant pas directement au code ci-dessus, cette remarque présente tout de même un certain intérêt. Considérez le graphique suivant :

Comptons le nombre de chemins de longueur n de A à B. Par exemple, pour n = 1 nous avons un chemin, 1. Pour n = 2 nous avons à nouveau un chemin, 01. Pour n = 3 nous avons deux chemins, 001 et 101 On montre tout simplement que le nombre de chemins de longueur n de A à B est exactement égal à F n. En notant la matrice d'adjacence pour le graphique, nous obtenons la même matrice que celle décrite ci-dessus. C'est un résultat bien connu de la théorie des graphes que pour une matrice d'adjacence donnée A, les occurrences dans A n sont le nombre de chemins de longueur n dans le graphe (l'un des problèmes mentionnés dans le film "Good Will Hunting").

Pourquoi y a-t-il de telles marques sur les bords ? Il s'avère que lorsque vous regardez une séquence infinie de caractères sur une séquence infinie de chemins dans les deux sens sur un graphique, vous obtenez quelque chose appelé "sous-décalages de type fini", qui est un type de système de dynamique symbolique. Ce sous-décalage particulier de type fini est connu sous le nom de « décalage du nombre d'or » et est spécifié par un ensemble de « mots interdits » (11). En d'autres termes, nous obtenons des séquences binaires infinies dans les deux sens et aucune paire d'entre elles ne sera adjacente. L'entropie topologique de ce système dynamique est égale au nombre d'or . Il est intéressant de voir comment ce nombre apparaît périodiquement dans différents domaines des mathématiques.