streamalism.org

1. Oversikt

I denne opplæringen vil vi se på Fibonacci-serien.

Spesielt implementerer vi tre måter å beregne n sikt av Fibonacci-serien, den siste er en konstanttidsløsning.

2. Fibonacci-serien

Fibonacci-serien er en serie tall der hvert begrep er summen av de to foregående begrepene. Det er de første to begrepene 0 og 1.

For eksempel er de første 11 terminene i serien 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, og 55.

I matematiske termer, sekvensen S_n av Fibonacci-tallene er definert av gjentakelsesforholdet:

S (n) = S (n-1) + S (n-2), med S (0) = 0 og S (1) = 1

La oss nå se på hvordan vi skal beregne n periode av Fibonacci-serien. De tre metodene vi vil fokusere på er rekursive, iterative og bruker Binets formel.

2.1. Rekursiv metode

For vår første løsning, la oss bare uttrykke gjentakelsesforholdet direkte i Java:

offentlig statisk int nthFibonacciTerm (int n) {if (n == 1 || n == 0) {return n; } returner nthFibonacciTerm (n-1) + nthFibonacciTerm (n-2); }

Som vi kan se, sjekker vi om n er lik 0 eller 1. Hvis det stemmer, returnerer vi den verdien. I alle andre tilfeller kaller vi funksjonen rekursivt for å beregne (n-1) th sikt og (n-2) th sikt og returnere summen.

Selv om den rekursive metoden er enkel å implementere, ser vi at denne metoden gjør mange gjentatte beregninger. For eksempel for å beregne Sjette sikt, ringer vi for å beregne 5. og 4. plass begrep. Videre kallet til å beregne 5. term ringer for å beregne 4. plass termin igjen. På grunn av dette faktum gjør den rekursive metoden mye overflødig arbeid.

Som det viser seg, gjør dette dens tidskompleksitet eksponentiell; O (Φn) for å være nøyaktig.

2.2. Iterativ metode

I den iterative metoden kan vi unngå gjentatte beregninger gjort i den rekursive metoden. I stedet beregner vi seriens vilkår og lagrer de to foregående vilkårene for å beregne de neste.

La oss ta en titt på implementeringen:

offentlig statisk int nthFibonacciTerm (int n) {if (n == 0 || n == 1) {return n; } int n0 = 0, n1 = 1; int tempNthTerm; for (int i = 2; i <= n; i ++) {tempNthTerm = n0 + n1; n0 = n1; n1 = tempNthTerm; } returner n1; }

For det første sjekker vi om begrepet som skal beregnes er 0 sikt eller Første begrep. Hvis det er tilfelle, returnerer vi de opprinnelige verdiene. Ellers beregner vi 2. plass begrepet bruker n0 og n1. Deretter endrer vi verdiene til n0 og n1 variabler for å lagre Første sikt og 2. plass periode henholdsvis. Vi fortsetter å itere til vi har beregnet ønsket periode.

Den iterative metoden unngår repeterende arbeid ved å lagre de to siste Fibonacci-begrepene i variabler. Tidskompleksiteten og romkompleksiteten til den iterative metoden er På) og O (1) henholdsvis.

2.3. Binets formel

Vi har bare definert n Fibonacci-nummer når det gjelder de to før det. Nå skal vi se på Binets formel for å beregne n Fibonacci-tall i konstant tid.

Fibonacci-vilkårene opprettholder et forhold som kalles gyldent forhold betegnet med Φ, det greske tegnet uttalt ‘phi’.

La oss først se på hvordan gyldent forhold beregnes:

Φ = (1 + √5) / 2 = 1.6180339887 ...

La oss nå se på Binets formel:

Sn = Φⁿ - (- Φ⁻ⁿ) / √5

Egentlig betyr dette det vi skal kunne få n Fibonacci-nummer med bare noe regning.

La oss uttrykke dette på Java:

offentlig statisk int nthFibonacciTerm (int n) {dobbelt kvadratRootOf5 = Math.sqrt (5); dobbel phi = (1 + kvadratRootOf5) / 2; int nthTerm = (int) ((Math.pow (phi, n) - Math.pow (-phi, -n)) / squareRootOf5); return nthTerm; }

Vi beregner først kvadratRootof5 og phi og lagre dem i variabler. Senere bruker vi Binets formel for å få ønsket periode.

Siden vi her har irrasjonelle tall, får vi bare en tilnærming. Derfor må vi holde på flere desimaler for høyere Fibonacci-tall for å gjøre rede for avrundingsfeil.

Vi ser at metoden ovenfor beregner n Fibonacci-term i konstant tid, eller O (1).

3. Konklusjon

I denne korte artikkelen så vi på Fibonacci-serien. Vi så på en rekursiv og en iterativ løsning. Deretter brukte vi Binets formel for å skape en løsning med konstant tid.

Som alltid er den fullstendige kildekoden til arbeidseksemplene tilgjengelig på GitHub.