Rekursiv funksjon av Fibonacci-tallet. Fibonacci-tall: syklus og rekursjon
Koden er ment for Python 3, selv om den også skal fungere med Python 2.
Til å begynne med, la meg minne deg om definisjonen:
Fn = Fn-1 + Fn-2
Og F 1 = F 2 = 1.
Lukket formel
Vi vil hoppe over detaljene, men interesserte kan gjøre seg kjent med utledningen av formelen. Ideen er å anta at det er noen x hvor F n = x n og deretter finne x.Hva betyr det
Reduser x n-2
Løse den andregradsligningen:
Det er her det "gyldne forholdet" ϕ=(1+√5)/2 vokser. Ved å erstatte de opprinnelige verdiene og gjøre noen flere beregninger, får vi:
Det er det vi bruker til å beregne Fn.
Fra __future__ import divisjon importer matematikk def fib(n): SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int(PHI ** n / SQRT5 + 0,5)
Flink:
Raskt og enkelt for små n
Det dårlige:
Flytepunktoperasjoner er påkrevd. Stor n vil kreve større presisjon.
Ond:
Å bruke komplekse tall for å beregne F n er vakkert fra et matematisk synspunkt, men stygt fra et datasynspunkt.
Rekursjon
Den mest åpenbare løsningen er en du har sett mange ganger før, mest sannsynlig som et eksempel på hva rekursjon er. Jeg vil gjenta det igjen for fullstendighetens skyld. I Python kan det skrives på én linje:Fib = lambda n: fib(n - 1) + fib(n - 2) hvis n > 2 annet 1
Flink:
En veldig enkel implementering som følger den matematiske definisjonen
Det dårlige:
Eksponentiell utførelsestid. For store n er det veldig tregt
Ond:
Stack Overflow
Utenat
Rekursjonsløsningen har et stort problem: overlappende beregninger. Når fib(n) kalles, telles fib(n-1) og fib(n-2). Men når fib(n-1) telles, vil den telle fib(n-2) igjen uavhengig - det vil si at fib(n-2) telles to ganger. Hvis vi fortsetter argumentasjonen, vil vi se at fib(n-3) vil telles tre ganger osv. For mange veikryss.Derfor trenger du bare å huske resultatene for ikke å telle dem igjen. Denne løsningen bruker tid og minne på en lineær måte. Jeg bruker en ordbok i løsningen min, men en enkel matrise kan også brukes.
M = (0: 0, 1: 1) def fib(n): hvis n i M: returner M[n] M[n] = fib(n - 1) + fib(n - 2) returner M[n]
(I Python kan dette også gjøres ved å bruke dekoratoren, functools.lru_cache.)
Flink:
Bare gjør rekursjon til en minneløsning. Konverterer eksponentiell utførelsestid til lineær utførelse, som bruker mer minne.
Det dårlige:
Kaster bort mye minne
Ond:
Mulig stabeloverløp, akkurat som rekursjon
Dynamisk programmering
Etter å ha løst med memorering, blir det klart at vi ikke trenger alle de tidligere resultatene, men bare de to siste. Dessuten, i stedet for å starte fra fib(n) og gå bakover, kan du starte fra fib(0) og gå fremover. Følgende kode har lineær utførelsestid og fast minnebruk. I praksis vil løsningshastigheten være enda høyere, siden det ikke er rekursive funksjonskall og tilhørende arbeid. Og koden ser enklere ut.Denne løsningen blir ofte nevnt som et eksempel på dynamisk programmering.
Def fib(n): a = 0 b = 1 for __ i område(n): a, b = b, a + b returnerer a
Flink:
Fungerer raskt for liten n, enkel kode
Det dårlige:
Fortsatt lineær utførelsestid
Ond:
Ikke noe spesielt.
Matrise algebra
Og til slutt, den minst opplyste, men den mest korrekte løsningen, med klok bruk av både tid og minne. Den kan også utvides til en hvilken som helst homogen lineær sekvens. Tanken er å bruke matriser. Det er nok bare å se det
Og en generalisering av dette sier det
De to verdiene for x som vi fikk tidligere, hvorav den ene var det gylne snitt, er egenverdiene til matrisen. Derfor er en annen måte å utlede en lukket formel på å bruke en matriseligning og lineær algebra.
Så hvorfor er denne formuleringen nyttig? Fordi eksponentiering kan gjøres i logaritmisk tid. Dette gjøres gjennom kvadrering. Poenget er det
Der det første uttrykket brukes for partall A, det andre for oddetall. Alt som gjenstår er å organisere matrisemultiplikasjonene, og alt er klart. Dette resulterer i følgende kode. Jeg opprettet en rekursiv implementering av pow fordi det er lettere å forstå. Se den iterative versjonen her.
Def pow(x, n, I, mult): """ Returnerer x i potensen av n. Antar at I er identitetsmatrisen som multipliseres med mult og n er et positivt heltall """ hvis n == 0: return I elif n == 1: return x else: y = pow(x, n // 2, I, mult) y = mult(y, y) if n % 2: y = mult(x, y) return y def identity_matrix (n): """Returnerer en n for n identitetsmatrise""" r = liste(område(n)) returner [ for j i r] def matrix_multiply(A, B): BT = list(zip(*B) ) returner [ for rad_a i A] def fib(n): F = pow([, ], n, identitetsmatrise(2), matrisemultipliker) returner F
Flink:
Fast minnestørrelse, logaritmisk tid
Det dårlige:
Koden er mer komplisert
Ond:
Du må jobbe med matriser, selv om de ikke er så ille
Sammenligning av ytelse
Det er verdt å sammenligne bare varianten av dynamisk programmering og matrisen. Hvis vi sammenligner dem med antall tegn i tallet n, viser det seg at matriseløsningen er lineær, og løsningen med dynamisk programmering er eksponentiell. Et praktisk eksempel er å beregne fib(10 ** 6), et tall som vil ha mer enn to hundre tusen sifre.N=10**6
Beregner fib_matrise: fib(n) har bare 208988 sifre, beregningen tok 0,24993 sekunder.
Beregner fib_dynamic: fib(n) har bare 208988 sifre, beregningen tok 11,83377 sekunder.
Teoretiske notater
Selv om det ikke er direkte relatert til koden ovenfor, har denne bemerkningen fortsatt en viss interesse. Tenk på følgende graf:
La oss telle antall baner med lengde n fra A til B. For eksempel, for n = 1 har vi en bane, 1. For n = 2 har vi igjen en bane, 01. For n = 3 har vi to baner, 001 og 101 Det kan ganske enkelt vises at antall baner med lengde n fra A til B er nøyaktig lik F n. Etter å ha skrevet ned tilgrensningsmatrisen for grafen, får vi den samme matrisen som ble beskrevet ovenfor. Det er et velkjent resultat fra grafteori at, gitt en tilstøtende matrise A, er forekomster i A n antall baner med lengde n i grafen (ett av problemene nevnt i filmen Good Will Hunting).
Hvorfor er det slike merker på ribbeina? Det viser seg at når du vurderer en uendelig sekvens av symboler på en tur-retur uendelig sekvens av stier på en graf, får du noe som kalles "finite type subshifts", som er en type symbolsk dynamikksystem. Denne spesielle subshiften av en endelig type er kjent som "det gylne forholdsskiftet", og er spesifisert av et sett med "forbudte ord" (11). Med andre ord vil vi få binære sekvenser som er uendelige i begge retninger og ingen par av dem vil være tilstøtende. Den topologiske entropien til dette dynamiske systemet er lik det gylne forholdet ϕ. Det er interessant hvordan dette tallet vises med jevne mellomrom i ulike områder av matematikken.
Svært ofte, på forskjellige olympiader, kommer du over problemer som dette, som du ved første øyekast tror kan løses med enkel brute force. Men hvis vi teller antall mulige alternativer, vil vi umiddelbart bli overbevist om ineffektiviteten til denne tilnærmingen: for eksempel vil den enkle rekursive funksjonen gitt nedenfor forbruke betydelige ressurser allerede ved det 30. Fibonacci-tallet, mens i Olympiads er løsningstiden ofte begrenset til 1-5 sekunder.
Int fibo(int n) ( if (n == 1 || n == 2) ( return 1; ) else ( return fibo(n - 1) + fibo(n - 2); ) )
La oss tenke på hvorfor dette skjer. For eksempel, for å beregne fibo(30), beregner vi først fibo(29) og fibo(28). Men samtidig «glemmer» programmet vårt at fibo(28) vi allerede beregnet når du søker etter fibo(29).
Hovedfeilen med denne direkte tilnærmingen er at identiske verdier av funksjonsargumenter beregnes mange ganger - og dette er ganske ressurskrevende operasjoner. Den dynamiske programmeringsmetoden vil hjelpe oss med å bli kvitt repeterende beregninger - dette er en teknikk der problemet er delt inn i generelle og repeterbare deloppgaver, som hver løses bare én gang - dette øker effektiviteten til programmet betydelig. Denne metoden er beskrevet i detalj i, det er også eksempler på å løse andre problemer.
Den enkleste måten å forbedre funksjonen vår på er å huske hvilke verdier vi allerede har beregnet. For å gjøre dette, må vi introdusere en ekstra matrise, som vil tjene som en "cache" for våre beregninger: før vi beregner en ny verdi, vil vi sjekke om den ikke har blitt beregnet før. Hvis vi beregnet den, vil vi ta den ferdige verdien fra matrisen, og hvis vi ikke beregnet den, må vi beregne den basert på de forrige og huske den for fremtiden:
Int cache; int fibo(int n) ( if (cache[n] == 0) ( if (n == 1 || n == 2) ( cache[n] = 1; ) else ( cache[n] = fibo(n) - 1) + fibo(n - 2 ) returner cache[n];
Siden vi i denne oppgaven garantert trenger den (N-1)-verdien for å beregne den N-te verdien, vil det ikke være vanskelig å omskrive formelen i iterativ form - vi vil ganske enkelt fylle matrisen vår på rad til vi når ønsket celle:
<= n; i++) { cache[i] = cache + cache; } cout << cache;
Nå kan vi legge merke til at når vi beregner verdien av F(N) , så er verdien av F(N-3) allerede garantert for oss aldri vil ikke trenge. Det vil si at vi bare trenger å lagre to verdier i minnet - F(N-1) og F(N-2) . Dessuten, så snart vi har beregnet F(N), mister lagring av F(N-2) all mening. La oss prøve å skrive ned disse tankene i form av kode:
//To tidligere verdier: int cache1 = 1; int cache2 = 1; //Ny verdi int cache3; for (int i = 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>Etter iterasjon vil cache2 miste sin relevans, dvs. det skal bli cache1 //Med andre ord, cache1 -- f(n-2), cache2 -- f(n-1), cache3 -- f(n). //La N=n+1 (tallet som vi beregner ved neste iterasjon). Da er n-2=N-3, n-1=N-2, n=N-1. //I samsvar med de nye realitetene, omskriver vi verdiene til variablene våre: cache1 = cache2; cache2 = cache3; ) cout<< cache3;
En erfaren programmerer vil forstå at koden ovenfor generelt sett er tull, siden cache3 aldri brukes (den skrives umiddelbart til cache2), og hele iterasjonen kan skrives om med bare ett uttrykk:
Cache = 1; cache = 1; for (int i = 2; i<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;
For de som ikke kan forstå hvordan magien med rester fungerer, eller bare vil se en mer ikke-åpenbar formel, er det en annen løsning:
Int x = 1; int y = 1; for (int i = 2; i< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;
Prøv å overvåke utførelsen av dette programmet: du vil være overbevist om riktigheten av algoritmen.
P.S. Generelt er det en enkelt formel for å beregne et hvilket som helst Fibonacci-tall, som ikke krever noen iterasjon eller rekursjon:
Const dobbel SQRT5 = sqrt(5); const dobbel PHI = (SQRT5 + 1) / 2; int fibo(int n)( return int(pow(PHI, n) / SQRT5 + 0,5); )
Men, som du kan gjette, er fangsten at kostnadene ved å beregne potenser til ikke-heltall er ganske høye, og det samme er feilen deres.
Fibonacci tall er en serie med tall der hvert neste tall er lik summen av de to foregående: 1, 1, 2, 3, 5, 8, 13, .... Noen ganger starter serien fra bunnen av: 0, 1, 1, 2, 3, 5, ... . I dette tilfellet vil vi holde oss til det første alternativet.
Formel:
F 1 = 1
F 2 = 1
Fn = Fn-1 + Fn-2
Regneeksempel:
F 3 = F 2 + F 1 = 1 + 1 = 2
F 4 = F 3 + F 2 = 2 + 1 = 3
F 5 = F 4 + F 3 = 3 + 2 = 5
F 6 = F 5 + F 4 = 5 + 3 = 8
...
Beregner det n-te tallet i Fibonacci-serien ved å bruke en while-løkke
- Tildel variablene fib1 og fib2 verdiene til de to første elementene i serien, det vil si tilordne variablene en.
- Be brukeren om nummeret på elementet hvis verdi han ønsker å få. Tilordne et tall til variabelen n.
- Utfør følgende trinn n - 2 ganger, siden de to første elementene allerede er tatt i betraktning:
- Legg til fib1 og fib2 , og tilordne resultatet til en midlertidig lagringsvariabel, for eksempel fib_sum .
- Sett variabel fib1 til fib2.
- Sett variabel fib2 til fib_sum .
- Vis verdien av fib2.
Merk. Hvis brukeren angir 1 eller 2, blir sløyfen aldri utført, og den opprinnelige verdien til fib2 skrives ut på skjermen.
fib1 = 1 fib2 = 1 n = input() n = int(n) i = 0 mens i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)
Kompakt versjon av koden:
fib1 = fib2 = 1 n = int (inngang ( "Fibonacci-seriens elementnummer: ") ) - 2 mens n > 0 : fib1, fib2 = fib2, fib1 + fib2 n -= 1 utskrift (fib2)
Skrive ut Fibonacci-tall ved hjelp av en for-løkke
I dette tilfellet vises ikke bare verdien til det ønskede elementet i Fibonacci-serien, men også alle tall opp til det, inkludert. For å gjøre dette plasseres utgangen av fib2-verdien i en løkke.
fib1 = fib2 = 1 n = int (input () ) hvis n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()
Eksempel på utførelse:
10 1 1 2 3 5 8 13 21 34 55
Rekursiv beregning av det n-te tallet i Fibonacci-serien
- Hvis n = 1 eller n = 2, returner en til den kallende grenen, siden det første og andre elementet i Fibonacci-serien er lik en.
- I alle andre tilfeller kaller du den samme funksjonen med argumentene n - 1 og n - 2. Legg til resultatet av de to anropene og returner det til den anropende programgrenen.
def fibonacci(n) : if n in (1 , 2 ) : return 1 return fibonacci(n - 1 ) + fibonacci(n - 2 ) print (fibonacci(10 ) )
La oss si n = 4. Da blir det et rekursivt kall til fibonacci(3) og fibonacci(2). Den andre vil returnere en, og den første vil resultere i ytterligere to funksjonskall: fibonacci(2) og fibonacci(1). Begge samtalene vil returnere én, for totalt to. Så kallet til fibonacci(3) returnerer tallet 2, som summeres til tallet 1 fra kallet til fibonacci(2). Resultat 3 returneres til hovedgrenen av programmet. Det fjerde elementet i Fibonacci-serien er lik tre: 1 1 2 3.