Značenje Fibonaccijevih brojeva
Fibonaccijevi brojevi su određeni niz pozitivnih cijelih brojeva, počevši od 0. Cijeli brojevi su pozitivni cijeli brojevi. Dakle, Fibonaccijev broj je određeni niz cijelih brojeva ili prirodnih brojeva, počevši od 0. U ovom nizu, prva dva broja su 0 i 1, tim redoslijedom. Odatle se razvijaju ostali brojevi zbrajanjem prethodna dva broja. Prvih dvanaest Fibonaccijevih brojeva dobiva se na sljedeći način:
0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89
Drugim riječima, prvih dvanaest Fibonaccijevih brojeva su:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Naravno, trinaesti bi broj bio: 144 = 55 + 89. Fibonaccijeve brojeve možemo zamisliti u nizu, ovako:
| 0 | 1 | 1 | dva | 3 | 5 | 8 | 13 | dvadeset i jedan | 3. 4 | 55 | 89 |
Niz ima indekse. U sljedećoj tablici, drugi redak prikazuje odgovarajuće indekse temeljene na nuli za Fibonaccijeve brojeve u nizu:
| 0 | 1 | 1 | dva | 3 | 5 | 8 | 13 | dvadeset i jedan | 3. 4 | 55 | 89 |
| 0 | 1 | dva | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | jedanaest |
S indeksima temeljenim na nuli, ako postoji dvanaest elemenata, tada je zadnji indeks 11.
Fibonaccijevi brojevi mogu se proizvesti u O(n) vremenu ili u O(1) vremenu. U ovim izrazima vremenske složenosti, n znači n glavnih operacija, a 1 znači 1 glavnu operaciju. S O(n), proizvodi se n Fibonaccijevih brojeva, počevši od 0. S O(1), iz odgovarajućeg indeksa proizvodi se jedan Fibonaccijev broj. Zbog toga O(1) uzima samo jednu glavnu operaciju umjesto n glavnih operacija.
Cilj ovog članka je objasniti kako proizvesti Fibonaccijeve brojeve, na bilo koji način, koristeći JavaScript, koji je danas zapravo ECMAScript.
Okruženje kodiranja
Okruženje node.js neće se koristiti kao što je čitatelj mogao predvidjeti. Umjesto toga, preglednik će se koristiti za tumačenje koda i prikaz rezultata. Skripta (kod) treba biti napisana u datoteci uređivača teksta, koju treba spremiti s ekstenzijom “.html.” Skripta treba imati minimalni kod:
DOCTYPE HTML >< html >
< glavu >
< titula > Fibonaccijevi brojevi s JavaScriptom titula >
glavu >
< tijelo >
< vrsta skripte = 'tekst/ecmascript' >
skripta >
tijelo >
html >
Ovo je približni minimalni kod koji web stranica treba. Sav kod za ovaj članak nalazi se između oznaka, .
Za pokretanje napisanog (dodanog) koda samo dvaput kliknite na ikonu naziva datoteke i preglednik računala će je otvoriti.
Definicija Fibonaccijevog broja
Postoji matematička definicija Fibonaccijevog broja. Definira se na sljedeći način:
Gdje je Fn Fibonaccijev broj koji odgovara indeksu temeljenom na nuli, n.
Prva dva broja: 0 i 1, unaprijed su deklarirana, tim redoslijedom. Posljednji redak ove funkcije pokazuje kako ostali brojevi potječu od prva dva broja u njihovom redoslijedu.
Ova definicija je također jedna od formula za Fibonaccijev broj.
Izrada Fibonaccijevih brojeva u O(n) vremenu
Ako je n 1, tada bi samo 0 bila prikazana kao Fibonaccijev broj. Ako je n 2, tada bi 0 i 1 bili prikazani kao Fibonaccijevi brojevi, tim redoslijedom. Ako je n 3, tada bi 0, 1 i 1 bili prikazani kao Fibonaccijevi brojevi tim redoslijedom. Ako je n 4, tada bi 0, 1, 1 i 2 bili prikazani kao Fibonaccijevi brojevi, tim redoslijedom. Ako je n 5, tada bi 0, 1, 1, 2 i 3 bili prikazani kao Fibonaccijevi brojevi, tim redoslijedom. Ako je n 6, tada bi 0, 1, 1, 2, 3 i 5 bili prikazani kao Fibonaccijevi brojevi, tim redoslijedom – i tako dalje.
ECMAscript funkcija za generiranje prvih n Fibonaccijevih cijelih brojeva (brojeva) je:
< vrsta skripte = 'tekst/ecmascript' >funkcija fibonacci ( A ) {
n = A. duljina ;
ako ( n > 0 )
A [ 0 ] = 0 ;
ako ( n > 1 )
A [ 1 ] = 1 ;
za ( ja = dva ; ja < n ; ja ++ ) { //n=0 i n=2 su uzeti u obzir
tekući br = A [ ja - 1 ] + A [ ja - dva ] ;
A [ ja ] = tekući br ;
}
}
Završna oznaka skripte nije prikazana. Funkcija prima niz. Prva dva Fibonaccijeva broja dodijeljena su na njihovoj poziciji. For-petlja ponavlja od indeksa temeljenog na nuli, 2 do malo ispod n. Najvažnija izjava u for-petlji je:
currNo = A[i – 1] + A[i – 2];
Time se zbrajaju prethodna dva broja u nizu kako bi se dobio trenutni broj. U trenutku kada funkcija fibonacci() završi s izvođenjem, svi elementi niza su prvih n Fibonaccijevih brojeva. Prikladan kod za pozivanje funkcije fibonacci() i prikaz Fibonaccijevih brojeva je:
N = 12 ;arr = novi Niz ( N ) ;
fibonacci ( arr ) ;
za ( ja = 0 ; ja < N ; ja ++ )
dokument. pisati ( arr [ ja ] + ' ' ) ;
dokument. pisati ( '
' ) ;
skripta >
Ovaj kôd prikazuje završnu oznaku skripte. Kod se upisuje ispod gornjeg koda. Ispis prikazan na web stranici je:
0 1 1 2 3 5 8 13 21 34 55 89
očekivano.
Izrada jednog Fibonaccijevog broja u O(1) vremenu
O(1) je konstantno vrijeme. Odnosi se na jednu glavnu operaciju. Još jedna matematička formula za dobivanje Fibonaccijevog broja je:
Imajte na umu da na desnoj strani jednadžbe kvadratni korijen od 5 nije podignut na potenciju n; to je izraz u zagradama koji se diže na potenciju n. Postoje dva takva izraza.
Ako je n 0, Fibn bi bio 0. Ako je n 1, Fibn bi bio 1. Ako je n 2, Fibn bi bio 1. Ako je n 3, Fibn bi bio 2. Ako je n 4, Fibn bi bio 3 – i tako dalje. Čitatelj može matematički provjeriti ovu formulu zamjenom različitih vrijednosti za n i procjenom. n je indeks temeljen na nuli u ovoj formuli. Rezultat je odgovarajući Fibonaccijev broj.
ECMAScript (JavaScript) kod za ovu formulu je:
< vrsta skripte = 'tekst/ecmascript' >funkcija fibbr ( n ) {
FibN = ( matematika . pow ( ( 1 + matematika . sqrt ( 5 ) ) / dva , n ) - matematika . pow ( ( 1 - matematika . sqrt ( 5 ) ) / dva , n ) ) / matematika . sqrt ( 5 ) ;
povratak FibN ;
}
Završna oznaka skripte nije prikazana. Imajte na umu kako su korištene unaprijed definirane funkcije snage (pow) i kvadratnog korijena (sqrt). U ECMAScriptu (JavaScript), modul Math ne mora se uvoziti. Funkcija fibNo() izravno implementira formulu. Prikladan poziv i prikaz za funkciju fibNo() na web stranici su:
N = jedanaest ;pravo = fibbr ( N ) ;
dokument. pisati ( pravo ) ;
skripta >
Kod prikazuje završnu oznaku skripte. Izlaz je:
89.0000000000003
Moguće je ukloniti nepotrebne decimalne znamenke iz odgovora. No, to je rasprava za neki drugi put.
Ako je potrebno više od jednog Fibonaccijevog broja, tada kôd mora pozvati formulu jednom za svaki odgovarajući n indeks temeljen na nuli.
Zaključak
Fibonaccijevi brojevi su određeni niz pozitivnih cijelih brojeva, počevši od 0. Cijeli brojevi su pozitivni cijeli brojevi. Dakle, Fibonaccijev broj je određeni niz cijelih brojeva ili prirodnih brojeva, počevši od 0. U ovom nizu, prva dva broja su 0 i 1, tim redoslijedom. Ova prva dva broja su samo definirana kao takva. Ostali brojevi se razvijaju odatle dodavanjem neposredno prethodna dva broja.
Nakon što proizvedemo prva dva Fibonaccijeva broja, kako bismo proizveli ostatak Fibonaccijevih brojeva, da bismo dobili ukupno n brojeva, mora se koristiti for-petlja s naredbom:
currNo = A[i – 1] + A[i – 2];
Time se zbrajaju posljednja dva Fibonaccijeva broja da bi se dobio trenutni Fibonaccijev broj.
Kada je dan indeks temeljen na nuli, da biste dobili odgovarajući Fibonaccijev broj, upotrijebite formulu:
