Un algorithme itératif pour des nombres de Fibonacci

Le problème, c'est que votre return y est à l'intérieur de la boucle de votre fonction. Ainsi, après la première itération, c'est déjà s'arrêter et de revenir à la première valeur: 1. Sauf quand n est 0, la fonction est prise pour un retour 0 lui-même, et dans le cas n est de 1, lorsque la boucle itère pas même une seule fois, et pas de return est en cours d'exécution (d'où le None valeur de retour).

Pour résoudre ce problème, il suffit de déplacer le return y à l'extérieur de la boucle.

Alternative de mise en œuvre

Suivantes KebertX l'exemple, voici une solution, je serais personnellement faire en Python. Bien sûr, si vous étiez à traiter un grand nombre de Fibonacci valeurs, vous pouvez même souhaitez combiner ces deux solutions et de créer un cache pour les nombres.

def f(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

OriginalL'auteur poke

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. Aussi longtemps que return y est à l'intérieur de la boucle, la fonction se termine sur la première itération de ta boucle for à chaque fois.

Voici une bonne solution à un autre utilisateur de venu avec:
Comment écrire la suite de Fibonacci en Python

OriginalL'auteur John Hornsby

En supposant que ces valeurs de la suite de fibonacci:

F(0) = 0;

F(1) = 1;

F(2) = 1;

F(3) = 2

Pour des 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, nous pouvons prendre ce qui est du calcul de fibonacci à partir de N = 0 à N = Target_N, comme nous le faisons, nous pouvons garder une trace de la précédente, les résultats 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; 
}

OriginalL'auteur yadriel

Je suis tombé sur ce sur un autre thread et il est nettement plus rapide que n'importe quoi d'autre que j'ai essayé et pas de temps sur les grands nombres. Voici une lien pour les 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

OriginalL'auteur user3464678

Comment à ce sujet simple, mais la façon 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]

Remarque! en conséquence, ce simple algorithme utilise seulement 1 affectation et 1 plus, puisque la longueur de la boucle est de raccourcir comme 1/2 et chaque boucle comprend 2 affectation et 2 ajouts.

OriginalL'auteur digitect38

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 tout à fait correcte

Cet algorithme utilise une lacune dans certains autres peuples, et maintenant, il est littéralement à deux fois plus rapide. Au lieu de juste mettre b égal à a ou vice-versa, puis la configuration a à a+b, je le fais deux fois avec seulement 2 caractères. J'ai aussi ajouté de la vitesse de test, basé sur la façon dont mon autre algorithme itératif est allé. Ce devrait être en mesure d'aller sur les 200 000 ème nombre de Fibonacci en une seconde. Il renvoie également à la longueur de la le nombre à la place du nombre entier, ce qui prendrait une éternité.

Mon autre pourrait aller à la deuxième le nombre de Fibonacci, comme indiqué par l'horloge intégrée: dans 10^-6 secondes. Cela on peut le faire en 5^-6. Je vais avoir quelques algorithmes avancés bientôt et les affiner pour une plus grande vitesse.

OriginalL'auteur tony