[Python] Un programme pour trouver une séquence de Fibonacci (fonction récursive, méthode de gouvernance divisionnaire, méthode de planification dynamique)

Programme pour trouver la séquence de Fibonacci

Écrivez un programme qui trouve n éléments dans la séquence de nombres de Fibonacci avec plusieurs descriptions.

Quelle est la séquence de Fibonacci?

Une séquence de nombres créée en ajoutant le terme précédent et le terme précédent.

1,1,2,3,5,8,13,21,34,55,,,,,,

Lorsque vous les ajoutez ensemble, un grand rectangle est créé.

La séquence de Fibonacci est un tourbillon d'ammonite et de tourbillons qui grossissent dans l'espace.

Le rectangle d'or de Steel Ball Run est également une séquence de Fibonacci.

python

def fib(n):
  arr = [1,1]
  for j in range(n-1):
    val = arr[j] + arr[j+1] 
    arr.append(val) 

  return (arr[len(arr)-1])

Vérification

n=35
for i in range(1, n):
  print(fib(i))

Cela revient à répéter jusqu'à ce que la condition spécifiée soit remplie pour, et le même processus est répété jusqu'à ce que la condition de retour soit remplie.

python

def fib(n):
  if n==1 or n==2:
    return 1
  return fib(n-1) + fib(n-2)

python

#Vérification
n=35
for i in range(1, n):
  print(fib(i))

Ce processus prend relativement du temps. En effet, le même calcul est ** calculé individuellement dans fib (n-1) et fib (n-2), respectivement.

Puisque fib (n-2) calcule plus tôt, si la solution est appliquée à fib (n-1), le temps de calcul peut être considérablement réduit.

Cette méthode historique est appelée ** méthode de planification dynamique **.

python

#S'il ne s'agit que d'une variable, memo devient une variable globale, alors mettez-la dans def et faites-en une variable locale.
def fib_memo(n):
  #Fib pour que la valeur reste même après la fin du traitement de la fonction(n)Sors de
  memo = [None]*(n+1)  #n+Préparez un tableau contenant un élément vide

  def _fib(n):
    if n==0 or n==1:
      return 1
    if memo[n] != None:  #Si l'élément de la valeur spécifiée est différent de None, utilisez cette valeur (* Les valeurs initiales sont toutes None)
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2) #Si aucune, remplacez les valeurs ajoutées
    return memo[n]
  
  return _fib(n)

Vérification

n=40
for i in range(0, n):
  print(fib_memo(i))

-Aucun: indiquer explicitement qu'il est vide (aucun objet) -_Nom de la fonction: suggère une fonction à utiliser uniquement localement

Le processus de calcul est considérablement plus rapide.

Il est également possible d'utiliser la méthode mémo au lieu de la méthode récursive pour calculer un par un à partir de petits nombres.

python

def fib_dp(n):
  memo = [None]*n
  memo[0] = 1
  memo[1] = 1
  for i in range(2, n):
    memo[i] = memo[i-1] + memo[i-2]
  return memo