Como escrever a sequência de Fibonacci?

140

Eu originalmente codifiquei o programa de maneira errada. Em vez de retornar os números de Fibonacci entre um intervalo (por exemplo, startNumber 1, endNumber 20 deve = apenas aqueles números entre 1 e 20), escrevi para o programa exibir todos os números de Fibonacci entre um intervalo (por exemplo, startNumber 1, endNumber 20 exibe = 20 primeiros números de Fibonacci). Eu pensei que tinha um código infalível. Também não vejo por que isso está acontecendo.

startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))

def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)

print map(fib, range(startNumber, endNumber))

Alguém apontou na minha Parte II (que foi fechada por ser uma duplicata - /programming/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ) que eu precisa passar o startNumber e endNumber através de um gerador usando um loop while. Alguém pode me indicar a direção de como fazer isso? Qualquer ajuda é bem vinda.


Sou um programador de aprendizado e me deparei com um pouco de confusão. Foi-me pedido que escrevesse um programa que computasse e exibisse a Sequência de Fibonacci por um número inicial e número final introduzidos pelo usuário (ou seja, startNumber = 20 endNumber = 100 e exibirá apenas os números entre esse intervalo). O truque é usá-lo inclusivamente (o que eu não sei fazer em Python? - Estou assumindo que isso significa usar um intervalo inclusivo?).

O que tenho até agora não é uma codificação real, mas sim:

  • Escreva a fórmula da sequência Fib para infinito
  • Exiba startNumber para endNumber apenas da sequência Fib.

Não tenho idéia por onde começar e estou pedindo idéias ou insights sobre como escrever isso. Eu também tentei escrever o fórum da sequência Fib, mas também me perco nisso.

SD.
fonte

Respostas:

257

Há muita informação sobre a sequência de Fibonacci na wikipedia e no wolfram . Muito mais do que você pode precisar. De qualquer forma, é bom aprender como usar esses recursos para encontrar (rapidamente, se possível) o que você precisa.

Escreva a fórmula da sequência Fib para infinito

Em matemática, é dado de forma recursiva:

fibonacci da wikipedia

Na programação, infinito não existe. Você pode usar um formulário recursivo traduzindo o formulário matemático diretamente no seu idioma, por exemplo, em Python, ele se torna:

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

Experimente no seu idioma favorito e veja que esse formulário requer muito tempo à medida que n aumenta. De fato, isso é O (2 n ) no tempo.

Vá nos sites que eu linkei para você e verá isso (no wolfram ):

Equação de Fibonacci

Este é muito fácil de implementar e muito, muito rápido de calcular, em Python:

from math import sqrt
def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

Uma outra maneira de fazer isso é seguir a definição (da wikipedia ):

O primeiro número da sequência é 0, o segundo número é 1 e cada número subsequente é igual à soma dos dois números anteriores da própria sequência, produzindo a sequência 0, 1, 1, 2, 3, 5, 8 , etc.

Se o seu idioma suportar iteradores, você pode fazer algo como:

def F():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b

Exiba startNumber para endNumber apenas da sequência Fib.

Depois de saber como gerar números de Fibonacci, basta percorrer os números e verificar se eles verificam as condições especificadas.

Suponha agora que você escreveu af (n) que retorna o n-ésimo termo da sequência de Fibonacci (como o que possui sqrt (5))

Na maioria dos idiomas, você pode fazer algo como:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

Em python, usaria o formulário do iterador e usaria:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

Minha dica é aprender a ler o que você precisa. O Projeto Euler (google for it) o ​​treinará para fazer isso: P Boa sorte e divirta-se!

Andrea Ambu
fonte
1
Você precisa usar um loop while, não mapear. Tente descobrir por conta própria e volte com o código, se não conseguir. Não sou preguiçoso (o código é mais curto que esse comentário). Estou fazendo isso para você, experimentá-lo com o "enquanto" dica;) Se você tem problema com isso voltar novamente;)
Andrea Ambu
Estou de volta, lol. Eu me livrei da função map (range) e estou usando apenas uma função range (startNumber, endNumber). Agora, o problema que tenho é onde usar a instrução while. Eu tento no início da função, mas é claro que há um número de linhas de erro concluídas. Onde devo colocá-lo? Thx
SD.
Tente fazer, à mão, um exemplo de entrada e saída do seu programa (com um curto intervalo). Tente então descobrir onde seu programa está errado. Tente converter o "método manual" no código. Isto é para exercitar, para aprender. Eu poderia escrever duas linhas de código, mas acho que você não aprenderá nada com elas.
Andrea Ambu
1
Devemos usar int(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))), alguma idéia? @AndreaAmbu
lord63. j
3
@ lord63.j, você só deve usar essa fórmula se estiver ciente de que ela começa a desviar do valor real quando nestá acima de 70 e explode com um OverflowError quando nestá um pouco acima de 600. Outras abordagens podem lidar com uma nde 1000 ou mais sem soprar aumentando ou perdendo a precisão.
Cdlane # 4/17
66

Gerador Python eficiente da sequência de Fibonacci

Encontrei essa pergunta ao tentar obter a geração Pythonic mais curta dessa sequência (depois percebendo que havia visto uma semelhante em uma Proposta de aprimoramento do Python ) e não notei mais ninguém surgindo com minha solução específica (embora a resposta principal fica perto, mas ainda menos elegante), então aqui está, com comentários descrevendo a primeira iteração, porque acho que isso pode ajudar os leitores a entender:

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)

e uso:

for index, fibonacci_number in zip(range(10), fib()):
     print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))

impressões:

  0:   0
  1:   1
  2:   1
  3:   2
  4:   3
  5:   5
  6:   8
  7:  13
  8:  21
  9:  34
 10:  55

(Para fins de atribuição, observei recentemente uma implementação semelhante na documentação do Python sobre módulos, mesmo usando as variáveis ae b, que agora me lembro de ter visto antes de escrever esta resposta. Mas acho que essa resposta demonstra melhor uso da linguagem.)

Implementação definida recursivamente

A Enciclopédia Online de Sequências Inteiras define a Sequência de Fibonacci recursivamente como

F (n) = F (n-1) + F (n-2) com F (0) = 0 e F (1) = 1

Definir sucintamente isso recursivamente em Python pode ser feito da seguinte maneira:

def rec_fib(n):
    '''inefficient recursive function as defined, returns Fibonacci number'''
    if n > 1:
        return rec_fib(n-1) + rec_fib(n-2)
    return n

Mas essa representação exata da definição matemática é incrivelmente ineficiente para números muito maiores que 30, porque cada número calculado também deve ser calculado para cada número abaixo dela. Você pode demonstrar como é lento usando o seguinte:

for i in range(40):
    print(i, rec_fib(i))

Recursão memorizada para eficiência

Ele pode ser memorizado para melhorar a velocidade (este exemplo aproveita o fato de que um argumento de palavra-chave padrão é o mesmo objeto toda vez que a função é chamada, mas normalmente você não usaria um argumento padrão mutável exatamente por esse motivo):

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

Você verá que a versão memorizada é muito mais rápida e rapidamente excederá sua profundidade máxima de recursão antes que você possa pensar em se levantar para tomar um café. Você pode ver o quanto mais rápido é visualmente, fazendo o seguinte:

for i in range(40):
    print(i, mem_fib(i))

(Pode parecer que podemos fazer o que está abaixo, mas na verdade não nos permite tirar proveito do cache, porque ele se chama antes que o setdefault seja chamado.)

def mem_fib(n, _cache={}):
    '''don't do this'''
    if n > 1:  
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

Gerador definido recursivamente:

Enquanto eu aprendia Haskell, me deparei com essa implementação em Haskell:

fib@(0:tfib) = 0:1: zipWith (+) fib tfib

O mais próximo que eu acho que posso chegar disso em Python no momento é:

from itertools import tee

def fib():
    yield 0
    yield 1
    # tee required, else with two fib()'s algorithm becomes quadratic
    f, tf = tee(fib()) 
    next(tf)
    for a, b in zip(f, tf):
        yield a + b

Isso demonstra:

[f for _, f in zip(range(999), fib())]

Só pode ir até o limite de recursão. Geralmente, 1000, enquanto a versão Haskell pode chegar a centenas de milhões, embora use todos os 8 GB de memória do meu laptop para fazer isso:

> length $ take 100000000 fib 
100000000

Consumindo o iterador para obter o enésimo número de fibonacci

Um comentarista pergunta:

Pergunta para a função Fib () que é baseada no iterador: e se você quiser obter o enésimo, por exemplo, o décimo número do fib?

A documentação do itertools tem uma receita para isso:

from itertools import islice

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)

e agora:

>>> nth(fib(), 10)
55
Aaron Hall
fonte
Sobre a última opção '' 'não faça isso' '', não entendo por que ela se chamaria antes de setdefault. O setdefault não deve retornar o valor se n for uma chave válida? O documento diz "Se a chave estiver no dicionário, retorne seu valor. Caso contrário, insira a chave com um valor padrão e retorne o padrão. O padrão é Nenhum". O que estou perdendo ?
Binithb #
@binithb a expressão dentro da setdefaultchamada é avaliada antes de setdefault .
Aaron Hall
23

Por que não simplesmente fazer o seguinte?

x = [1,1]
for i in range(2, 10):  
    x.append(x[-1] + x[-2]) 
print(', '.join(str(y) for y in x))
Thomas Spycher
fonte
21

A ideia por trás da sequência de Fibonacci é mostrada no seguinte código Python:

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

Isso significa que fib é uma função que pode fazer uma de três coisas. Ele define fib (1) == 1, fib (0) == 0 e fib (n) como:

fib (n-1) + fib (n-2)

Onde n é um número inteiro arbitrário. Isso significa que fib (2), por exemplo, se expande para a seguinte aritmética:

fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1

Podemos calcular fib (3) da mesma maneira com a aritmética mostrada abaixo:

fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0

O importante a entender aqui é que fib (3) não pode ser calculado sem o cálculo de fib (2), que é calculado conhecendo as definições de fib (1) e fib (0). Ter uma chamada de função em si, como a função fibonacci, é chamada recursão, e é um tópico importante na programação.

Parece uma tarefa de casa, então não vou fazer a parte inicial / final para você. O Python é uma linguagem maravilhosamente expressiva para isso, portanto, isso deve fazer sentido se você entender matemática e, esperançosamente, ensinar sobre recursão. Boa sorte!

Edit: Uma crítica em potencial ao meu código é que ele não usa o super útil rendimento da função Python, o que torna a função fib (n) muito mais curta. No entanto, meu exemplo é um pouco mais genérico, já que muitas linguagens fora do Python realmente produzem.

James Thompson
fonte
Este não é um problema de lição de casa, mas uau, obrigado pela resposta! Eu entendo o que preciso fazer, mas iniciá-lo e implementar é o que estou preso agora (especialmente com a implementação de valores de entrada do usuário). Você pode fornecer algumas dicas sobre isso? Eu continuo recebendo um erro <function fib at 0x0141FAF0>.
SD.
Entendo que você está tentando muito implementar um programa que pode estar além da sua capacidade atual. Me fazer escrever mais código não ajudará. Você deve tentar mexer no meu código até que ele funcione e ler mais tutoriais em Python. Espaço em branco pode ser um problema, mas não conheço esse erro.
James Thompson
Compreendo. Existe alguma outra idéia que você acha que posso estar perdendo? Eu entendo se você não pode ajudar no entanto. Eu agradeço pelo seu tempo.
SD.
Seu erro <function fib at 0x0141FAF0> pode ser o resultado de dizer "fib" (que se refere à própria função) em vez de "fib ()" que chamará a função. Boa sorte.
Kiv
8
Lembre-se de que esse ingênuo método recursivo de calcular números de Fibonacci pode entrar no estouro da pilha (e não no site) muito rapidamente. Para fins práticos, gere iterativamente ou use algum tipo de memorização ou algo assim.
David Thornley
12

Complexidade do tempo:

O recurso de armazenamento em cache reduz a maneira normal de calcular a série Fibonacci de O (2 ^ n) para O (n) , eliminando as repetições na árvore recursiva da série Fibonacci:

insira a descrição da imagem aqui

Código:

import sys

table = [0]*1000

def FastFib(n):
    if n<=1:
        return n
    else:
        if(table[n-1]==0):
            table[n-1] = FastFib(n-1)
        if(table[n-2]==0):
            table[n-2] = FastFib(n-2)
        table[n] = table[n-1] + table[n-2]
        return table[n]

def main():
    print('Enter a number : ')
    num = int(sys.stdin.readline())
    print(FastFib(num))

if __name__=='__main__':
    main()
Akash Rana
fonte
9

Isso é bastante eficiente, usando operações aritméticas básicas O (log n).

def fib(n):
    return pow(2 << n, n + 1, (4 << 2*n) - (2 << n) - 1) % (2 << n)

Este usa operações aritméticas básicas O (1), mas o tamanho dos resultados intermediários é grande e, portanto, não é de todo eficiente.

def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)

Este calcula X ^ n no anel polinomial Z [X] / (X ^ 2 - X - 1) usando exponenciação por quadratura. O resultado desse cálculo é o polinômio Fib (n) X + Fib (n-1), a partir do qual o enésimo número de Fibonacci pode ser lido.

Novamente, isso usa operações aritméticas O (log n) e é muito eficiente.

def mul(a, b):
        return a[0]*b[1]+a[1]*b[0]+a[0]*b[0], a[0]*b[0]+a[1]*b[1]

def fib(n):
        x, r = (1, 0), (0, 1)
        while n:
                if n & 1: r = mul(r, x)
                x = mul(x, x)
                n >>= 1
        return r[0]
Paul Hankin
fonte
1
A primeira e a terceira técnicas são boas. A segunda técnica é desativada por 1; ele efetivamente precisa n -= 1funcionar corretamente e também não funciona n = 0. De qualquer forma, realmente me ajudaria se um monte de contexto fosse adicionado para explicar como eles estão funcionando, especialmente a primeira técnica. Vejo que você tem um post em paulhankin.github.io/Fibonacci
Acumenus 4/16/16
6

Código Python canônico para imprimir a sequência de Fibonacci:

a,b=1,1
while True:
  print a,
  a,b=b,a+b       # Could also use b=a+b;a=b-a

Para o problema "Imprima o primeiro número de Fibonacci com mais de 1000 dígitos":

a,b=1,1
i=1
while len(str(a))<=1000:
  i=i+1
  a,b=b,a+b

print i,len(str(a)),a
Da Vinci
fonte
4

Nós sabemos isso

insira a descrição da imagem aqui

E que o n-ésimo poder dessa matriz nos dá:

insira a descrição da imagem aqui

Portanto, podemos implementar uma função que simplesmente calcula a potência dessa matriz com a potência n-ésima -1.

como todos sabemos o poder a ^ n é igual a

insira a descrição da imagem aqui

Portanto, no final, a função fibonacci seria O (n) ... nada realmente diferente de uma implementação mais fácil se não fosse pelo fato de também sabermos isso x^n * x^n = x^2ne a avaliação de, x^nportanto, poder ser feita com complexidade O (log n )

Aqui está minha implementação de fibonacci usando linguagem de programação rápida:

struct Mat {
    var m00: Int
    var m01: Int
    var m10: Int
    var m11: Int
}

func pow(m: Mat, n: Int) -> Mat {
    guard n > 1 else { return m }
    let temp = pow(m: m, n: n/2)

    var result = matMultiply(a: temp, b: temp)
    if n%2 != 0 {
        result = matMultiply(a: result, b: Mat(m00: 1, m01: 1, m10: 1, m11: 0))
    }
    return result
}

func matMultiply(a: Mat, b: Mat) -> Mat {
    let m00 = a.m00 * b.m00 + a.m01 * b.m10
    let m01 = a.m00 * b.m01 + a.m01 * b.m11
    let m10 = a.m10 * b.m00 + a.m11 * b.m10
    let m11 = a.m10 * b.m01 + a.m11 * b.m11

    return Mat(m00: m00, m01: m01, m10: m10, m11: m11)
}

func fibonacciFast(n: Int) -> Int {

    guard n > 0 else { return 0 }
    let m = Mat(m00: 1, m01: 1, m10: 1, m11: 0)

    return pow(m: m, n: n-1).m00
}

Isso tem complexidade O (log n). Calculamos a potência de Q com o expoente n-1 e, em seguida, pegamos o elemento m00, que é Fn + 1, que no expoente de potência n-1 é exatamente o n-ésimo número de Fibonacci que desejávamos.

Depois de ter a função rápida de fibonacci, você pode iterar do número inicial e final para obter a parte da sequência de Fibonacci em que está interessado.

let sequence = (start...end).map(fibonacciFast)

é claro que primeiro faça uma verificação no início e no fim para garantir que eles possam formar um intervalo válido.

Eu sei que a pergunta tem 8 anos, mas me diverti respondendo de qualquer maneira. :)

Giuseppe Lanza
fonte
3

Sequência de Fibonacci é: 1, 1, 2, 3, 5, 8, ....

Isto é f(1) = 1, f(2) = 1, f(3) = 2, ..., f(n) = f(n-1) + f(n-2).

Minha implementação favorita (mais simples e, no entanto, atinge uma velocidade leve em comparação com outras implementações) é a seguinte:

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

Teste

>>> [fibonacci(i) for i in range(1, 10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34]

Cronometragem

>>> %%time
>>> fibonacci(100**3)
CPU times: user 9.65 s, sys: 9.44 ms, total: 9.66 s
Wall time: 9.66 s

Editar: um exemplo de visualização para essas implementações.

Aziz Alto
fonte
3

use recursão:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
x=input('which fibonnaci do you want?')
print fib(x)
user2095044
fonte
2

Outra maneira de fazer isso:

a,n=[0,1],10
map(lambda i: reduce(lambda x,y: a.append(x+y),a[-2:]),range(n-2))

Atribuir lista a 'a', atribuir número inteiro a 'n' Map e reduzir são duas das três funções mais poderosas em python. Aqui, o mapa é usado apenas para iterar 'n-2' vezes. a [-2:] obterá os dois últimos elementos de uma matriz. a.append (x + y) adicionará os dois últimos elementos e será anexado à matriz

sanooj
fonte
1

Todos eles parecem um pouco mais complicados do que precisam. Meu código é muito simples e rápido:

def fibonacci(x):

    List = []
    f = 1
    List.append(f)
    List.append(f) #because the fibonacci sequence has two 1's at first
    while f<=x:
        f = List[-1] + List[-2]   #says that f = the sum of the last two f's in the series
        List.append(f)
    else:
        List.remove(List[-1])  #because the code lists the fibonacci number one past x. Not necessary, but defines the code better
        for i in range(0, len(List)):
        print List[i]  #prints it in series form instead of list form. Also not necessary
Timmy
fonte
2
Programação dinâmica FTW! O fibonacci (1000000000000000000000000000000000000000000000000000000000000000000000000000000000) responde quase que instantaneamente
Hans
6
De alguma forma eu duvido.
Lanaru 18/03/2015
Que tal iniciar a lista como [0, 1] (ou seja, List.append (0); List.append (1)) para evitar o comando remove depois do resto? ... e o número de fibonacci deve ser melhor indexado, pois fibonacci (10) retorna os números de fibonacci abaixo de 10, e não o 10º.
SeF
1

OK .. depois de se cansar de se referir a todas as respostas longas, agora encontre o tipo abaixo e o caminho bastante simples para implementar Fibonacci em python. Você pode aprimorá-lo da maneira que desejar, obtendo um argumento ou recebendo informações do usuário ... ou altere os limites de 10000. Conforme necessário ...

def fibonacci():
    start = 0 
    i = 1 
    lt = []
    lt.append(start)
    while start < 10000:
        start += i
        lt.append(start)
        i = sum(lt[-2:])
        lt.append(i)
    print "The Fibonaccii series: ", lt

Essa abordagem também funciona bem. Encontre a análise de execução abaixo

In [10]: %timeit fibonacci
10000000 loops, best of 3: 26.3 ns per loop
Haroon Rashedu
fonte
1

Esta é uma melhoria na resposta de Matthew Henry:

def fib(n):
    a = 0
    b = 1
    for i in range(1,n+1):
            c = a + b
            print b
            a = b
            b = c

o código deve imprimir b em vez de imprimir c

Saída: 1,1,2,3,5 ....

adongo
fonte
1

Usando for loop e imprimir apenas o resultado

def fib(n:'upto n number')->int:
    if n==0:
        return 0
    elif n==1:
        return 1
    a=0
    b=1
    for i in range(0,n-1):
        b=a+b
        a=b-a
    return b

Resultado

>>>fib(50)
12586269025
>>>>
>>> fib(100)
354224848179261915075
>>> 

Imprimir o listcontendo todos os números

def fib(n:'upto n number')->int:
    l=[0,1]
    if n==0:
        return l[0]
    elif n==1:
        return l
    a=0
    b=1
    for i in range(0,n-1):
        b=a+b
        a=b-a
        l.append(b)
    return l

Resultado

>>> fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
R__raki__
fonte
1
import time
start_time = time.time()



#recursive solution
def fib(x, y, upperLimit):
    return [x] + fib(y, (x+y), upperLimit) if x < upperLimit else [x]

#To test :

print(fib(0,1,40000000000000))
print("run time: " + str(time.time() - start_time))

Resultados

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368 R $ 1.200,00 (Bruto mensal) .Período Integral: R $ 2.000,00 (Bruto mensal) .Período Integral: R $ 2.000,00 (Bruto mensal) .Período Integral. , 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781975515575573755751557557575757575757575757575757575757565756575657565757756756756756756756756756756756756756755 em

tempo de execução: 0.04298138618469238

nathan rogers
fonte
1

existe um método muito fácil de perceber isso!

você pode executar esse código on-line livremente usando http://www.learnpython.org/

# Set the variable brian on line 3!

def fib(n):
"""This is documentation string for function. It'll be available by fib.__doc__()
Return a list containing the Fibonacci series up to n."""
result = []
a = 0
b = 1
while a < n:
    result.append(a)  # 0 1 1 2 3 5  8  (13) break
    tmp_var = b       # 1 1 2 3 5 8  13
    b = a + b         # 1 2 3 5 8 13 21
    a = tmp_var       # 1 1 2 3 5 8  13
    # print(a)
return result

print(fib(10))
# result should be this: [0, 1, 1, 2, 3, 5, 8]
xgqfrms
fonte
uma maneira fácil de realizar a série Fibonacci usando apenas o iterador, sem nenhuma estrutura de dados de recursão complexa!
Xgqfrms
1

Isso pode ser feito da seguinte maneira.

n = 0

números = [0]

para i na faixa (0,11):
    imprimir n,
    numbers.append (n)
    prev = números [-2]
    se n == 0:
        n = 1
    outro:
        n = n + anterior
J.Jai
fonte
1

Apenas por diversão, no Python 3.8+ você pode usar uma expressão de atribuição (também conhecida como operador morsa) em uma compreensão de lista, por exemplo:

>>> a, b = 0, 1
>>> [a, b] + [b := a + (a := b) for _ in range(8)]  # first 10 Fibonacci numbers
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Uma expressão de atribuição permite atribuir um valor a uma variável e retorná-lo na mesma expressão. Portanto, a expressão

b := a + (a := b)

é equivalente a executar

a, b = b, a + b

e retornando o valor de b.

Eugene Yarmash
fonte
0

Após 15 minutos de um tutorial que usei ao aprender Python, ele solicitou ao leitor que escrevesse um programa que calculasse uma sequência de Fibonacci a partir de 3 números de entrada (primeiro número de Fibonacci, segundo número e número no qual interromper a sequência). O tutorial cobriu apenas variáveis, se / então e loops até esse ponto. Ainda não há funções. Eu vim com o seguinte código:

sum = 0
endingnumber = 1                

print "\n.:Fibonacci sequence:.\n"

firstnumber = input("Enter the first number: ")
secondnumber = input("Enter the second number: ")
endingnumber = input("Enter the number to stop at: ")

if secondnumber < firstnumber:

    print "\nSecond number must be bigger than the first number!!!\n"

else:

while sum <= endingnumber:

    print firstnumber

    if secondnumber > endingnumber:

        break

    else:

        print secondnumber
        sum = firstnumber + secondnumber
        firstnumber = sum
        secondnumber = secondnumber + sum

Como você pode ver, é realmente ineficiente, mas funciona.

Jonas
fonte
0
def fib():
    a,b = 1,1
    num=eval(input("Please input what Fib number you want to be calculated: "))
    num_int=int(num-2)
    for i in range (num_int):
        a,b=b,a+b
    print(b)
AlexB
fonte
3
eval(input())não é necessário aqui; Eu acho que int(input())no caso é melhor.
GingerPlusPlus
0

Apenas passando por http://projecteuler.net/problem=2, essa foi minha opinião

# Even Fibonacci numbers
# Problem 2

def get_fibonacci(size):
    numbers = [1,2]
    while size > len(numbers):
        next_fibonacci = numbers[-1]+numbers[-2]
        numbers.append(next_fibonacci)

    print numbers

get_fibonacci(20)
Filype
fonte
0
def fib(x, y, n):
    if n < 1: 
        return x, y, n
    else: 
        return fib(y, x + y, n - 1)

print fib(0, 1, 4)
(3, 5, 0)

#
def fib(x, y, n):
    if n > 1:
        for item in fib(y, x + y, n - 1):
            yield item
    yield x, y, n

f = fib(0, 1, 12)
f.next()
(89, 144, 1)
f.next()[0]
55
jdsantiagojr
fonte
0

Talvez isso ajude

def fibo(n):
    result = []
    a, b = 0, 1
    while b < n:
            result.append(b)
            a, b = b, b + a
    return result
Van Gogh
fonte
0

baseado na sequência clássica de fibonacci e apenas por uma questão de uma linha

se você precisar apenas do número do índice, poderá usar o reduzir (mesmo que reduzir não seja mais adequado para isso, pode ser um bom exercício)

def fibonacci(index):
    return reduce(lambda r,v: r.append(r[-1]+r[-2]) or (r.pop(0) and 0) or r , xrange(index), [0, 1])[1]

e para obter a matriz completa, basta remover o ou (r.pop (0) e 0)

reduce(lambda r,v: r.append(r[-1]+r[-2]) or r , xrange(last_index), [0, 1])
Kadmillos
fonte
0

Que tal este? Eu acho que não é tão chique quanto as outras sugestões, porque exige a especificação inicial do resultado anterior para produzir a saída esperada, mas eu sinto que é uma opção muito legível, ou seja, tudo o que faz é fornecer o resultado e o resultado anterior para a recursão.

#count the number of recursions
num_rec = 0

def fibonacci(num, prev, num_rec, cycles):

    num_rec = num_rec + 1

    if num == 0 and prev == 0:
        result  = 0;
        num = 1;
    else:
        result = num + prev

    print(result)

    if num_rec == cycles:
        print("done")
    else:
        fibonacci(result, num, num_rec, cycles)

#Run the fibonacci function 10 times
fibonacci(0, 0, num_rec, 10)

Aqui está a saída:

0
1
1
2
3
5
8
13
21
34
done
the_marcelo_r
fonte
0

Traduzido basicamente de Ruby:

def fib(n):
    a = 0
    b = 1
    for i in range(1,n+1):
            c = a + b
            print c
            a = b
            b = c

...

Matthew Smith
fonte
0
def fib(lowerbound, upperbound):
    x = 0
    y = 1
    while x <= upperbound:
        if (x >= lowerbound):
            yield x
        x, y = y, x + y

startNumber = 10
endNumber = 100
for fib_sequence in fib(startNumber, endNumber):
    print "And the next number is... %d!" % fib_sequence
JayL
fonte
0

Uma explicação mais detalhada de como funciona a memorização para a sequência de Fibonacci.

# Fibonacci sequence Memoization

fib_cache = {0:0, 1:1}

def fibonacci(n):
    if n < 0:
        return -1
    if fib_cache.has_key(n):
        print "Fibonacci sequence for %d = %d cached" % (n, fib_cache[n])
        return fib_cache[n]
    else:
        fib_cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return fib_cache[n]

if __name__ == "__main__":
    print fibonacci(6)
    print fib_cache
    # fibonacci(7) reuses fibonacci(6) and fibonacci(5)
    print fibonacci(7)
    print fib_cache
sysuser
fonte
0

Eu estava tentando evitar uma função recursiva para resolver esse problema, então tomei uma abordagem iterativa. Eu estava originalmente fazendo uma função recursiva memorizada, mas continuava atingindo a profundidade recursiva máxima. Eu também tinha objetivos rígidos de memória, para que você me veja mantendo o array o menor possível durante o processo de loop, mantendo apenas 2-3 valores no array a qualquer momento.

def fib(n):
    fibs = [1, 1] # my starting array
    for f in range(2, n):
        fibs.append(fibs[-1] + fibs[-2]) # appending the new fib number
        del fibs[0] # removing the oldest number
    return fibs[-1] # returning the newest fib

print(fib(6000000))

Obter o sexto milionésimo número de fibonacci leva cerca de 282 segundos na minha máquina, enquanto o 600k fibonacci leva apenas 2,8 segundos. Não consegui obter números tão grandes de fibonacci com uma função recursiva, mesmo memorizada.

Jared Mackey
fonte