Jak napisać ciąg Fibonacciego?

140

Początkowo błędnie zakodowałem program. Zamiast zwracać liczby Fibonacciego między zakresem (tj. StartNumber 1, endNumber 20 powinno = tylko te liczby między 1 a 20), napisałem, aby program wyświetlał wszystkie liczby Fibonacciego między zakresem (tj. StartNumber 1, endNumber 20 wyświetla = pierwsze 20 liczb Fibonacciego). Myślałem, że mam pewny kod. Nie rozumiem też, dlaczego tak się dzieje.

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))

Ktoś wskazał w mojej części II (która została zamknięta jako duplikat - /programming/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ), że ja trzeba przekazać startNumber i endNumber przez generator przy użyciu pętli while. Czy ktoś może mi wskazać, jak to zrobić? Każda pomoc jest mile widziana.


Jestem programistą uczącym się i wpadłem w kłopoty. Jestem poproszony o napisanie programu, który będzie obliczał i wyświetlał Sekwencję Fibonacciego przez wprowadzony przez użytkownika numer początkowy i końcowy (tj. StartNumber = 20 endNumber = 100 i wyświetli tylko liczby z tego zakresu). Sztuczka polega na tym, aby używać go w sposób włączający (czego nie wiem, jak to zrobić w Pythonie? - zakładam, że oznacza to użycie zakresu włączającego?).

Jak dotąd nie mam faktycznego kodowania, ale raczej:

  • Napisz wzór sekwencji Fib do nieskończoności
  • Wyświetl startNumber do endNumber tylko z sekwencji Fib.

Nie mam pojęcia, od czego zacząć i proszę o pomysły lub wgląd w to, jak to napisać. Próbowałem też napisać forumla sekwencji Fib, ale też się na tym pogubiłem.

SD.
źródło

Odpowiedzi:

257

Na Wikipedii i wolframie jest wiele informacji o Sekwencji Fibonacciego . O wiele więcej, niż możesz potrzebować. W każdym razie dobrze jest nauczyć się korzystać z tych zasobów, aby znaleźć (jeśli to możliwe szybko) to, czego potrzebujesz.

Napisz wzór sekwencji Fib do nieskończoności

W matematyce jest podawany w formie rekurencyjnej:

fibonacci z wikipedii

W programowaniu nieskończoność nie istnieje. Możesz użyć formy rekurencyjnej, tłumacząc formę matematyczną bezpośrednio w swoim języku, na przykład w Pythonie staje się to:

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

Wypróbuj go w swoim ulubionym języku i przekonaj się, że ten formularz wymaga dużo czasu, ponieważ n rośnie. W rzeczywistości jest to O (2 n ) w czasie.

Wejdź na strony, które z Tobą połączyłem i zobaczę to (na wolframie ):

Równanie Fibonacciego

Ten jest dość łatwy do zaimplementowania i bardzo, bardzo szybki do obliczenia, w Pythonie:

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

Innym sposobem na to jest zastosowanie się do definicji (z Wikipedii ):

Pierwsza liczba w ciągu to 0, druga liczba to 1, a każda kolejna liczba jest równa sumie dwóch poprzednich liczb z samej sekwencji, co daje ciąg 0, 1, 1, 2, 3, 5, 8 itp.

Jeśli twój język obsługuje iteratory, możesz zrobić coś takiego:

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

Wyświetl startNumber do endNumber tylko z sekwencji Fib.

Kiedy już wiesz, jak generować liczby Fibonacciego, wystarczy przejść przez kolejne liczby i sprawdzić, czy weryfikują one podane warunki.

Załóżmy, że teraz napisałeś af (n), który zwraca n-ty człon ciągu Fibonacciego (jak ten z sqrt (5))

W większości języków możesz zrobić coś takiego:

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

W Pythonie użyłbym formularza iteratora i wybrałbym:

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

Moja rada to nauczyć się czytać, czego potrzebujesz. Project Euler (google for it) nauczy Cię tego: P Powodzenia i baw się dobrze!

Andrea Ambu
źródło
1
Musisz użyć pętli while, a nie mapy. Spróbuj samodzielnie to rozgryźć, a jeśli nie możesz tego zrobić, wróć z kodem. Nie jestem leniwy (kod jest krótszy niż ten komentarz). Robię to dla Ciebie, wypróbuj to z podpowiedzią "while";) Jeśli masz z tym problem, wróć ponownie;)
Andrea Ambu
Wróciłem, lol. Pozbyłem się funkcji map (range) i używam tylko funkcji range (startNumber, endNumber). Teraz mam problem, gdzie użyć instrukcji while. Próbuję na początku funkcji, ale oczywiście jest mnóstwo gotowych linii błędu. Gdzie mam to umieścić? Dzięki
SD.
Spróbuj zrobić ręcznie przykład wejścia-wyjścia twojego programu (z krótkim zakresem). Spróbuj więc dowiedzieć się, gdzie twój program jest zły. Spróbuj przekonwertować w kodzie „metodę ręczną”. To służy do ćwiczeń, do nauki. Mógłbym zapisać dwie linijki kodu, ale nie sądzę, żebyś się z nich czegoś nauczył.
Andrea Ambu,
1
Powinniśmy wykorzystać int(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5)))jakieś pomysły? @AndreaAmbu
lord63. j
3
@ lord63.j, powinieneś używać tej formuły tylko wtedy, gdy jesteś świadomy, że zaczyna odbiegać od rzeczywistej wartości, gdy njest powyżej 70 i wybucha, OverflowError gdy kiedy njest nieco powyżej 600. Inne podejścia mogą obsłużyć n1000 lub więcej bez dmuchania wzrost lub utrata precyzji.
cdlane
66

Wydajny Pythonic generator ciągu Fibonacciego

Znalazłem to pytanie, próbując uzyskać najkrótszą generację tej sekwencji w Pythonie (później zdałem sobie sprawę, że widziałem podobne w propozycji rozszerzenia Pythona ) i nie zauważyłem nikogo innego wymyślającego moje konkretne rozwiązanie (chociaż najlepsza odpowiedź zbliża się, ale jeszcze mniej elegancko), więc oto jest, z komentarzami opisującymi pierwszą iterację, bo myślę, że to może pomóc czytelnikom zrozumieć:

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)

i zastosowanie:

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

wydruki:

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

(Dla celów atrybucji zauważyłem ostatnio podobną implementację w dokumentacji Pythona na temat modułów, nawet przy użyciu zmiennych ai b, którą teraz pamiętam, widziałem przed napisaniem tej odpowiedzi. Ale myślę, że ta odpowiedź pokazuje lepsze użycie języka.)

Implementacja definiowana rekurencyjnie

Online Encyclopedia of Integer sekwencji definiuje Fibonacciego rekurencyjnie jako

F (n) = F (n-1) + F (n-2) przy F (0) = 0 i F (1) = 1

Zwięzłe zdefiniowanie tego rekurencyjnego w Pythonie można wykonać w następujący sposób:

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

Ale ta dokładna reprezentacja definicji matematycznej jest niewiarygodnie nieefektywna dla liczb znacznie większych niż 30, ponieważ każda obliczana liczba musi również obliczyć każdą liczbę poniżej niej. Możesz zademonstrować, jak powolne jest to, używając:

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

Zapamiętana rekursja dla wydajności

Można go zapamiętać w celu zwiększenia szybkości (w tym przykładzie wykorzystuje się fakt, że domyślny argument słowa kluczowego jest tym samym obiektem za każdym razem, gdy wywoływana jest funkcja, ale normalnie nie używałbyś zmiennego argumentu domyślnego z tego właśnie powodu):

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

Przekonasz się, że zapamiętana wersja jest znacznie szybsza i szybko przekroczy maksymalną głębokość rekursji, zanim będziesz mógł nawet pomyśleć o wstaniu na kawę. Możesz zobaczyć, o ile szybciej jest to wizualnie, robiąc to:

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

(Może się wydawać, że możemy po prostu wykonać poniższe czynności, ale w rzeczywistości nie pozwala nam to skorzystać z pamięci podręcznej, ponieważ wywołuje się przed wywołaniem setdefault).

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

Generator definiowany rekurencyjnie:

Kiedy uczyłem się Haskell, natknąłem się na tę implementację w Haskell:

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

Wydaje mi się, że najbliżej tego, co w tej chwili mogę uzyskać w Pythonie, jest:

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

To pokazuje:

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

Może jednak wzrosnąć tylko do limitu rekursji. Zwykle 1000, podczas gdy wersja Haskell może dochodzić do 100 milionów, chociaż wykorzystuje do tego całe 8 GB pamięci mojego laptopa:

> length $ take 100000000 fib 
100000000

Zużywanie iteratora w celu uzyskania n-tej liczby Fibonacciego

Komentator pyta:

Pytanie do funkcji Fib (), która jest oparta na iteratorze: a co jeśli chcesz otrzymać n-ty, na przykład 10-ty numer fib?

Dokumentacja itertools zawiera przepis na to:

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)

i teraz:

>>> nth(fib(), 10)
55
Aaron Hall
źródło
Jeśli chodzi o ostatnią opcję '' 'nie rób tego' '', nie rozumiem, dlaczego miałaby się wywoływać przed setdefault. Czy setdefault nie ma zwracać wartości, jeśli n jest prawidłowym kluczem? Dokument mówi: „Jeśli klucz jest w słowniku, zwróć jego wartość. Jeśli nie, wstaw klucz z wartością domyślną i zwróć wartość domyślną. Domyślnie wartość domyślna to Brak”. Czego mi brakuje ?
binithb
@binithb wyrażenie wewnątrz setdefaultwywołania jest oceniane przed setdefault jest.
Aaron Hall
23

Dlaczego po prostu nie wykonać następujących czynności?

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
źródło
21

Idea sekwencji Fibonacciego jest pokazana w poniższym kodzie Pythona:

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

Oznacza to, że fib jest funkcją, która może wykonać jedną z trzech rzeczy. Definiuje fib (1) == 1, fib (0) == 0 i fib (n) jako:

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

Gdzie n jest dowolną liczbą całkowitą. Oznacza to, że na przykład fib (2) rozwija się do następującej arytmetyki:

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

Możemy obliczyć fib (3) w ten sam sposób za pomocą arytmetyki pokazanej poniżej:

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

Ważne jest, aby tutaj zdać sobie sprawę, że fib (3) nie można obliczyć bez obliczenia fib (2), które oblicza się znając definicje fib (1) i fib (0). Samo wywołanie funkcji, podobnie jak funkcja Fibonacciego, nazywa się rekurencją i jest to ważny temat w programowaniu.

To brzmi jak zadanie domowe, więc nie zamierzam robić dla ciebie części początkowej / końcowej. Python jest jednak do tego cudownie wyrazistym językiem, więc powinno to mieć sens, jeśli rozumiesz matematykę, i miejmy nadzieję, że nauczy Cię rekurencji. Powodzenia!

Edycja: Jedna potencjalna krytyka mojego kodu polega na tym, że nie używa on bardzo poręcznej wydajności funkcji Pythona, co sprawia, że ​​funkcja fib (n) jest znacznie krótsza. Mój przykład jest jednak trochę bardziej ogólny, ponieważ niewiele języków poza Pythonem faktycznie daje wyniki.

James Thompson
źródło
To nie jest problem z pracą domową, ale wow, dziękuję za odpowiedź! Rozumiem, co muszę zrobić, ale jego uruchomienie i wdrożenie jest tym, na czym utknąłem (szczególnie w przypadku wdrażania wartości danych wejściowych użytkownika). Czy możesz o tym opowiedzieć? Wciąż otrzymuję błąd <function fib at 0x0141FAF0>.
SD.
Rozumiem, że bardzo się starasz wprowadzić program, który może wykraczać poza Twoje obecne możliwości. To, że napiszę więcej kodu, nie pomoże. Powinieneś spróbować zhakować mój kod, dopóki nie zadziała, i przeczytaj więcej samouczków Pythona. Białe znaki mogą być problemem, ale nie znam tego błędu.
James Thompson,
Rozumiem. Czy jest jakiś inny pomysł, o którym myślisz, że może mi brakować? Rozumiem, jeśli nie możesz pomóc. Dziękuję za poświęcony czas.
SD.
Twój błąd <function fib at 0x0141FAF0> może być wynikiem wypowiedzenia „fib” (co odnosi się do samej funkcji) zamiast „fib ()”, które wywoła funkcję. Powodzenia.
Kiv
8
Pamiętaj, że ta naiwna rekurencyjna metoda obliczania liczb Fibonacciego może bardzo szybko doprowadzić do przepełnienia stosu (nie do witryny). Ze względów praktycznych generuj iteracyjnie lub użyj jakiegoś rodzaju zapamiętywania lub czegoś podobnego.
David Thornley
12

Złożoność czasowa:

Funkcja buforowania ogranicza normalny sposób obliczania szeregów Fibonacciego z O (2 ^ n) do O (n) poprzez eliminację powtórzeń w drzewie rekurencyjnym szeregu Fibonacciego:

wprowadź opis obrazu tutaj

Kod :

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
źródło
9

Jest to dość wydajne przy użyciu O (log n) podstawowych operacji arytmetycznych.

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

Ten wykorzystuje podstawowe operacje arytmetyczne O (1), ale rozmiar wyników pośrednich jest duży, więc wcale nie jest wydajny.

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

To oblicza X ^ n w pierścieniu wielomianowym Z [X] / (X ^ 2 - X - 1) używając potęgowania przez podniesienie do kwadratu. Wynikiem tego obliczenia jest wielomian Fib (n) X + Fib (n-1), z którego można odczytać n-tą liczbę Fibonacciego.

Ponownie, wykorzystuje to O (log n) operacji arytmetycznych i jest bardzo wydajne.

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
źródło
1
Pierwsza i trzecia technika są dobre. Druga technika jest wyłączona o 1; skutecznie musi n -= 1działać poprawnie, ale też nie działa n = 0. W każdym razie naprawdę pomogłoby mi, gdyby dodano dużo kontekstu, aby wyjaśnić, jak to działa, zwłaszcza pierwsza technika. Widzę, że masz post na paulhankin.github.io/Fibonacci
Acumenus
6

Kanoniczny kod Pythona do drukowania sekwencji Fibonacciego:

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

W przypadku problemu „Wydrukuj pierwszą liczbę Fibonacciego dłuższą niż 1000 cyfr”:

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
źródło
4

Wiemy to

wprowadź opis obrazu tutaj

I że n-ta potęga tej macierzy daje nam:

wprowadź opis obrazu tutaj

Możemy więc zaimplementować funkcję, która po prostu oblicza potęgę tej macierzy do potęgi n-tej -1.

jak wszystko, co wiemy, moc a ^ n jest równa

wprowadź opis obrazu tutaj

Więc na końcu funkcja Fibonacciego byłaby O (n) ... nic tak naprawdę nie różni się od łatwiejszej implementacji, gdyby nie fakt, że również o tym wiemy, x^n * x^n = x^2na zatem oszacowanie x^nmożna przeprowadzić ze złożonością O (log n )

Oto moja implementacja Fibonacciego przy użyciu szybkiego języka programowania:

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
}

Ma to złożoność O (log n). Obliczamy moc Q z wykładnikiem n-1, a następnie bierzemy element m00, czyli Fn + 1, który przy wykładniku potęgi n-1 jest dokładnie n-tą liczbą Fibonacciego, którą chcieliśmy.

Gdy już masz szybką funkcję Fibonacciego, możesz iterować od numeru początkowego i końcowego, aby uzyskać interesującą Cię część ciągu Fibonacciego.

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

Oczywiście najpierw przeprowadź kontrolę na początku i na końcu, aby upewnić się, że mogą tworzyć prawidłowy zakres.

Wiem, że to pytanie ma 8 lat, ale i tak dobrze się bawiłem. :)

Giuseppe Lanza
źródło
3

Ciąg Fibonacciego jest: 1, 1, 2, 3, 5, 8, ....

Oznacza to f(1) = 1, f(2) = 1, f(3) = 2, ..., f(n) = f(n-1) + f(n-2).

Moja ulubiona implementacja (najprostsza, a jednocześnie osiągająca prędkość światła w porównaniu z innymi implementacjami) to:

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

Test

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

wyczucie czasu

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

Edycja: przykładowa wizualizacja dla tych realizacji.

Aziz Alto
źródło
3

użyj rekurencji:

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
źródło
2

Inny sposób na zrobienie tego:

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

Przypisanie listy do „a”, przypisanie liczby całkowitej do „n” Map i redukuj to dwie z trzech najpotężniejszych funkcji w Pythonie. Tutaj mapa jest używana tylko do iteracji 'n-2' razy. a [-2:] otrzyma ostatnie dwa elementy tablicy. a.append (x + y) doda ostatnie dwa elementy i dołączy do tablicy

sanooj
źródło
1

To wszystko wygląda na nieco bardziej skomplikowane, niż powinno. Mój kod jest bardzo prosty i szybki:

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
źródło
2
Dynamiczne programowanie FTW! fibonacci (1000000000000000000000000000000000000000000000000000000000000000000000000000) odpowiada niemal natychmiast
Hans
6
Jakoś w to wątpię.
Lanaru
A co z rozpoczęciem listy jako [0, 1] (tj. List.append (0); List.append (1)), aby uniknąć polecenia usuwania po innym? ... a liczba Fibonacciego powinna być lepiej indeksowana, ponieważ Fibonacci (10) zwraca liczby Fibonacciego poniżej 10, a nie dziesiątą.
SEF
1

OK ... po zmęczeniu odwoływaniem się do wszystkich długich odpowiedzi, teraz znajdź poniższy sort & słodki, całkiem prosty sposób implementacji Fibonacciego w Pythonie. Możesz go ulepszyć tak, jak chcesz, uzyskując argument lub dane wejściowe użytkownika… lub zmienić limity z 10000. W razie potrzeby ……

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

To podejście również się sprawdza. Znajdź poniżej analizę uruchamiania

In [10]: %timeit fibonacci
10000000 loops, best of 3: 26.3 ns per loop
Haroon Rashedu
źródło
1

to jest ulepszenie odpowiedzi Mateusza Henry'ego:

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

kod powinien drukować b zamiast drukowania c

wyjście: 1,1,2,3,5 ....

adongo
źródło
1

Używając pętli for i wypisuj tylko wynik

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

Wynik

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

Wydrukuj listzawierający wszystkie liczby

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

Wynik

>>> fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
R__raki__
źródło
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))

Wyniki

[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 , 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 2524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433497874437, 70178734150, 70134736150 , 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 40527395805378708705376, 27876208701

czas pracy: 0,04298138618469238

Nathan Rogers
źródło
1

jest na to bardzo prosty sposób!

możesz uruchomić ten kod bezpłatnie online, korzystając z 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
źródło
łatwy sposób na zrealizowanie szeregu Fibonacciego przy użyciu iteratora, bez żadnej złożonej struktury danych rekursji!
xgqfrms
1

Można to zrobić w następujący sposób.

n = 0

liczby = [0]

dla i w zakresie (0,11):
    drukuj n,
    numbers.append (n)
    prev = liczby [-2]
    jeśli n == 0:
        n = 1
    jeszcze:
        n = n + poprz
J.Jai
źródło
1

Dla zabawy, w Pythonie 3.8+ możesz użyć wyrażenia przypisania (znanego również jako operator morsa) w zrozumieniu listowym , np .:

>>> 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]

Wyrażenie przypisania umożliwia przypisanie wartości do zmiennej i zwrócenie jej w tym samym wyrażeniu. Dlatego wyrażenie

b := a + (a := b)

jest równoważne wykonaniu

a, b = b, a + b

i zwracając wartość b.

Eugene Yarmash
źródło
0

Po 15 minutach samouczka, którego użyłem podczas nauki języka Python, poprosiłem czytelnika o napisanie programu, który obliczy ciąg Fibonacciego z 3 liczb wejściowych (pierwsza liczba Fibonacciego, druga liczba i liczba, przy której zatrzyma sekwencję). Samouczek obejmował tylko zmienne, jeśli / to i pętle do tego momentu. Nie ma jeszcze funkcji. Wymyśliłem następujący kod:

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

Jak widać, jest to naprawdę nieefektywne, ale DZIAŁA.

Jonas
źródło
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
źródło
3
eval(input())nie jest tu potrzebny; Myślę, że int(input())w przypadku jest lepiej.
GingerPlusPlus
0

Właśnie przechodząc przez http://projecteuler.net/problem=2 to było moje podejście

# 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)
Typ pliku
źródło
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
źródło
0

Może to pomoże

def fibo(n):
    result = []
    a, b = 0, 1
    while b < n:
            result.append(b)
            a, b = b, b + a
    return result
van Gogh
źródło
0

oparty na klasycznej sekwencji Fibonacciego i tylko ze względu na jednowierszowe

jeśli potrzebujesz tylko numeru indeksu, możesz użyć redukcji (nawet jeśli zmniejszasz, to nie nadaje się do tego najlepiej, może to być dobre ćwiczenie)

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]

aby uzyskać pełną tablicę, po prostu usuń or (r.pop (0) i 0)

reduce(lambda r,v: r.append(r[-1]+r[-2]) or r , xrange(last_index), [0, 1])
Kadmillos
źródło
0

A co z tym? Wydaje mi się, że nie jest tak wyszukany, jak inne sugestie, ponieważ wymaga wstępnej specyfikacji poprzedniego wyniku, aby uzyskać oczekiwany wynik, ale uważam, że jest to bardzo czytelna opcja, tj. Wszystko, co robi, to podanie wyniku i poprzedniego wyniku do rekurencja.

#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)

Oto wynik:

0
1
1
2
3
5
8
13
21
34
done
the_marcelo_r
źródło
0

Zasadniczo przetłumaczone z Rubiego:

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
źródło
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
źródło
0

Bardziej szczegółowe wyjaśnienie, jak działa memoizacja dla sekwencji Fibonacciego.

# 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
źródło
0

Próbowałem uniknąć funkcji rekurencyjnej, aby rozwiązać ten problem, więc przyjąłem podejście iteracyjne. Początkowo wykonywałem zapamiętaną funkcję rekurencyjną, ale nadal osiągałem maksymalną głębokość rekurencyjną. Miałem również ścisłe cele dotyczące pamięci, więc zobaczysz, jak utrzymuję tablicę tak małą, jak tylko potrafię podczas procesu zapętlania, utrzymując w tablicy tylko 2-3 wartości w dowolnym momencie.

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))

Uzyskanie 6-milionowej liczby Fibonacciego zajmuje około 282 sekund na moim komputerze, podczas gdy 600k Fibonacciego zajmuje tylko 2,8 sekundy. Nie udało mi się uzyskać tak dużych liczb Fibonacciego z funkcją rekurencyjną, nawet zapamiętaną.

Jared Mackey
źródło