Efficace de calcul de la suite de Fibonacci

Je suis en train de travailler sur un Projet Euler problème: celui de la somme des nombres de Fibonacci.

Mon code:

def Fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

list1 = [x for x in range(39)]
list2 = [i for i in list1 if Fibonacci(i) % 2 == 0]

La solution du problème peut être facilement trouvé par l'impression de la somme(liste 2). Cependant, c'est prendre beaucoup de temps pour arriver à la liste 2, je suis dans le doute. Est-il possible de faire plus vite? Ou est-il correct, même de cette façon...

(le problème: En considérant les termes de la suite de Fibonacci dont les valeurs ne dépassent pas quatre millions de dollars, la somme de la valeur des termes.)

P. S. j'ai trouvé les valeurs pour lesquelles elle ne dépasse pas 4 millions de dollars en essayant.
Astuce: essayez de lire la page wiki...
Non: la page wiki pour les nombres de Fibonacci....
Naïf récursivité ne fonctionne que dans O(phi^n)
On peut calculer dans O(log n). Voir n-ième nombre de fibonacci dans sublinéaire temps.
Projet Euler 's Même nombres de Fibonacci est sur even-valued terms, et non pas les valeurs avec la même ordinal/pour les même arguments/au même indice. Si vous pouvez trouver l'ordinal pour le plus grand terme plus petite que la limite (four million avec "Problème 2"), vous pouvez trouver cette somme en une seule évaluation de la fonction de Fibonacci.

InformationsquelleAutor user65165 | 2013-08-11

80

Oui. La primitive récursive solution prend beaucoup de temps. La raison pour cela est que, pour chaque nombre calculé, il a besoin de calculer tous les nombres précédents plus d'une fois. Jetez un oeil à l'image ci-dessous.

Il représente le calcul de Fibonacci(5) avec votre fonction. Comme vous pouvez le voir, il calcule la valeur de Fibonacci(2) trois fois, et la valeur de Fibonacci(1) cinq fois. Que devient de pire en pire plus le numéro que vous voulez calculer.

Ce qui le rend même pire, c'est qu'avec tous les nombres de fibonacci vous calculer dans votre liste, vous n'avez pas utiliser les numéros précédents d'avoir les connaissances nécessaires pour accélérer la vitesse de calcul permet de calculer chaque nombre "à partir de zéro."

Il ya quelques options pour rendre cela plus rapidement:

1. Créer une liste "par le bas"

La façon la plus simple est de créer une liste de nombres de fibonacci jusqu'à le nombre que vous voulez. Si vous le faites, vous construire "par le bas", ou pour parler, et vous pouvez réutiliser les numéros précédents pour créer le prochain. Si vous avez une liste des nombres de fibonacci [0, 1, 1, 2, 3], vous pouvez utiliser les deux derniers numéros de cette liste pour créer le prochain numéro.

Cette approche devrait ressembler à quelque chose comme ceci:
```
>>> def fib_to(n):
...     fibs = [0, 1]
...     for i in range(2, n+1):
...         fibs.append(fibs[-1] + fibs[-2])
...     return fibs
...
```
Ensuite, vous pouvez obtenir les 20 premiers nombres de fibonacci en faisant
```
>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
```
Ou vous pouvez obtenir le 17e nombre de fibonacci à partir d'une liste de la première 40 en faisant
```
>>> fib_to(40)[17]
1597
```
2. Memoization (relativement avancée technique)

Une autre alternative pour le rendre plus rapide existe, mais il est un peu plus compliqué que de bien. Depuis votre problème est que vous re-calculer les valeurs que vous avez déjà calculé, vous pouvez à la place choisir de sauvegarder les valeurs que vous avez déjà calculée dans un dict, et essayer d'obtenir à partir de l'avant de recalculer eux. Ceci est appelé memoization. Il peut ressembler à quelque chose comme ceci:
```
>>> def fib(n, computed = {0: 0, 1: 1}):
...     if n not in computed:
...         computed[n] = fib(n-1, computed) + fib(n-2, computed)
...     return computed[n]
```
Cela vous permet de calculer les grands nombres de fibonacci en un clin d'oeil:
```
>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675
```
C'est en fait, une telle technique courante que Python 3 comprend un décorateur pour le faire pour vous. Je vous présente, automatique memoization!
```
import functools

@functools.lru_cache(None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)
```
Cela fait à peu près la même chose que la fonction précédente, mais avec tous les computed trucs traitées par le lru_cache décorateur.

3. Juste compter jusqu' (un naïf solution itérative)

Une troisième méthode, comme suggéré par Mitch, est à juste compter jusqu'sans enregistrer l'intermédiaire de valeurs dans une liste. Vous pourriez imaginer faire
```
>>> def fib(n):
...     a, b = 0, 1
...     for _ in range(n):
...         a, b = b, a+b
...     return a
```
Je ne recommande pas ces deux dernières méthodes, si votre objectif est de créer un liste de nombres de fibonacci. fib_to(100) va être beaucoup plus vite que [fib(n) for n in range(101)] parce qu'avec ce dernier, vous obtenez toujours le problème de calcul de chaque nombre de la liste à partir de zéro.
- ou vous pouvez utiliser la formule itérative ...
- Si vous modifiez la fonction à la fin à venir de mitch à un générateur au lieu de cela, ce sera encore mieux, car vous ne serez pas recalculer le nombre à chaque fois. il suffit de changer de retour de rendement et de le déplacer dans la boucle for.
- ne serait-il pas fondamentalement devenir la première fonction d'ici là? (Sauf que vous ne pouvez prendre qu'une valeur une fois, et vous ne pouvez pas indexer.)
- Génial la réponse! Je vous remercie beaucoup. J'ai appris beaucoup de nouvelles choses ainsi 😀
- yah. Ce serait le même, mais sans exiger qu'ils tous être conservés. Si vous voulais de l'indice, alors vous devriez juste besoin de faire list(fib(N)). Probablement à un petit gain de performance si. Je n'ai pas lu toute la réponse. Je suis la gueule de bois.
- Très belle réponse complète. À l'aide mutable argument par défaut pour un mémo est un de mes préférés python astuces. Vous pouvez également mentionner les closed-form expression pour fib numéros.
- Une solution pour calculer la première nth même nombres de Fibonacci à l'aide d'un générateur est absent de cette réponse complète cependant. Vous pouvez trouver une mise en œuvre dans ma réponse ci-dessous. @kqr: Aucune idée pourquoi LRU cache décorateur est beaucoup plus lent que d'une main memoized solution?
- Ennuyeux réponse: La main de cache est spécialisée dans la tâche et donc de meilleures performances en étant en mesure d'ignorer complètement beaucoup de cas limites. Le décorateur est censé faire la bonne chose pour tout appel de fonction avec n'importe quel ensemble de paramètres, qui mange des cycles. Réponse intéressante: faites-vous plaisir: fossies.org/dox/Python-3.4.3/functools_8py_source.html#l00438
- memoization serait de retour dans les grands ensembles in fib computed[n] = fib(n-1, computed) + fib(n-2, computed) [Previous line repeated 995 more times] RecursionError: maximum recursion depth exceeded
- Et malheureusement, même en utilisant la queue-appelons cela ne résout pas, @AlexandrosSpyropoulos. Tout simplement parce que Guido, le créateur de Python, n'aime pas l'idée de la Queue d'Appel d'Optimisation... euh. Eh bien, +1 pour la réponse à l'aide de la functools.lru_cache. Vraiment super
- Il y a une forme fermée formule pour les nombres de Fibonacci. Pourquoi sur terre serait-on utiliser autre chose?
InformationsquelleAutor kqr
46

C'est un très algorithme rapide et il peut trouver le n-ième nombre de Fibonacci beaucoup plus rapide que la simple approche itérative présentés dans les autres réponses, il est très avancé si:
```
def fib(n):
    v1, v2, v3 = 1, 1, 0    # initialise a matrix [[1,1],[1,0]]
    for rec in bin(n)[3:]:  # perform fast exponentiation of the matrix (quickly raise it to the nth power)
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2
```
Vous pouvez lire un peu plus à propos impliqués mathématiques ici.
- Où puis-je trouver une explication mathématique de la source pour la méthode?
- Vous pouvez lire à ce sujet impliqué maths ici: en.wikipedia.org/wiki/Fibonacci_number#Matrix_form. Mon algorithme utilise exponentiation rapide pour élever la matrice à la nième puissance.
- C'est trop difficiles à comprendre. Je ne recommande pas la solution pour frais de départ.
- Est-il plus rapide que la plaine forme fermée? en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding
- probablement, mais il sera également incorrectes pour les grandes valeurs de n que python floats sont d'une précision limitée, à la différence de la ints
- C'est de loin la méthode la plus rapide. Il peut même être plus rapide d'utiliser n % 2, n //= 2 pour rec au lieu de l'opération de chaîne bin.
InformationsquelleAutor Piotr Dabkowski

Python n'est pas d'optimiser la queue de la récursivité, donc la plupart des solutions présentées ici échouera avec Error: maximum recursion depth exceeded in comparison si n est trop gros (et en gros, je veux dire 1000).

La limite de la récursivité peut être augmenté, mais il fera de Python crash sur un débordement de pile dans le système d'exploitation.

Remarque la différence de performance entre fib_memo /fib_local et fib_lru /fib_local_exc: LRU cache est beaucoup plus lent et n'a même pas complet, car il génère une erreur d'exécution déjà pour n = ~500:

import functools
from time import clock
#import sys
#sys.setrecursionlimit()
@functools.lru_cache(None)
def fib_lru(n):
if n < 2:
return n
return fib_lru(n-1) + fib_lru(n-2)
def fib_memo(n, computed = {0: 0, 1: 1}):
if n not in computed:
computed[n] = fib_memo(n-1, computed) + fib_memo(n-2, computed)
return computed[n]
def fib_local(n):
computed = {0: 0, 1: 1}
def fib_inner(n):
if n not in computed:
computed[n] = fib_inner(n-1) + fib_inner(n-2)
return computed[n]
return fib_inner(n)
def fib_local_exc(n):
computed = {0: 0, 1: 1}
def fib_inner_x(n):
try:
computed[n]
except KeyError:
computed[n] = fib_inner_x(n-1) + fib_inner_x(n-2)
return computed[n]
return fib_inner_x(n)
def fib_iter(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
def benchmark(n, *args):
print("-" * 80)
for func in args:
print(func.__name__)
start = clock()
try:
ret = func(n)
#print("Result:", ret)
except RuntimeError as e:
print("Error:", e)
print("Time:", "{:.8f}".format(clock() - start))
print()
benchmark(500, fib_iter, fib_memo, fib_local, fib_local_exc, fib_lru)

Résultats:

fib_iter
Time: 0.00008168
fib_memo
Time: 0.00048622
fib_local
Time: 0.00044645
fib_local_exc
Time: 0.00146036
fib_lru
Error: maximum recursion depth exceeded in comparison
Time: 0.00112552

La solution itérative est de loin la manière la plus rapide et ne pas endommager la pile, même pour n=100k (0.162 secondes). Il ne renvoie pas l'intermédiaire de la suite de Fibonacci en effet.

Si vous voulez calculer le nth même nombre de Fibonacci, vous pourriez adapter l'approche itérative comme ceci:

def fib_even_iter(n):
a, b = 0, 1
c = 1
while c < n:
a, b = b, a + b
if a % 2 == 0:
c += 1
return a

Ou si vous êtes intéressé, à chaque numéro sur le chemin, utilisez un générateur:

def fib_even_gen(n):
a, b = 0, 1
c = 1
yield a
while c < n:
a, b = b, a + b
if a % 2 == 0:
yield a
c += 1
return a
for i, f in enumerate(fib_even_gen(100), 1):
print("{:3d}.  {:d}".format(i, f))

Résultat:

  1.  0
2.  2
3.  8
4.  34
5.  144
6.  610
7.  2584
8.  10946
9.  46368
10.  196418
11.  832040
12.  3524578
13.  14930352
14.  63245986
15.  267914296
16.  1134903170
17.  4807526976
18.  20365011074
19.  86267571272
20.  365435296162
21.  1548008755920
22.  6557470319842
23.  27777890035288
24.  117669030460994
25.  498454011879264
26.  2111485077978050
27.  8944394323791464
28.  37889062373143906
29.  160500643816367088
30.  679891637638612258
31.  2880067194370816120
32.  12200160415121876738
33.  51680708854858323072
34.  218922995834555169026
35.  927372692193078999176
36.  3928413764606871165730
37.  16641027750620563662096
38.  70492524767089125814114
39.  298611126818977066918552
40.  1264937032042997393488322
41.  5358359254990966640871840
42.  22698374052006863956975682
43.  96151855463018422468774568
44.  407305795904080553832073954
45.  1725375039079340637797070384
46.  7308805952221443105020355490
47.  30960598847965113057878492344
48.  131151201344081895336534324866
49.  555565404224292694404015791808
50.  2353412818241252672952597492098
51.  9969216677189303386214405760200
52.  42230279526998466217810220532898
53.  178890334785183168257455287891792
54.  757791618667731139247631372100066
55.  3210056809456107725247980776292056
56.  13598018856492162040239554477268290
57.  57602132235424755886206198685365216
58.  244006547798191185585064349218729154
59.  1033628323428189498226463595560281832
60.  4378519841510949178490918731459856482
61.  18547707689471986212190138521399707760
62.  78569350599398894027251472817058687522
63.  332825110087067562321196029789634457848
64.  1409869790947669143312035591975596518914
65.  5972304273877744135569338397692020533504
66.  25299086886458645685589389182743678652930
67.  107168651819712326877926895128666735145224
68.  453973694165307953197296969697410619233826
69.  1923063428480944139667114773918309212080528
70.  8146227408089084511865756065370647467555938
71.  34507973060837282187130139035400899082304280
72.  146178119651438213260386312206974243796773058
73.  619220451666590135228675387863297874269396512
74.  2623059926317798754175087863660165740874359106
75.  11111460156937785151929026842503960837766832936
76.  47068900554068939361891195233676009091941690850
77.  199387062373213542599493807777207997205533596336
78.  844617150046923109759866426342507997914076076194
79.  3577855662560905981638959513147239988861837901112
80.  15156039800290547036315704478931467953361427680642
81.  64202014863723094126901777428873111802307548623680
82.  271964099255182923543922814194423915162591622175362
83.  1152058411884454788302593034206568772452674037325128
84.  4880197746793002076754294951020699004973287771475874
85.  20672849399056463095319772838289364792345825123228624
86.  87571595343018854458033386304178158174356588264390370
87.  370959230771131880927453318055001997489772178180790104
88.  1571408518427546378167846658524186148133445300987550786
89.  6656593304481317393598839952151746590023553382130993248
90.  28197781736352815952563206467131172508227658829511523778
91.  119447720249892581203851665820676436622934188700177088360
92.  505988662735923140767969869749836918999964413630219877218
93.  2143402371193585144275731144820024112622791843221056597232
94.  9079598147510263717870894449029933369491131786514446266146
95.  38461794961234640015759308940939757590587318989278841661816
96.  162926777992448823780908130212788963731840407743629812913410
97.  690168906931029935139391829792095612517948949963798093315456
98.  2923602405716568564338475449381171413803636207598822186175234
99.  12384578529797304192493293627316781267732493780359086838016392
100.  52461916524905785334311649958648296484733611329035169538240802
Time: 0.00698620

C'est le premier de 100, même nombres de Fibonacci dans ~7ms et inclut les frais généraux de l'impression à la borne (facile de sous-estimer sur Windows).

+1 pour l'introduction de [générateur] à cette question. (Vous pouvez générer la même valeur directement des termes à l'aide de a, b = 0, 2 et a, b = b, a + 4*b.)
J'ai fait un exemple simple utilisant Ruby au lieu (n - 1).times.reduce([0, 1]) { |array| [array[1], array[0] + array[1]] }.last
Merci, cela fait toute une différence pour n = 100k (12.5 s vs 0,6 s avec l'impression de console désactivé).

InformationsquelleAutor CoDEmanX

5

Basée sur le fait que fib(n) = fib(n-1)+fib(n-2), la solution simple est
```
def fib(n):
if (n <=1):
return(1)
else:
return(fib(n-1)+fib(n-2))
```
cependant, le problème ici est que certaines valeurs sont calculées à plusieurs reprises, et par conséquent, il est très inefficace. La raison peut être vu dans ce sketch:

Essentiellement, chaque appel récursif de fib fonction doit calculer toutes les précédentes nombres de fibonacci pour son propre usage. Ainsi, la plupart des valeur calculée sera fib(1), car elle doit apparaître dans tous les nœuds feuilles de l'arbre illustré par la réponse de @kqr. La complexité de cet algorithme est le nombre de nœuds de l'arbre, qui est de $O(2^n)$.

Maintenant une meilleure façon est de garder la trace de deux nombres, la valeur actuelle et la valeur précédente, de sorte que chaque appel n'a pas à calculer toutes les valeurs précédentes. C'est la deuxième algorithme dans l'esquisse, et peut être mis en œuvre comme suit
```
def fib(n):
if (n==0):
return(0,1)
elif (n==1):
return(1,1)
else:
a,b = fib(n-1)
return(b,a+b)
```
La complexité de cet algorithme est linéaire en $O(n)$, et certains exemples seront
```
>>> fib(1)
(1, 1)
>>> fib(2)
(1, 2)
>>> fib(4)
(3, 5)
>>> fib(6)
(8, 13)
```
InformationsquelleAutor Vahid Mirjalili

Solution dans R, l'indice de référence calcule 1 à 1000e nombre de Fibonacci de la série dans 1,9 secondes. Serait beaucoup plus rapide en C++ ou Fortran, en fait, depuis la rédaction de mon post initial, j'ai écrit une fonction équivalente en C++ et qui a terminé dans un impressionnant 0.0033 quelques secondes, même en python complété en 0,3 secondes.

#Calculate Fibonnaci Sequence
fib <- function(n){
if(n <= 2)
return(as.integer(as.logical(n)))
k = as.integer(n/2)
a = fib(k + 1)
b = fib(k)
if(n %% 2 == 1)
return(a*a + b*b)
return(b*(2*a - b))
}
#Function to do every fibonacci number up to nmax
doFib <- function(nmax = 25,doPrint=FALSE){
res = sapply(0:abs(nmax),fib)
if(doPrint)
print(paste(res,collapse=","))
return(res)
}
#Benchmark
system.time(doFib(1000))
#user  system elapsed 
#  1.874   0.007   1.892

InformationsquelleAutor Nicholas Hamilton

J'ai basé cette sur un article sur les nombres de Fibonacci sur Wikipédia. L'idée est d'éviter le bouclage et la récursivité et il suffit de calculer la valeur en tant que de besoin.

De ne pas être un math wiz, choisi parmi les formules et l'a rendu à code et modifié jusqu'à ce que les valeurs est sorti.

import cmath
def getFib(n):
#Given which fibonacci number we want, calculate its value
lsa = (1 / cmath.sqrt(5)) * pow(((1 + cmath.sqrt(5)) / 2), n)
rsa = (1 / cmath.sqrt(5)) * pow(((1 - cmath.sqrt(5)) / 2), n)
fib = lsa-rsa
#coerce to real so we can round the complex result
fn = round(fib.real) 
return fn 
#Demo using the function
s = ''
for m in range(0,30):
s = s + '(' + str(m) + ')' + str(getFib(m)) + ' '
print(s)

Comment ce faire de [finding] the sum of the even-valued terms not [exceeding] four million rapide?

InformationsquelleAutor Dan Rhea

kqr's solution n ° 2 est mon définitive favori.

Toutefois, dans ce cas précis nous perdre tous nos calculs entre conséquente des appels dans la compréhension de liste:

list2 = [i for i in list1 if fib(i) % 2 == 0]

j'ai donc décidé d'aller plus loin et memoize il entre en boucle étapes, comme suit:

def cache_fib(ff):
comp = {0: 0, 1: 1}
def fib_cached(n, computed=comp):
return ff(n, computed)
return fib_cached
@cache_fib
def fib(n, computed={0: 0, 1: 1}):
if n not in computed:
computed[n] = fib(n - 1, computed) + fib(n - 2, computed)
return computed[n]

InformationsquelleAutor Lukasz

Il y a un O(1) solution: https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding

import math
PHI = (1 + math.sqrt(5)) / 2
SQRT5 = math.sqrt(5)
def fast_fib(n):
if n < 0:
raise ValueError('Fibs for negative values are not defined.')
return round(math.pow(PHI, n) / SQRT5)

InformationsquelleAutor Bastian Venthur

1

Des problèmes comme cela va prendre un certain temps si il y a beaucoup de niveaux de récursivité. La définition récursive est bon pour le codage du problème d'une manière qui peut être facilement compris, mais si vous en avez besoin pour courir plus vite une solution itérative comme la réponse dans ce fil sera beaucoup plus rapide.
- c'est pourquoi j'ai suggéré l'affiche de regarder la page du wiki pour les nombres de Fibonacci
- De manière récursive exprimant quelque chose de ne pas le faire automatiquement, plus facile à comprendre
- Je suis d'accord que ça ne fait pas automatiquement de le rendre plus facile à comprendre, mais vous pouvez souvent d'exprimer encore plus clairement et d'une manière très semblable à la façon dont vous voulez voir la formule affichée par ex. formule de fibonacci est F_n = F_{n-1} + F_{n-2} avec les valeurs de départ F_0 = 0, F_1 = 1. Le programme proposé par l'OP est presque identique.
- Il peut être utile si vous fournir le lien. J'ai essayé de chercher et trouvé cette page: stackoverflow.com/tags/fibonacci/info qui ne semble pas à dire ce qui n'est pas couvert par l'OP.
- Je suis en supposant même un nouvel utilisateur peut utiliser un moteur de recherche.
InformationsquelleAutor ChrisProsser
1

Récursive de calcul de Fibonacci sera plus inefficace que de le faire de manière itérative. Ma recommandation est:

Prendre le temps de créer un Fibonacci classe comme un itérateur, et de faire les calculs de façon indépendante pour chaque élément de l'index, peut-être avec quelques @memoize décorateur (et aussi ici) pour mettre en cache tous les calculs précédents.

Espérons que cette aide!
- Dans le cas où vous faites référence à la queue-appel d'optimisation quand vous dites "optimiser droit récursive code" – ce n'est pas possible d'optimisation à faire ici, puisque vous recurse deux branches. Si il serait possible à tous, vous seriez capable d'émuler en Python à l'aide d'un argument mot-clé.
- Je vois, donc ce type d'optimisation ne peut pas être fait dans les langages fonctionnels?
- Pas dans le calcul des nombres de fibonacci à l'aide de cette méthode, aucun. L'ordinateur a besoin de garder chaque image de la pile pour être en mesure d'effectuer l'addition.
- Merci, je vais supprimer cette recommandation de la réponse à prévenir d'autres trompeuse.
InformationsquelleAutor Paulo Bu

Un moyen rapide de calculer l'fib(n/2) nombre de façon récursive:

fibs = {0: 0, 1: 1}
def fib(n):
if n in fibs: return fibs[n]
if n % 2 == 0:
fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2)
return fibs[n]
else:
fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2)
return fibs[n]
from time import time
s=time()
print fib(1000000)
print time()-s

InformationsquelleAutor Stefan Gruenwald

1

Haskell 1 liner :-
```
fibs = 0 : (f 1 1) where f a b = a : f b (a+b)
```
Ce code est extrêmement efficace et calcule les nombres de Fibonacci jusqu'à (10^1000) en moins d'une seconde !
Ce code sera également utile pour ce problème dans le Projet Euler.
- la question cependant est marqué [python]
InformationsquelleAutor rohansumant
1

Pour trouver la somme de la première n même valeur nombres de fibonacci directement, mettre 3n + 2 dans vos favoris méthode efficace de calculer un unique nombre de fibonacci, décrémenter par un et de les diviser par deux (fib((3*n+2) - 1)/2)). Comment avez-maths nuls survivre avant de OEIS?

InformationsquelleAutor greybeard

Vous pouvez utiliser l'équation avec des racines carrées pour le calcul de ce si vous n'utilisez pas l'arithmétique à virgule flottante, mais garder la trace des coefficients d'une autre façon que vous allez. Cela donne essentiellement une constante de temps exacte de l'algorithme pour des nombres de Fibonacci:

def rootiply(a1,b1,a2,b2,c):
''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
return a1*a2 + b1*b2*c, a1*b2 + a2*b1
def rootipower(a,b,c,n):
''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
ar,br = 1,0
while n != 0:
if n%2:
ar,br = rootiply(ar,br,a,b,c)
a,b = rootiply(a,b,a,b,c)
n /= 2
return ar,br
def fib(k):
''' the kth fibonacci number'''
a1,b1 = rootipower(1,1,5,k)
a2,b2 = rootipower(1,-1,5,k)
a = a1-a2
b = b1-b2
a,b = rootiply(0,1,a,b,5)
# b should be 0!
assert b == 0
return a/2**k/5
if __name__ == "__main__":
assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
assert fib(10)==55

InformationsquelleAutor Scott

C'est une version améliorée de Fibonacci où nous calculer Fibonacci de nombre qu'une seule fois:

dicFib = { 0:0 ,1 :1 }
iterations = 0
def fibonacci(a):
if  (a in dicFib):      
return dicFib[a]    
else :
global iterations               
fib = fibonacci(a-2)+fibonacci(a-1)
dicFib[a] = fib
iterations += 1
return fib
print ("Fibonacci of 10 is:" , fibonacci(10))
print ("Fibonacci of all numbers:" ,dicFib)
print ("iterations:" ,iterations)
# ('Fibonacci of 10 is:', 55)
# ('Fibonacci of all numbers:', {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55})
# ('iterations:', 9)

Ici, nous sommes de stockage de Fibonacci de chaque nombre dans le dictionnaire. De sorte que vous pouvez le voir, il calcule qu'une seule fois pour chaque itération et pour Fibonacci(10) est à seulement 9 fois.

InformationsquelleAutor Girish Gupta

1

Un O(1) solution

Il s'avère qu'il y a une belle formule récursive pour la somme de même nombres de Fibonacci. Le n-ième terme de la séquence de sommes de même nombres de Fibonacci est S_{n} = 4*S_{n-1} + S_{n-2} + 2 la Preuve est laissée au lecteur, mais consiste à prouver (1) Fibo sont les numéros de chaque troisième, 2) la preuve de la formule ci-dessus avec l'induction, en utilisant la définition de Fibo numéros. À l'aide de la logique de ici, nous pouvons dériver une forme fermée formule pour cela avec un peu d'effort:

S_{n} = -1/2 + (1/4 + 3*sqrt(5)/20)*(2+sqrt(5))**n + (1/4 - 3*sqrt(5)/20)*(2-sqrt(5))**n

Malgré la sqrt, cela fait partie intégrante de l'intégrale n, donc cela peut être facilement calculée en utilisant la pratique des fonctions à partir de ma réponse précédente, ou à l'aide d'un package comme sympy pour gérer les racines exactement.
```
import sympy as sp
one = sp.sympify(1) #to force casting to sympy types
k1 = -one/2
k2 = one/4 + 3*sp.sqrt(5)/20
k3 = one/4 - 3*sp.sqrt(5)/20
r1 = one
r2 = 2 + sp.sqrt(5)
r3 = 2 - sp.sqrt(5)
def even_sum_fibo(n):
#get the nth number in the sequence of even sums of Fibonacci numbers.  If you want the sum of Fibos up to some number m, use n = m/3 (integer division)
return sp.simplify(k1*r1**n + k2*r2**n + k3*r3**n)
```
InformationsquelleAutor Scott
1

O(1) SOLUTION

La formule est également appelé Binet Formule (lire plus)

Fondamentalement, nous pouvons l'écrire dans python comme ceci:
```
def fib(n):
a = ((1 + (5 ** 0.5)) / 2)**int(n)
b = ((1 - (5 ** 0.5)) / 2)**int(n)
return round((a - b) / (5 ** 0.5))
```
Toutefois, en Raison de la relativement faible de la valeur de b, on peut l'ignorer et de la fonction peut être aussi simple que de
```
def fib(n):
return round((((1+(5**0.5))/2)**int(n))/(5**0.5))
```
InformationsquelleAutor Tatsu
0

Bien qu'une réponse tardive mais il pourrait être utile
```
fib_dict = {}
def fib(n): 
try:
return fib_dict[n]
except:
if n<=1:
fib_dict[n] = n
return n
else:
fib_dict[n] = fib(n-1) + fib (n-2)
return fib(n-1) + fib (n-2)
print fib(100)
```
C'est beaucoup plus rapide que la méthode traditionnelle
- Répondre à ce? Essayer de comprendre la question, vérifiez si la réponse vous êtes tenté de vous donner est déjà là - ou dans l'une des "doublons"s.
- Son juste un complément d'info que l'habitude de mal à personne.Il ne pourrait pas vous aider, mais il serait certainement aider d'autres personnes qui cherchent.
InformationsquelleAutor Abx

Donné le numéro de départ et le nombre maximum; je pense que la solution suivante pour fibonacci serait intéressant. La bonne chose est qu'il ne comprend pas la récursivité, réduire le fardeau de la mémoire.

# starting number is a
# largest number in the fibonacci sequence is b
def fibonacci(a,b):
fib_series = [a, a]
while sum(fib_series[-2:]) <=b:
next_fib = sum(fib_series[-2:])
fib_series.append(next_fib)
return fib_series
print('the fibonacci series for the range %s is %s'
%([3, 27], fibonacci(3, 27)))
the fibonacci series for the range [1, 12] is [3, 3, 6, 9, 15, 24]

InformationsquelleAutor everestial007

0

Voici un exemple simple sans récursivité et de O(n)
```
def fibonacci(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
```
- Quelle question est-ce répondre?
- il y a un moyen de le rendre encore plus vite?"
InformationsquelleAutor dan-klasson
0

Spoiler alerte: ne lisez pas ceci si vous êtes en train de faire du Projet Euler Question 2 jusqu'à ce que vous avez eu une fissure à elle-même.

De forme fermée de la série-somme-approches basées sur le côté, ce qui semble plus efficace que la plupart de ce que j'ai vu posté, car il ne nécessite qu'un plutôt bon marché itération de boucle par même nombre de Fibonacci, de sorte que seulement 12 itérations pour atteindre 4 000 000 d'.
```
def sumOfEvenFibonacciNumbersUpTo(inclusiveLimit):
even = 0
next = 1
sum  = 0
while even<=inclusiveLimit:
sum  += even
even += next<<1
next  = (even<<1)-next
return sum
```
InformationsquelleAutor egyik

Ici est une Solution Optimisée avec le Dictionnaire

def Fibonacci(n):
if n<2 : return n
elif not n in fib_dict :
fib_dict[n]= Fibonacci(n-1) + Fibonacci(n-2)
return fib_dict[n]
#dictionary which store Fibonacci values with the Key
fib_dict = {}
print(Fibonacci(440))

InformationsquelleAutor vishwaraj

import time
def calculate_fibonacci_1(n):
if n == 0:
return 0
if n == 1:
return 1
return calculate_fibonacci_1(n - 1) + calculate_fibonacci_1(n - 2)
def calculate_fibonacci_2(n):
fib = [0] * n
fib[0] = 1
fib[1] = 1
for i in range(2, n):
fib[i] = fib[i - 1] + fib[i - 2]
return fib[n-1]
def calculate_fibonacci_3(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
def calculate_fibonacci_4(n):
v1, v2, v3 = 1, 1, 0
for rec in bin(n)[3:]:
calc = v2*v2
v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
if rec == '1':
v1, v2, v3 = v1+v2, v1, v2
return v2
def calculate_fibonacci_5(n):
if n == 0:
return (0, 1)
else:
a, b = calculate_fibonacci_5(n // 2)
c = a * (b * 2 - a)
d = a * a + b * b
if n % 2 == 0:
return (c, d)
else:
return (d, c + d)
n = 30
start = time.time()
calculate_fibonacci_1(n)
end = time.time()
print(end - start)
start = time.time()
calculate_fibonacci_2(n)
end = time.time()
print(end - start)
start = time.time()
calculate_fibonacci_3(n)
end = time.time()
print(end - start)
start = time.time()
calculate_fibonacci_4(n)
end = time.time()
print(end - start)
start = time.time()
calculate_fibonacci_5(n)
end = time.time()
print(end - start)

pour n=30:

0.264876127243
6.19888305664e-06
8.10623168945e-06
7.15255737305e-06
4.05311584473e-06

pour n=300:

>10s
3.19480895996e-05
1.78813934326e-05
7.15255737305e-06
6.19888305664e-06

pour n=3000:

>10s
0.000766038894653
0.000277996063232
1.78813934326e-05
1.28746032715e-05

pour n=30000:

>10s
0.0550990104675
0.0153529644012
0.000290870666504
0.000216007232666

pour n=300000:

>10s
3.35211610794
0.979753017426
0.012097120285
0.00845909118652

pour n=3000000:

>10s
>10s
>10s
0.466345071793
0.355515003204

pour n=30000000:

>100s
>100s
>100s
16.4943139553
12.6505448818

avertissement: codes de fonctions. 4 et 5 n'ont pas été écrit par moi

InformationsquelleAutor SantaXL

-4

int count=0;
void fibbo(int,int);
void main()
{
fibbo(0,1);
getch();
}
void fibbo(int a,int b)
{
count++;
printf(" %d ",a);
if(count<=10)
fibbo(b,a+b);
else
return;
}

Pourriez-vous écrire une petite explication sur ce que votre code est en train de faire?

InformationsquelleAutor Manoj Nawathale

Vous devez vous connecter pour publier un commentaire.

1. Créer une liste "par le bas"

2. Memoization (relativement avancée technique)

3. Juste compter jusqu' (un naïf solution itérative)

Un O(1) solution