Fibonacci-serien i Java

1. Oversigt

I denne vejledning ser vi på Fibonacci-serien.

Specifikt implementerer vi tre måder at beregne n periode af Fibonacci-serien, hvor den sidste er en konstant-tid-løsning.

2. Fibonacci-serien

Fibonacci-serien er en række tal, hvor hvert udtryk er summen af ​​de to foregående termer. Det er de første to vilkår 0 og 1.

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

I matematiske termer er sekvensen Sn af Fibonacci-tal er defineret af gentagelsesforholdet:

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

Lad os nu se på, hvordan man beregner n løbetid for Fibonacci-serien. De tre metoder, vi vil fokusere på, er rekursive, iterative og bruger Binets formel.

2.1. Rekursiv metode

For vores første løsning, lad os blot udtrykke gentagelsesforholdet direkte i Java:

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

Som vi kan se, kontrollerer vi, om n er lig med 0 eller 1. Hvis det er sandt, returnerer vi den værdi. I ethvert andet tilfælde kalder vi rekursivt funktionen til at beregne (n-1) th periode og (n-2) th sigt og returnere deres sum.

Selvom den rekursive metode er enkel at implementere, ser vi, at denne metode gør mange gentagne beregninger. For eksempel for at beregne 6. sigt, foretager vi opkald for at beregne 5. plads og 4. plads semester. Desuden kaldes op til at beregne 5. plads term kalder for at beregne 4. plads periode igen. På grund af dette faktum gør den rekursive metode meget overflødigt arbejde.

Som det viser sig, gør dette dens tidskompleksitet eksponentiel; O (Φn) for at være præcis.

2.2. Iterativ metode

I den iterative metode kan vi undgå gentagne beregninger foretaget i den rekursive metode. I stedet beregner vi seriens vilkår og gemmer de to foregående vilkår for at beregne det næste.

Lad os se på dens implementering:

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; } returnere n1; }

For det første kontrollerer vi, om udtrykket, der skal beregnes, er 0 sigt eller 1. semester. Hvis det er tilfældet, returnerer vi de oprindelige værdier. Ellers beregner vi 2. plads udtryk ved hjælp n0 og n1. Derefter ændrer vi værdierne for n0 og n1 variabler til at gemme 1. periode og 2. plads term henholdsvis. Vi fortsætter med at gentage, indtil vi har beregnet den krævede periode.

Den iterative metode undgår gentagne arbejder ved at gemme de sidste to Fibonacci-termer i variabler. Den iterative metodes tidskompleksitet og rumkompleksitet er På) og O (1) henholdsvis.

2.3. Binets formel

Vi har kun defineret n Fibonacci-antal i form af de to før det. Nu skal vi se på Binets formel for at beregne n Fibonacci-nummer i konstant tid.

Fibonacci-vilkårene opretholder et kaldet forhold gyldent forhold betegnet med Φ, den græske karakter udtalt 'phi'.

Lad os først se på, hvordan gyldent forhold beregnes:

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

Lad os nu se på Binets formel:

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

Faktisk betyder det det vi skulle være i stand til at få n Fibonacci-nummer med bare noget aritmetik.

Lad os udtrykke dette i Java:

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

Vi beregner først kvadratRootof5 og phi og gem dem i variabler. Senere anvender vi Binets formel for at få den krævede periode.

Da vi har at gøre med irrationelle tal her, får vi kun en tilnærmelse. Derfor bliver vi nødt til at holde på flere decimaler for højere Fibonacci-tal for at tage højde for afrundingsfejl.

Vi ser, at ovenstående metode beregner n Fibonacci-betegnelse i konstant tid, eller O (1).

3. Konklusion

I denne korte artikel kiggede vi på Fibonacci-serien. Vi så på en rekursiv og en iterativ løsning. Derefter anvendte vi Binets formel for at skabe en løsning med konstant tid.

Som altid er den fulde kildekode for arbejdseksemplerne tilgængelig på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found