Un algorithme itératif pour les nombres de Fibonacci

vous retournez une valeur à l'intérieur d'une boucle, donc la fonction quitte avant que la valeur de y ne soit jamais supérieure à 1.

si je peux suggérer quelque chose de plus court, et beaucoup plus pythonful:

def fibs(n):                                                                                                 
    fibs = [0, 1, 1]                                                                                           
    for f in range(2, n):                                                                                      
        fibs.append(fibs[-1] + fibs[-2])                                                                         
    return fibs[n]

cela va faire exactement la même chose que votre algorithme, mais au lieu de créer trois variables temporaires, il les ajoute simplement dans une liste, et renvoie le nième nombre de fibonacci par index.

Sur fib(0), vous êtes de retour 0 car:

if (n == 0) {
    return 0;
}

Sur fib(1), vous êtes de retour 1 car:

y = 1
return y

Sur la fig(2), vous êtes de retour 1 car:

y = 1
return y

...et ainsi de suite. Tant que return y est à l'intérieur de votre boucle, la fonction se termine sur la première itération de votre boucle à chaque fois.

Voici une bonne solution qu'un autre utilisateur a trouvé: Comment faire écrire la séquence de Fibonacci en Python

Non récursif de la suite de Fibonacci en python

def fibs(n):
    f = []
    a = 0
    b = 1
    if n == 0 or n == 1:
        print n
    else:
        f.append(a)
        f.append(b)
        while len(f) != n:
            temp = a + b
            f.append(temp)
            a = b
            b = temp

    print f

fibs(10)

sortie: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

en supposant ces valeurs pour la séquence de fibonacci:

F (0) = 0;

F (1) = 1;

F (2) = 1;

F (3) = 2

pour les valeurs de N > 2 nous allons calculer la valeur de fibonacci avec cette formule:

F (N) = F(N-1) + F (N-2)

une approche itérative que nous pouvons adopter est de calculer fibonacci de N = 0 à N = Target_N, comme nous le faisons nous pouvons garder la trace des résultats précédents de fibonacci pour N-1 et n-2

public int Fibonacci(int N)
{
    // If N is zero return zero
    if(N == 0)
    {
        return 0;
    }

    // If the value of N is one or two return 1
    if( N == 1 || N == 2)
    {
       return 1;
    }

    // Keep track of the fibonacci values for N-1 and N-2
    int N_1 = 1;
    int N_2 = 1;

    // From the bottom-up calculate all the fibonacci values until you 
    // reach the N-1 and N-2 values of the target Fibonacci(N)
    for(int i =3; i < N; i++)
    {
       int temp = N_2;
       N_2 = N_2 + N_1;
       N_1 = temp;
    }

    return N_1 + N_2; 
}

def fibiter(n):
    f1=1
    f2=1
    tmp=int()
    for i in range(1,int(n)-1):
        tmp = f1+f2
        f1=f2
        f2=tmp
    return f2

ou avec affectation parallèle:

def fibiter(n):
    f1=1
    f2=1
    for i in range(1,int(n)-1):
        f1,f2=f2,f1+f2
    return f2

imprimer fibiter(4)

je suis tombé sur ce sur un autre fil et il est beaucoup plus rapide que n'importe quoi d'autre que j'ai essayé et wont time out sur de grands nombres. Voici un lien aux mathématiques.

def fib(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

cette œuvre ( intuitivement )

def fib(n):
    if n < 2:
        return n
    o,i = 0,1
    while n > 1:
        g = i
        i = o + i
        o = g
        n -= 1
    return i

Que Diriez-vous de cette voie simple mais la plus rapide... (Je viens de découvrir!)

def fib(n):
    x = [0,1]
    for i in range(n >> 1):
        x[0] += x[1]
        x[1] += x[0]
    return x[n % 2]

Note! par conséquent, cet algorithme simple n'utilise qu'une assignation et une addition, puisque la longueur de la boucle est raccourcie de 1/2 et que chaque boucle comprend deux assignations et deux additions.

fcount = 0 #a count recording the number of Fibonacci numbers generated
prev = 0
current = 0
next = 1
ll = 0 #lower limit
ul = 999 #upper limit

while ul < 100000:
    print("The following Fibonacci numbers make up the chunk between %d and %d." % (ll, ul))
    while next <= ul:
        print(next)
        prev = current
        current = next
        next = prev + current
        fcount += 1 #increments count

    print("Number of Fibonacci numbers between %d and %d is %d. \n" % (ll, ul, fcount))        
    ll = ul + 1 #current upper limit, plus 1, becomes new lower limit
    ul += 1000 #add 1000 for the new upper limit
    fcount = 0 #set count to zero for a new batch of 1000 numbers

import time

a,b=0,1
def fibton(n):
    if n==1:
        time.clock()
        return 0,time.clock()
    elif n==2:
        time.clock()
        return 1,time.clock()
    elif n%2==0:
        read="b"
    elif n%2==1:
        read="a"
    else:
        time.clock()
        for i in range(1,int(n/2)):
            a,b=a+b,a+b
        if read=="b":
            return b,time.clock()
        elif read=="a":
            return.a,time.clock()

avertissement: je suis actuellement sur un appareil mobile et cela peut ne pas être totalement correct

cet algorithme utilise un écart chez certains autres peuples et maintenant il est littéralement deux fois plus rapide. Au lieu de simplement définir b égal à a ou vice versa et ensuite définir a à a+b , je le fais deux fois avec seulement 2 caractères supplémentaires. J'ai aussi ajouté le test de vitesse, basé sur la façon dont mon autre algorithme itératif est allé. Ce devrait être en mesure pour atteindre le 200000ème numéro de Fibonacci en une seconde. Il renvoie aussi la longueur du nombre au lieu du nombre entier, ce qui prendrait une éternité.

mon autre pouvait aller au deuxième numéro Fibonacci, comme indiqué par l'horloge intégrée: en 10^-6 secondes. Cela on peut le faire en 5^-6. Je vais bientôt avoir des algorithmes plus avancés et les affiner pour une vitesse maximale.

pour spécifiquement votre programme, vous pouvez utiliser le code suivant

def fib (n): 
if( n == 0):
    return 0
else:
    x = 0 
    y = 1 
    for i in range(1,n):
        y =y+x
        x=y
    return y

for i in range(10):
    print (fib(i))

Ici, x est l'ancienne valeur et y est la valeur actuelle. Dans la boucle, remplacer y (valeur courante) par y+x (valeur courante + ancienne valeur), puis attribuer la valeur courante à x.Print valeur courante