J'essaie de créer une fonction qui me donne la séquence Fibonacci pour toute valeur de n. Cependant, après le n = 92, je reçois des réponses incorrectes.
import numpy as np
def Power(M, n):
if not n:
return 1
elif n % 2:
return M*Power(M, n-1)
else:
sqrt = Power(M, n//2)
return sqrt**2
def _fib(n):
G = np.matrix([[1,1],[1,0]])
F = Power(G, n)
return F[0,1]
3 Réponses :
On dirait que vous ressemblez à des problèmes de précision des points flottants.
Les entiers de Python 3 sont une précision arbitraire, vous pouvez donc simplement les utiliser et lru_cache code> pour mémoisation: p> 1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
...
92 7540113804746346429
93 12200160415121876738
94 19740274219868223167
Je préférerais si mon algorithme actuel est réparé - je l'ai ajouté dans la modification.
L'algorithme OP prend O (journal n) d'opérations de base et utilise des objets O (1), tandis que la mémoisation est O (n) d'opérations de base et utilise des objets O (n) pour le premier appel à FIB (N). En fait, étant donné que ceux-ci sont gros-int la complexité est O ((log n) ** 2) vs. O (n log n).
Vous devez définir un Cependant, cela soulève légèrement la barre (si votre système n'est pas Même en utilisant cette valeur par défaut) et débordera bientôt, et vous ne le remarquerez même pas aussi facilement que les chiffres ne seront pas négatifs ... La réponse@michael fonctionne beaucoup mieux. dttype pour permettre des numéros plus importants dans votre matrice:
Merci! Juste une clarification - cela augmente-t-il de 32 bits à 64 bits pour l'entier?
Merci de votre aide. Y a-t-il un moyen d'augmenter la limite? Je veux faire un graphique jusqu'à n = 15 000
Vous devez autoriser les numéros Big-int, sinon vous êtes limité avec les bits 63 par défaut (+ bit de signe) ou avec np.uint64 code> qui est seulement 1 bit plus grand: import numpy as np
def Power(M, n):
if not n:
# Original 'return 1' does not work with n=0
return np.identity(2, dtype=object)
elif n % 2:
return M*Power(M, n-1)
else:
sqrt = Power(M, n//2)
return sqrt**2
def fib(n):
# This allows for big-int
G = np.matrix([[1,1],[1,0]], dtype=object)
F = Power(G, n)
return F[0,1]
Merci! Cela fonctionne pour toute valeur pour n. Pouvez-vous simplement décrire ce que Dtype = objet signifie? Il suffit de tourner int en bigint?
@Utsoroy lire ici: Stackoverflow.com/questions/28552599/ ...
Quel est l'algorithme que vous utilisez ici?
@Akx a ajouté l'algorithme dans la question
Avez-vous essayé de définir un
DTYPE pour la matrice? BTW, obtention d'untypeError: 'int' objet n'est pas syndicalable à la place ...Je ne reçois aucun type de cette erreur comme l'erreur de type. Je n'ai pas essayé de faire dype - comment faire ça?
Overflow entier 32 bits:
2 ^ 31 + 6246583658587674878 = 12200160415121876738