streamalism.org

1. Overzicht

In deze tutorial kijken we naar de Fibonacci-serie.

Concreet zullen we drie manieren implementeren om de n term van de Fibonacci-reeks, waarvan de laatste een constante-tijdoplossing is.

2. Fibonacci-reeks

De Fibonacci-reeks is een reeks getallen waarin elke term de som is van de twee voorgaande termen. De eerste twee termen zijn 0 en 1.

De eerste 11 termen van de serie zijn bijvoorbeeld 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, en 55.

In wiskundige termen, de volgorde S_n van de Fibonacci-getallen wordt gedefinieerd door de herhalingsrelatie:

S (n) = S (n-1) + S (n-2), met S (0) = 0 en S (1) = 1

Laten we nu eens kijken hoe we de n term van de Fibonacci-reeks. De drie methoden waarop we ons zullen concentreren, zijn recursief, iteratief en gebruiken de formule van Binet.

2.1. Recursieve methode

Laten we voor onze eerste oplossing de herhalingsrelatie rechtstreeks in Java uitdrukken:

openbare statische int nthFibonacciTerm (int n) {if (n == 1 || n == 0) {return n; } retourneer nthFibonacciTerm (n-1) + nthFibonacciTerm (n-2); }

Zoals we kunnen zien, controleren we of n is gelijk aan 0 of 1. Als het waar is, geven we die waarde terug. In elk ander geval roepen we recursief de functie aan om de (n-1) th termijn en (n-2) th termijn en geven hun som terug.

Hoewel de recursieve methode eenvoudig te implementeren is, zien we dat deze methode veel herhaalde berekeningen uitvoert. Om bijvoorbeeld de 6e term, we bellen om de te berekenen 5e en de 4e termijn. Bovendien is de oproep om de 5e term maakt een oproep om de 4e term opnieuw. Vanwege dit feit doet de recursieve methode veel overbodig werk.

Het blijkt dat dit maakt zijn tijdcomplexiteit exponentieel; O (Φn) Om precies te zijn.

2.2. Iteratieve methode

In de iteratieve methode kunnen we de herhaalde berekeningen die in de recursieve methode worden gedaan, vermijden. In plaats daarvan berekenen we de termen van de reeks en slaan we de vorige twee termen op om de volgende te berekenen.

Laten we de implementatie eens bekijken:

openbare statische int nthFibonacciTerm (int n) {if (n == 0 || n == 1) {return n; } int n0 = 0, n1 = 1; int tempNthTerm; voor (int i = 2; i <= n; i ++) {tempNthTerm = n0 + n1; n0 = n1; n1 = tempNthTerm; } retourneer n1; }

Allereerst kijken we of de te berekenen term de 0e term of 1e termijn. Als dat het geval is, retourneren we de beginwaarden. Anders berekenen we de 2e term gebruiken n0 en n1. Vervolgens wijzigen we de waarden van n0 en n1 variabelen om de 1e termijn en 2e term respectievelijk. We blijven itereren totdat we de vereiste looptijd hebben berekend.

De iteratieve methode vermijdt repetitief werk door de laatste twee Fibonacci-termen in variabelen op te slaan. De tijdcomplexiteit en ruimtecomplexiteit van de iteratieve methode is Aan) en O (1) respectievelijk.

2.3. Binet's formule

We hebben alleen de n Fibonacci-nummer in termen van de twee ervoor. Nu zullen we de formule van Binet bekijken om de n Fibonacci-getal in constante tijd.

De Fibonacci-termen handhaven een zogenaamde ratio gouden ratio aangegeven met Φ, het Griekse karakter dat wordt uitgesproken als ‘phi '.

Laten we eerst eens kijken hoe de gouden ratio berekend:

Φ = (1 + √5) / 2 = 1,6180339887 ...

Laten we nu eens kijken Binet's formule:

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

Eigenlijk betekent dit dat we zouden het n Fibonacci-getal met slechts wat rekenkunde.

Laten we dit in Java uitdrukken:

openbare statische int nthFibonacciTerm (int n) {double squareRootOf5 = Math.sqrt (5); dubbele phi = (1 + squareRootOf5) / 2; int nthTerm = (int) ((Math.pow (phi, n) - Math.pow (-phi, -n)) / squareRootOf5); terug nthTerm; }

We berekenen eerst de squareRootof5 en phi en sla ze op in variabelen. Later passen we de formule van Binet toe om de vereiste term te krijgen.

Omdat we hier te maken hebben met irrationele getallen, krijgen we alleen een benadering. Daarom zullen we meer decimalen moeten vasthouden voor hogere Fibonacci-getallen om rekening te houden met afrondingsfouten.

We zien dat de bovenstaande methode de n Fibonacci-term in constante tijd, of O (1).

3. Conclusie

In dit korte artikel hebben we gekeken naar de Fibonacci-serie. We hebben gekeken naar een recursieve en een iteratieve oplossing. Vervolgens hebben we de formule van Binet toegepast om een ​​oplossing met constante tijd te creëren.

Zoals altijd is de volledige broncode van de werkende voorbeelden beschikbaar op GitHub.