Hvordan skriver man Fibonacci-sekvensen?

Jeg havde oprindeligt kodet programmet forkert. I stedet for at returnere Fibonacci-tallene mellem et interval (dvs. startNumber 1, endNumber 20 skal = kun tallene mellem 1 & 20), har jeg skrevet, at programmet skal vise alle Fibonacci-tallene mellem et interval (dvs. startNumber 1, endNumber 20 viser = de første 20 Fibonacci-tal). Jeg troede at jeg havde en sikker kode. Jeg kan heller ikke se hvorfor dette sker.

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

Nogen gjorde mig opmærksom på i min del II (som blev lukket for at være en dublet - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii) at jeg skal sende startNumber og endNumber gennem en generator ved hjælp af en while loop. Kan nogen venligst pege mig i retning af, hvordan jeg skal gøre dette? Enhver hjælp er velkommen.

I'm en læring programmør og I've løb ind i en lidt af en jumble. Jeg er blevet bedt om at skrive et program, der vil beregne og vise Fibonacci's Sequence ved en bruger indtastet startnummer og slutnummer (dvs. startNumber = 20 endNumber = 100 og det vil kun vise tallene mellem dette interval). Tricket er at bruge det inklusivt (som jeg ikke ved hvordan man gør i Python? - I'm antager, at det betyder at bruge et inkluderende område?).

Det jeg har indtil videre er ingen egentlig kodning, men snarere:

  • Skriv Fib-sekvensformel til uendelig
  • Vis startNumber til endNumber kun fra Fib sekvens.

Jeg har ingen idé om hvor jeg skal starte og jeg beder om ideer eller indsigt i hvordan jeg skal skrive dette. Jeg har også prøvet at skrive Fib-sekvens forumla men jeg bliver også tabt på det.

martineau
Redigeret spørgsmål 2018ør januar 2018 в 1:42
Programmering
python sequences fibonacci
2009ør januar 2009 в 5:49
3 visninger
Løsning

Der er masser af oplysninger om Fibonacci-sekvensen på [wikipedia][1] og på [wolfram][2]. Meget mere end du måske har brug for. Under alle omstændigheder er det en god ting at lære at bruge disse ressourcer til at finde (hurtigt, hvis muligt) det, du har brug for.

Skriv Fib sekvensformel til uendelig

I matematik er det'givet i en rekursiv form:

![fibonacci fra wikipedia][3]

I programmering findes infinite ikke. Du kan bruge en rekursiv form, der oversætter den matematiske form direkte i dit sprog, for eksempel i Python bliver det:

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

Prøv det i dit yndlingssprog og se, at denne form kræver meget meget** tid, når n bliver større. Faktisk er det O(2n) i tid.

Gå videre på de websteder, som jeg har linket til dig, og du vil se dette (på wolfram)):

[![Fibonacci-ligningen][4]]][4]

Denne er ret nem at implementere og meget, meget hurtig at beregne, i Python:

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

En anden måde at gøre det på er at følge definitionen (fra wikipedia)):

Det første tal i sekvensen er 0, det andet tal er 1, og hvert efterfølgende tal er lig med summen af de to foregående tal i sekvensen sekvensen selv, hvilket giver sekvensen 0, 1, 1, 1, 2, 3, 5, 8 osv.

Hvis dit sprog understøtter iteratorer, kan du gøre noget i stil med:

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

Vis kun startNummer til slutNummer fra Fib-sekvens.

Når du ved, hvordan du genererer Fibonacci-tal, skal du blot cykle tallene igennem og kontrollere, om de opfylder de givne betingelser.

Antag nu, at du har skrevet en f(n), der returnerer den n-te term af Fibonacci-sekvensen (som den med sqrt(5) )

I de fleste sprog kan du gøre noget i stil med:


def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur
Tony Edgecombe
Redigeret svar 2017ør september 2017 в 12:47
Kommentarer (14)

Idéen bag Fibonacci-sekvensen er vist i følgende Python-kode:

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

Det betyder, at fib er en funktion, der kan gøre en af tre ting. Den definerer fib(1) == 1, fib(0) == 0, og fib(n) til at være:

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

Hvor n er et vilkårligt heltal. Det betyder, at fib(2) f.eks. udvider sig til følgende aritmetik:

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

Vi kan beregne fib(3) på samme måde med den nedenfor viste aritmetik:

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

Det vigtige at indse her er, at fib(3) ikke kan beregnes uden at beregne fib(2), som beregnes ved at kende definitionerne af fib(1) og fib(0). At en funktion kalder sig selv, som fibonacci-funktionen gør, kaldes rekursion, og det er et vigtigt emne inden for programmering.

Dette lyder som en hjemmeopgave, så jeg vil ikke lave start/slut-delen for dig. Python er dog et vidunderligt udtryksfuldt sprog til dette, så dette burde give mening hvis du forstår matematik, og vil forhåbentlig lære dig om rekursion. Held og lykke!

Edit: En potentiel kritik af min kode er, at den ikke bruger den superhåndterede Python-funktion yield, som gør fib(n)-funktionen meget kortere. Mit eksempel er dog lidt mere generisk, da ikke mange sprog uden for Python faktisk har yield.

Kommentarer (5)
 
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)
sloth
Redigeret svar 2012ør august 2012 в 2:19
Kommentarer (1)