Hvordan skrive Fibonacci sekvensen i Python – Stack Overflow

Hvordan skrive Fibonacci sekvensen i Python - Stack Overflow

Jeg hadde opprinnelig kodet programmet feilaktig. I stedet for å returnere Fibonacci tall mellom et utvalg (ie. Startnummer 1, endNumber 20 burde = kun disse numrene mellom en & 20), har jeg skrevet til programmet for å vise alle Fibonacci tall mellom et utvalg (ie. Startnummer 1, endNumber 20 skjermer = 20 første Fibonacci tall). Jeg trodde jeg hadde en sikker-brann kode. Jeg ser ikke hvorfor dette skjer.

Noen påpekte i min del II (som ble stengt for å være et duplikat – http://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii) at jeg må bestå startnummer og endNumber gjennom en generator ved hjelp av en stund loop. Kan noen vennligst peke meg i retning av hvordan du gjør dette? Alle hjelpe er velkomne.

Jeg er en lærings programmerer og jeg har kjørt inn i en bit av et virvar. Jeg er bedt om å skrive et program som vil beregne og vise Fibonacci av en bruker matet inn startnummer og slutt nummer (ie. Startnummer = 20 endNumber = 100, og det vil bare vise tallene mellom dette området). Trikset er å bruke den inkluderende (som jeg ikke vet hvordan de skal gjøre i Python? – Jeg antar at dette betyr å bruke et inkluderende rekkevidde?).

Hva jeg har så langt er ingen faktiske koding, men heller:

  • Skriv Fib sekvens formel til uendelig
  • Vis startnummer til endNumber bare fra Fib sekvens.

Jeg aner ikke hvor du skal begynne, og jeg ber om ideer eller innsikt i hvordan å skrive dette. Jeg har også prøvd å skrive Fib sekvens forumla men jeg tapt på det også.

spurte 30 januar ’09 på 05:49

34 svar

Det er massevis av informasjon om Fibonacci Sequence på wikipedia og på wolfram. Mye mer enn du trenger. Allikevel er det en god ting å lære å bruke disse ressursene for å finne (raskt hvis mulig) hva du trenger.

Skriv Fib sekvens formel til uendelig

I matematikk, er det gitt i en rekursiv form:

I programmering, uendelig finnes ikke. Du kan bruke en rekursiv skjema sette matematikk skjemaet direkte på ditt språk, for eksempel i Python blir det:

Prøv det i din favoritt språket og se at dette skjemaet krever mye tid som n blir større. Faktisk er dette O (2-n) i tide.

Gå på på nettstedene jeg knyttet til deg og vil se denne (på wolfram):

Dette er ganske enkelt å implementere og veldig, veldig fort å beregne, i Python:

En annen måte å gjøre det på er følgende definisjon (fra wikipedia):

Det første tallet i sekvensen er 0, det andre tall er 1, og hver etterfølgende rekke er lik summen av de to forutgående antall sekvensen i seg selv, hvilket ga den sekvens 0, 1, 1, 2, 3, 5, 8 , etc.

Hvis språket støtter iteratorer kan du gjøre noe sånt som:

Vis startnummer til endNumber bare fra Fib sekvens.

Når du vet hvordan å generere Fibonacci tall du må bare sykle gjennom tallene og se om de bekrefte de gitte forhold.

Anta nå at du skrev en f (n) som returnerer n-te løpetid Fibonacci Sequence (som den med sqrt (5))

I de fleste språk kan du gjøre noe sånt som:

I python vil jeg bruke iterator form og gå for:

Mitt tips er å lære å lese hva du trenger. Prosjekt Euler (google for det) vil trene deg til å gjøre det: P Lykke til og ha det gøy!

Prøv å gjøre, for hånd, et eksempel på input-output fra programmet (med en kort rekkevidde). Prøv deretter å finne ut hvor programmet er feil. Prøv å konvertere "for-hånd-metoden" i kode. Dette er for trening, for å lære. Jeg kunne legge ned to linjer med kode, men jeg tror ikke du vil lære noe fra dem. – Andrea Ambu 3 februar ’09 på 23:11

Effektiv Pytonske generator av Fibonacci-sekvensen

Jeg fant dette spørsmålet mens du prøver å få kortest Pytonske generasjon av denne sekvensen (senere innser jeg hadde sett en lignende en i en Python Enhancement Proposal), og jeg har ikke lagt merke til noen andre kommer opp med min bestemt løsning (selv om toppen svar blir tett, men likevel mindre elegant), så her er det, med kommentarer som beskriver den første iterasjon, fordi jeg tror det kan hjelpe leserne forstå:

(For navngivelse formål, jeg har nylig lagt merke til en lignende gjennomføring i Python dokumentasjon på moduler, selv ved hjelp av variablene a og b. Som jeg nå husker å ha sett før du skriver dette svaret. Men jeg tror dette svaret viser bedre bruk av språket.)

Rekursivt definert implementering

The Online Encyclopedia of heltallssekvenser definerer Fibonacci Sequence rekursivt som

F (n) = F (n-1) + F (n-2) med F (0) = 0 og F (1) = 1

Konsist definere dette rekursivt i Python kan gjøres på følgende måte:

Men dette nøyaktig representasjon av den matematiske definisjonen er utrolig ineffektivt for tallene mye større enn 30, fordi hvert nummer blir beregnet må også beregne for hvert nummer under. Du kan vise hvor sakte det er ved hjelp av følgende:

Memoized rekursjon for effektivitet

Det kan memoized å forbedre hastigheten (dette eksempelet utnytter det faktum at en standard søkeord argument er det samme objektet hver gang funksjonen kalles, men normalt du ikke vil bruke en foranderlig standard argument for nettopp denne grunn):

Du finner memoized versjonen er mye raskere, og vil raskt overstige det høyeste rekursjon dybde før du kan begynne å tenke å stå opp for kaffe. Du kan se hvor mye raskere det er visuelt ved å gjøre dette:

(Det kan virke som vi kan bare gjøre det under, men det er faktisk ikke la oss dra nytte av bufferen, fordi det kaller seg før setdefault kalles.)

svarte 20 juli ’14 på 02:24

Ideen bak Fibonacci sekvensen er vist i følgende Python-kode:

Dette betyr at løgn er en funksjon som kan gjøre en av tre ting. Det definerer fib (1) == 1, fib (0) == 0, og fib (n) til å være:

Hvor n er et vilkårlig helt tall. Dette betyr at fib (2) for eksempel, utvides ut til den aritmetiske følgende:

Vi kan beregne fib (3) på samme måte med den aritmetiske vist nedenfor:

Det som er viktig å innse her er at fib (3) kan ikke beregnes uten beregning fib (2), som beregnes ved å vite definisjonen av fib (1) og fib (0). Å ha en funksjon samtale seg selv som den fibonacci funksjonen ikke kalles rekursjon, og det er et viktig tema i programmering.

Dette høres ut som en hjemmelekse slik at jeg ikke kommer til å gjøre start / slutt del for deg. Python er et fantastisk uttrykksfullt språk for dette selv, så dette bør være fornuftig hvis du forstår matematikk, og vil forhåpentligvis lære deg om rekursjon. Lykke til!

Edit: En mulig kritikk av koden min er at den ikke bruker super-hendig Python funksjon avkastning, noe som gjør den liten løgn (n) fungere mye kortere. Mitt eksempel er litt mer generisk men siden ikke mange språk utenfor Python har faktisk avkastning.

svarte 30 januar ’09 6:15

Jeg forstår at du prøver veldig hardt å gjennomføre et program som kan være utenfor din nåværende evne. Å ha meg til å skrive mer kode vil ikke hjelpe deg. Du bør prøve å hacke rundt med min kode før det fungerer, og lese flere Python tutorials. Mellomrom kan være et problem, men jeg vet ikke at feilen. – James Thompson 30 januar ’09 på 06:39

Dette er ganske effektiv, bruker O (log n) regningsartene.

Denne bruker O (1) grunnleggende aritmetiske operasjoner, men størrelsen av de mellomliggende resultater er stor og det er ikke effektiv i det hele tatt.

Denne beregner X ^ n i polynomet ring Z [X] / (X ^ 2 – X – 1) med potenser av kvadrere. Resultatet av denne beregningen er det polynom Fib (n) X + Fib (n-1), fra hvilken den n-te Fibonacci tall kan avleses.

Igjen, bruker denne O (log n) aritmetiske operasjoner og er veldig effektiv.

15 minutter inn en tutorial jeg brukte da lære Python, spurte leseren til å skrive et program som skulle beregne en Fibonacci-sekvensen fra 3 inngangsnummer (første Fibonacci-tall, andre nummer, og nummeret på å stoppe sekvensen). Opplæringen hadde bare dekket variabler, hvis / thens, og looper opp til det punktet. Ingen funksjoner ennå. Jeg kom opp med følgende kode:

Som du kan se, er det virkelig ineffektivt, men det fungerer.

svarte 24 oktober ’11 på 07:53

svarte 11 april ’13 på 13:53

Bare gå gjennom http://projecteuler.net/problem=2 dette var min ta på den

svarte 12 september ’13 på 11:53

svarte 24 november ’13 på 01:09

Han er nok ikke den første personen til å tildele det som en jobb å gjøre. Men det er kjempebra å finne det ut selv. Jeg lærte mye å finne det ut faktisk, og det var en blast.

Jeg anbefaler at du finne det ut selv før du prøver og kopiere andres kode for lekser.

I videoen ovenfor, Sal instruktøren viser forestillinger hele teorien bak Fibonacci-tall, og med det i tankene bør du være i stand til å finne det ut.

Det tok meg ca 10 minutter, og dette er koden jeg har gjort (jeg lærer Python starter 3 dager siden, og dette er min første programmeringsspråk for å lære). Jeg ville ikke ha vært i stand til å skrive koden hvis det ikke var for video fra opplæringen før: https://www.khanacademy.org/science/computer-science-subject/computer-science/v/comparing-iterative- og-rekursive-faktorielle-funksjoner som man gir et eksempel på Sal gjør en rekursiv fakultet ligning og gir deg mind-set for å løse dette problemet.

Her er min kode:

Du kan se at hvis tallet er 1 eller 0 så du bare returnere antall.

Jeg finner dette renere enn å si om tallet er en retur 1 og hvis tallet er 0 return 0.

svarte 28 januar ’14 på 07:44

Kanskje dette vil hjelpe

svarte 7 mars ’14 på 19:11

svarte 7 desember ’14 på 14:50

basert på klassiske fibonacci sekvens og bare for moro skyld av one-liners

hvis du bare trenger antall indeksen, kan du bruke redusere (selv om redusere det ikke er best egnet for dette kan det være en god øvelse)

og for å få komplett utvalg bare fjerne den eller (r.pop (0) og 0)

svarte 11 februar ’15 på 18:01

Hva med denne? Jeg antar at det er ikke så fancy som de andre forslagene, fordi det krever den første spesifikasjonen av forrige resultat for å produsere den forventede effekt, men jeg føler er en veldig lesbart alternativ, dvs. alt den gjør er å gi resultatet og den forrige resultatet til rekursjon.

Her er resultatet:

svarte 22 februar ’15 på 14:58

En mer detaljert forklaring på hvordan Memoization fungerer for Fibonacci-sekvensen.

svarte 17 desember ’15 på 06:47

Jeg prøvde å unngå en rekursiv funksjon for å løse dette problemet, så jeg tok en iterativ tilnærming. Jeg var opprinnelig å gjøre en memoized rekursiv funksjon, men holdt trykket maks rekursiv dybde. Jeg hadde også strenge minne mål slik at du vil se meg holde rekken så liten som jeg kan i løpet av looping prosessen bare holde 2-3 verdiene i matrisen til enhver tid.

Får 6 million fibonacci tall tar ca 282 sekunder på min maskin mens 600k fibonacci tar bare 2,8 sekunder. Jeg var ikke i stand til å få så store fibonacci tall med en rekursiv funksjon, selv en memoized en.

svarte des 31 ’15 på 05:51

Fibonacci sekvens er: 1, 1, 2, 3, 5, 8.

Det er f (1) = 1. f (2) = 1. f (3) = 2 f (n) = f (n-1) + f (n-2).

Min favoritt implementering (enkleste og likevel oppnår en lysets hastighet i forhold til andre implementeringer) er dette:

svarte 14 mars ’16 på 09:33

Jeg gjorde en litt interaktiv python Fibonacci Sequence, det spør hvor mange ganger du vil at den skal gjenta, da det viser deg de tallene i Fibonacci sekvensen. Her er koden .

svarte aug 16 ’16 på 22:47

Rekursjon legger tid. For å eliminere looper, først import matematikk. Deretter bruker Math.sqrt og golden ratio i en funksjon:

svarte 29 august ’16 på 20:23

Når en rekursiv script (looping) overstiger maksimal rekursjon dybde. skriptet vil krasje med en RuntimeError grunn Pythons endelig stack størrelse. den fryktede stack overflow. – noobninja Aug 29 ’16 på 23:22

2017 Stack Exchange Inc

Kilde: stackoverflow.com

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert. Obligatoriske felt er merket med *

one + 6 =