ti-enxame.com

Um algoritmo iterativo para números de Fibonacci

Estou interessado em um algoritmo iterativo para números de Fibonacci, então encontrei a fórmula no wiki ... parece simples, então tentei em Python ... não tem problema em compilar e a fórmula parece correta ... não certo por que está dando a saída errada ... eu não a implementei certo?

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

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

saída


Nenhum
1
1
1
1
1
1

15
Ris

O problema é que seu return y Está dentro do loop de sua função. Portanto, após a primeira iteração, ele já parará e retornará o primeiro valor: 1. Exceto quando n for 0; nesse caso, a função será criada para retornar o próprio 0 E, no caso n é 1, quando o loop for não itera nem uma vez e nenhum return está sendo executado (daí o valor de retorno None).

Para corrigir isso, basta mover o return y Para fora do loop.

Implementação alternativa

Seguindo o exemplo do KebertX, aqui está uma solução que eu pessoalmente faria em Python. Obviamente, se você processar muitos valores de Fibonacci, poderá combinar essas duas soluções e criar um cache para os números.

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

Você está retornando um valor dentro de um loop, para que a função saia antes que o valor de y chegue a ser maior que 1.

Se eu puder sugerir algo mais curto e muito mais pythonful:

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

Isso fará exatamente a mesma coisa que o seu algoritmo, mas em vez de criar três variáveis ​​temporárias, apenas as adiciona a uma lista e retorna o enésimo número de fibonacci pelo índice.

4
KebertX

Sequência de Fibonacci não recursiva em 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)

Saída: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

1
karuna

Em fib (0), você retorna 0 porque:

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

Em fib (1), você está retornando 1 porque:

y = 1
return y

Na figura (2), você retornará 1 porque:

y = 1
return y

...e assim por diante. Enquanto return y está dentro do seu loop, a função termina sempre na primeira iteração do seu loop for.

Aqui está uma boa solução que outro usuário apresentou: Como escrever a sequência de Fibonacci em Python

1
John Hornsby

Outra abordagem possível:

a=0
b=1
d=[a,b]
n=int(input("Enter a number"))
i=2
while i<n:
    e=d[-1]+d[-2]
    d.append(e)
    i+=1
print("Fibonacci series of {} is {}".format(n,d))
0
Loki

Este trabalho ( intuitivamente )

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
0
MsO

Que tal essa maneira simples, mas mais rápida ... (Acabei de descobrir!)

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

Nota! como resultado, esse algoritmo simples usa apenas 1 atribuição e 1 adição, pois o comprimento do loop é reduzido em 1/2 e cada loop inclui 2 atribuições e 2 adições.

0
digitect38
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
0
Jedi_Jezzi
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 com atribuição paralela:

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

fibiter de impressão (4)

0
Andrei Volokitin

Me deparei com isso em outro segmento e é significativamente mais rápido do que qualquer outra coisa que eu tentei e não demorará muito tempo. Aqui está um link para a matemática.

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
0
user3464678