Fibonacci tall på Java -språk
Faktisk er de to første Fibonacci -tallene forhåndsdefinerte. Det første fibonacci -tallet er 0 og det andre fibonacci -tallet er 1. Med nullbasert indeksering og forutsatt at fibonacci-tallene er i en matrise, så:
Ved indeks 0 er fibonacci -nummeret 0, (forhåndsdefinert);Ved indeks 1 er fibonacci -nummeret 1, (forhåndsdefinert);
Ved indeks 2 er fibonacci -tallet 1 = 1 + 0, (per definisjon);
Ved indeks 3 er fibonacci -tallet 2 = 1 + 1, (per definisjon);
Ved indeks 4 er fibonacci -tallet 3 = 2 + 1, (per definisjon);
Ved indeks 5 er fibonacci -tallet 5 = 3 + 2, (per definisjon);
Ved indeks 6 er fibonacci -tallet 8 = 5 + 3, (per definisjon);
Ved indeks 7 er fibonacci -tallet 13 = 8 + 5, (per definisjon);
Ved indeks 8 er fibonacci -tallet 21 = 13 + 8, (per definisjon);
Ved indeks 9 er fibonacci -tallet 34 = 21 + 13, (per definisjon);
og så videre.
I programmering brukes variabelen n, og ikke jeg brukes til nullbaserte indekser for disse fibonacci-tallene. Og med det er de første tolv fibonacci -tallene:
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 1. 3 | 21 | 34 | 55 | 89 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
Den andre raden i tabellen gir nullbaserte indekser, som hver vil ha variabelen N i programmering. Den første raden gir de tilsvarende fibonacci -tallene. Så fibonacci -tall er ikke bare noen tall. Kjernedefinisjonen begynner med 0, for det første Fibonacci -nummeret og 1 for det andre Fibonacci -nummeret. Resten av tallene er produsert derfra.
Fibonacci -tall kan produseres i O (n) tid og også i O (1) tid. For O (n) tid, hvis n er 12 for eksempel, vil de første tolv fibonacci -tallene bli produsert. For o (1) tid produseres bare ett fibonacci -nummer. For eksempel, hvis n er 6, ville Fibonacci nummer 8 bli produsert.
Denne artikkelen forklarer disse to måtene å produsere fibonacci -tall i Java.
Formel for et fibonacci -nummer
Det er en matematisk formel for et fibonacci -nummer. Denne formelen kan skrives i tre linjer eller en linje. I tre linjer er det skrevet som:
hvor fn er fibonacci-nummeret på nullbasert nth indeks. Slik er fibonacci -nummeret definert.
Produserer fibonacci -tall i O (n) tid
Hvis fibonacci -tall skal produseres i o (3) ganger, vil tallene, 0, 1, 1 bli produsert; Det er de tre første Fibonacci -tallene. Den siste nullbaserte nth indeks her, er 2. Hvis fibonacci -tall skal produseres i O (7) ganger, vil tallene, 0, 1, 1, 2, 3, 5, 8 bli produsert; Det er de syv første fibonacci -tallene. Den siste nullbaserte nth Indeks her, er 6. Hvis fibonacci -tall skal produseres i o (n) ganger, vil tallene, 0, 1, 1, 2, 3, 5, 8 - - -, bli produsert; Det er de første n fibonacci -tallene. Den siste nullbaserte nth Indeks her er n-1.
Java -metoden i en klasse for å produsere de første N Fibonacci -tallene er:
klasse fibonaccivoid fibonacci (int [] p)
int n = p.lengde;
if (n> 0)
P [0] = 0;
if (n> 1)
P [1] = 1;
for (int i = 2; i
P [i] = currno;
Klassen, Fibonacci er privat. De Fibonacci () Metoden tar matrisen P og returnerer tomrom. Metoden begynner med å bestemme lengden på matrisen. Denne lengden på n er antallet fibonacci -tall som kreves. Første og andre Fibonacci -tall bestemmes eksplisitt og settes i første og andre plassering i matrisen.
Resten av fibonacci-tallene som begynner fra den tredje (indeksen, n = 2) bestemmes i en for-loop og setter i sine posisjoner i matrisen. Så funksjonen må returnere ugyldig. Hoveduttalelsen i For-loop legger til de to foregående tallene.
Indeksvariabelen, i, har blitt brukt i stedet for n, med det formålet med klarhet.
En passende Java hovedklasse (med Java hovedmetode) er:
offentlig klasse Mainpublic static void main (String args [])
int m = 12;
int [] arr = new int [m];
Fibonacci obj = new Fibonacci ();
obj.Fibonacci (arr);
for (int i = 0; i
System.ute.println ();
Etter at tallene er produsert av Fibonacci () -metoden, leser Java -hovedmetoden dem ut.
Produsere ett fibonacci -nummer i konstant tid
Det er en matematisk formel som kan brukes til å produsere et fibonacci-nummer, når det får den tilsvarende nullbaserte indeksen, n. Formelen er:
hvor n er den nullbaserte indeksen og FIBn er det tilsvarende fibonacci -nummeret. Legg merke til at det på høyre side av ligningen ikke er kvadratroten til 5 som heves til kraften n; det er uttrykket i parenteser som heves til kraften n. Det er to av slike uttrykk.
Hvis n er 0, fibn ville være 0. Hvis n er 1, fibn ville være 1. Hvis n er 2, fibn ville være 1. Hvis n er 3, fibn ville være 2. Hvis n er 4, fibn ville være 3 - og så videre. Leseren kan bekrefte denne formelen matematisk, ved å erstatte forskjellige verdier med n og evaluere.
Når den ble kodet, ville denne formelen produsere bare ett fibonacci -nummer for n. Hvis det kreves mer enn ett fibonacci -tall, må koden for formelen kalles en gang for hver av de forskjellige tilsvarende indeksene.
I Java er metoden for å produsere bare ett fibonacci -nummer:
Importer Java.lang.*;klasse fib
dobbel fiBno (int n)
dobbel fiBn = (matematikk.POW ((1+matematikk.SQRT (5))/2, n) -MATH.POW ((1-MATH.sqrt (5)) / 2, n)) / matematikk.SQRT (5);
Retur Fibn;
Javaen.lang.* Pakken måtte importeres i begynnelsen av programmet. Dette er fordi pakken har matematikklassen, som har Power (POW) og Square Root (SQRT) metoder. Den tilpassede Java -metoden implementerer her matematikkformelen direkte.
Tidskompleksiteten for denne funksjonen er O (1), konstant tam av en hovedoperasjon. En passende Java hovedklasse, med Java hovedmetode for metoden ovenfor er:
offentlig klasse Mainpublic static void main (String args [])
int n = 11;
Fib obj = new fib ();
dobbel ret = obj.Fibno (n);
System.ute.println (ret);
Indeksen n = 11 sendes og Fibonacci -nummeret, 89 returneres. Utgangen er:
89.00000000000003Unødvendige desimalsifre kan fjernes, men det er en diskusjon for en annen gang.
Konklusjon
Fibonacci -tall er en bestemt sekvens av hele tall. For å få gjeldende antall, legg til de umiddelbare foregående tilsvarende tall. De to første fibonacci-tallene, 0 etterfulgt av 1, er forhåndsklærte, for hele sekvensen. Resten av fibonacci -tallene produseres derfra.
For å produsere fibonacci-tall fra indeks 2, til det som tilsvarer indeks n-1, bruk en for-loop med hoveduttalelsen:
int currno = p [i - 1] + p [i - 2];der currno er det nåværende fibonacci -nummeret og p er matrisen for å lagre n -tallene.
For å produsere bare ett fibonacci-nummer fra hvilken som helst nullbasert indeks n, bruk den matematiske formelen: