J'apprends des mémoations dans des fonctions récursives et jeté sur un exemple de Fibonacci sur YouTube. Je n'ai jamais vu la personne qui dirige le code alors peut-être qu'il écrivit-il mal.
Lorsque j'ai copié le code et j'ai essayé de l'exécuter, j'ai eu une erreur depuis que je déclare note de gamme, donc je définit simplement la gamme sur le Entrée + 1 (puisque je n'utilise pas l'index 0) et a donc résolu ce problème. Mais maintenant je suis coincé à la mauvaise valeur de retour. Le code ci-dessus ne jette aucune erreur mais renvoie simplement la valeur "UINPTUT". Donc, si j'entraîne 6, pour le numéro de la 6e fois Fibonacci, le programme renvoie 6 au lieu de 8, qui est le numéro du 6ème numéro. Je suis à perte de la raison pour laquelle cela se produit. Lorsque j'ai googlé le problème, j'ai trouvé des threads qui ont suggéré d'utiliser des dicts au lieu de listes. C'est tout va bien si c'est le seul moyen de le faire. Mais s'il y a un moyen de faire fonctionner avec une liste, j'aimerais comprendre comment cela se fait pour que je comprends pourquoi je rencontre ce problème.
4 Réponses :
Vous avez rempli la liste code> Mémo code> avec la liste Vous devriez Supprimer cette ligne P> (plage (UINPUT + 1)) code>. Votre fonction est alors teste mémo [num]! = Aucune code>, ce qui doit être vrai. Donc, il fait toujours mémo de retour [num] code>, renvoyant ainsi le numéro dans la liste Mémo code> par la plage plage code>. memo = list(range(uInput + 1))
accéder à Dans votre cas, vous voulez Vérifiez que l'index est dans la plage avec mémo [num] code> ne retournera jamais Aucun code>. Si num code> est hors de portée, un indexerror code> sera soulevé. De plus, vous ne voulez généralement pas passer un argument code> code> sur votre fonction et la laissez-la compter sur son propre objet code> Mémo code>. len code>. Chaque fois que num code> est hors de portée, la sortie doit être calculée de manière récursive et mémodifiée. Ce n'est qu'alors alors peut-il être retourné. P> def fib(num, memo=[0, 1]):
while num >= len(memo):
memo.append(memo[-1] + memo[-2])
return memo[num]
J'aime beaucoup l'idée d'appends, je le trouve plus délicieux car il peut sembler sur le premier regard. +1 pour ça.
Cela fonctionne, avec la modification que vous devez, envoyer un mémo avec l'appel récursif également. La fonction attend deux arguments et lancera une erreur si les deux ne sont pas envoyées.
Il y a une erreur ici:
def fib(num, memo):
if memo[num] is None:
memo[num] = fib(num-1, memo) + fib(num-2, memo)
return memo[num]
uInput = int(input("Fibonacci: "))
memo = [0,1] + [None]*uInput
fibNum = fib(uInput, memo)
print(fibNum)
Je pense que votre question fait un excellent argument pourquoi la mémoisation doit être appliquée comme un décorateur au lieu d'être étroitement liée à la fonction elle-même: sinon vous êtes essayer de déboguer deux programmes différents en même temps. Essayez ce qui précède avec une entrée de 100 avec, et sans, le Ceci, bien sûr, reste limité à des entrées relativement faibles par la profondeur de la pile d'appels Python. Il y a des algorithmes itératifs (et encore mieux récursifs) qui peuvent faire mieux. @lru_cache () décorateur.