En mathématiques, la série de Fibonacci est une séquence de nombres telle que chaque nombre de la série est une somme des nombres précédents. La série commence par 0 et 1. Ce blog nous apprendra comment créer la série de Fibonacci en Python à l'aide d'une boucle, d'une récursivité et d'une programmation dynamique.

1. Qu'est-ce que la série de Fibonacci
2. Logique des séries de Fibonacci
3. Formule de la série de Fibonacci
4. Spirale de Fibonacci
5. Algorithme des séries de Fibonacci
6. Série de Fibonacci en Python
   a. Série de Fibonacci utilisant la boucle
   b. Série de Fibonacci utilisant la récursivité
   c. Série de Fibonacci utilisant la programmation dynamique
7. FAQ

Leonardo Pisano Bogollo était un mathématicien italien de la République de Pise et était considéré comme le mathématicien occidental le plus talentueux du Moyen Âge. Il a vécu entre 1170 et 1250 en Italie. "Fibonacci" était son surnom, signifiant "Fils de Bonacci". Fibonacci n'était pas le premier à connaître la séquence, et elle était connue en Inde des centaines d'années auparavant !

Qu'est-ce que la série de Fibonacci ?

La série de Fibonacci est une suite de nombres où chaque nombre résulte de en additionnant les deux derniers nombres consécutifs. Les 2 premiers nombres commencent par 0 et 1, et le troisième nombre de la séquence est 0+1=1. Le 4e nombre est l'addition du 2e et du 3e nombre, c'est-à-dire 1+1=2, et ainsi de suite.
La suite de Fibonacci est la suite de nombres :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

La logique de la série de Fibonacci

Le nombre suivant est la somme des deux nombres qui le précèdent.
Le 3ème élément est (1+0) = 1
Le 4ème élément est (1+1) = 2
Le 5ème élément est (2+1) = 3

Formule de la série de Fibonacci

La formule de calcul de la série est donc la suivante :
x_n =x_n-1 +x_n-2 ; où
x_n est le nombre de termes "n"
x_n-1 est le terme précédent (n-1)
x_n-2 est le terme avant cela

Spirale de Fibonacci

Une propriété intéressante à propos de ces nombres est que nous obtenons une spirale lorsque nous faisons des carrés avec ces largeurs. Une spirale de Fibonacci est un motif de quarts de cercle connectés à l'intérieur d'un bloc de carrés avec des nombres de Fibonacci écrits dans chacun des blocs. Le nombre dans le carré géant est la somme des 2 petits carrés suivants. Il s'agit d'un arrangement parfait où chaque bloc est désigné par un nombre plus élevé que les deux blocs précédents. L'idée principale a été dérivée du modèle logarithmique, qui semble également similaire. Ces chiffres sont également liés au nombre d'or.

Apprenez à trouver si une chaîne est un palindrome en Python

Algorithme des séries de Fibonacci

Approche itérative

• Initialiser les variables a,b à 1
• Initialiser la boucle for in range[1,n) # n exclusif
• Calculez le numéro suivant dans la série ; totale = a+b
• Stocker la valeur précédente dans b
• Stocker le total dans un

Approche récursive

• Si n vaut 1 ou 0 ; retour 1
• Sinon retourner fib(n-1) + fib(n-2)

Approche de programmation dynamique

• Initialiser un tableau arr de taille n à zéros
• Si n vaut 0 ou 1 ; retour 1 Sinon
• Initialiser arr[0] et arr[1] à 1
• Exécuter une boucle dans la plage[2,num]
• Calculer la valeur arr[I]=arr[I-1] +arr[I-2]
• Le tableau a la séquence calculée jusqu'à n

Par conséquent, la solution serait de calculer la valeur une fois et de la stocker dans un tableau à partir duquel elle sera accessible la prochaine fois qu'elle sera requise. Par conséquent, nous utilisons la programmation dynamique dans de tels cas. Les conditions de mise en œuvre de la programmation dynamique sont
1. sous-problèmes qui se chevauchent
2. sous-structure optimale

Approche itérative

def fib_iter(n):
    a=1
    b=1
    if n==1:
        print('0')
    elif n==2:
        print('0','1')
    else:
        print("Iterative Approach: ", end=' ')
        print('0',a,b,end=' ')
        for i in range(n-3):
            total = a + b
            b=a
            a= total
            print(total,end=' ')
        print()
        return b
        
fib_iter(5)

TESTEZ LE CODE

Résultat : Approche itérative : 0 1 1 2 3

Approche récursive

def fib_rec(n):
    if n == 1:
        return [0]
    elif n == 2:
        return [0,1]
    else:
        x = fib_rec(n-1)
        # the new element the sum of the last two elements
        x.append(sum(x[:-3:-1]))
        return x
x=fib_rec(5)
print(x)

TESTEZ LE CODE

Sortie – 0, 1, 1, 2, 3

Approche de programmation dynamique

There is a slight modification to the iterative approach. We use an additional array.

def fib_dp(num):
    arr = [0,1]
    print("Dynamic Programming Approach: ",end= ' ')
    if num==1:
        print('0')
    elif num==2:
        print('[0,','1]')
    else:
        while(len(arr)<num):
            arr.append(0)
        if(num==0 or num==1):
            return 1
        else:
            arr[0]=0
            arr[1]=1
            for i in range(2,num):
                arr[i]=arr[i-1]+arr[i-2]
            print(arr)    
            return arr[num-2]
fib_dp(5)

TESTEZ LE CODE

Sortie – 0, 1, 1, 2, 3

Si vous avez trouvé ce blog utile, découvrir l'intelligence artificielle et avancez dans votre carrière. Apprenez des meilleurs de l'industrie et accédez à des séances de mentorat et à une aide à la carrière.

FAQ

Lectures complémentaires

1. Factorielle d'un nombre en Python
2. Palindrome en Python
3. Convertir une liste en chaîne en Python
4. Fonction d'évaluation en Python