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.

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:

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 ⁿ ) w czasie.

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

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!

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

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

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.

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:

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

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]

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

Wiemy to

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

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

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

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.

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)

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

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

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

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

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]

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

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]

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

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.

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.

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)

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)

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

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

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

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

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

...

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

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

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ą.