Arti Angka Fibonacci
Bilangan Fibonacci adalah barisan bilangan bulat positif tertentu, dimulai dari 0. Bilangan bulat adalah bilangan bulat positif. Jadi, bilangan Fibonacci adalah barisan bilangan bulat atau bilangan asli tertentu, dimulai dari 0. Dalam barisan ini, dua bilangan pertama adalah 0 dan 1, dalam urutan itu. Sisa angka dikembangkan dari sana dengan menambahkan dua angka sebelumnya. Dua belas angka Fibonacci pertama diperoleh sebagai berikut:
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
Dengan kata lain, dua belas angka Fibonacci pertama adalah:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Tentu saja, angka ketiga belas adalah: 144 = 55 + 89. Angka-angka Fibonacci dapat dibayangkan berada dalam sebuah array, seperti:
| 0 | 1 | 1 | dua | 3 | 5 | 8 | 13 | dua puluh satu | 3. 4 | 55 | 89 |
Sebuah array memiliki indeks. Dalam tabel berikut, baris kedua menunjukkan indeks berbasis nol yang sesuai untuk angka Fibonacci dalam array:
| 0 | 1 | 1 | dua | 3 | 5 | 8 | 13 | dua puluh satu | 3. 4 | 55 | 89 |
| 0 | 1 | dua | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | sebelas |
Dengan indeks berbasis nol, jika ada dua belas elemen, maka indeks terakhir adalah 11.
Bilangan Fibonacci dapat dihasilkan dalam waktu O(n) atau dalam waktu O(1). Dalam ekspresi kompleksitas waktu ini, n berarti n operasi utama, dan 1 berarti 1 operasi utama. Dengan O(n), n angka Fibonacci dihasilkan, mulai dari 0. Dengan O(1), satu angka Fibonacci dihasilkan dari indeks yang sesuai. Itulah sebabnya O(1) hanya membutuhkan satu operasi utama, bukan n operasi utama.
Tujuan artikel ini adalah untuk menjelaskan cara menghasilkan angka Fibonacci, dengan cara apa pun, menggunakan JavaScript, yang sebenarnya adalah ECMAScript hari ini.
Lingkungan Pengkodean
Lingkungan node.js tidak akan digunakan seperti yang diharapkan pembaca. Sebagai gantinya, browser akan digunakan untuk interpretasi kode dan menampilkan hasilnya. Script (kode) harus ditulis dalam file editor teks, yang harus disimpan dengan ekstensi “.html.” Skrip harus memiliki kode minimum:
DOCTYPE HTML >< html >
< kepala >
< judul > Angka Fibonacci dengan JavaScript judul >
kepala >
< tubuh >
< jenis skrip = 'teks/ecmascript' >
naskah >
tubuh >
html >
Ini adalah perkiraan kode minimum yang dibutuhkan halaman web. Semua pengkodean untuk artikel ini berada di antara tag, .
Untuk menjalankan kode tertulis (ditambahkan), cukup klik dua kali ikon nama file, dan browser komputer akan membukanya.
Definisi Bilangan Fibonacci
Ada definisi matematika untuk bilangan Fibonacci. Ini didefinisikan sebagai berikut:
Dimana Fn adalah angka Fibonacci yang sesuai dengan indeks berbasis nol, n.
Dua angka pertama: 0 dan 1, sudah dideklarasikan sebelumnya, dalam urutan itu. Baris terakhir dari fungsi ini menunjukkan bagaimana sisa angka berasal dari dua angka pertama dalam urutannya.
Definisi ini juga merupakan salah satu rumus untuk bilangan Fibonacci.
Memproduksi Bilangan Fibonacci dalam Waktu O(n)
Jika n adalah 1, maka hanya 0 yang akan ditampilkan sebagai angka Fibonacci. Jika n adalah 2, maka 0 dan 1 akan ditampilkan sebagai angka Fibonacci, dalam urutan itu. Jika n adalah 3, maka 0, 1, dan 1 akan ditampilkan sebagai angka Fibonacci dalam urutan itu. Jika n adalah 4, maka 0, 1, 1, dan 2 akan ditampilkan sebagai angka Fibonacci, dalam urutan itu. Jika n adalah 5, maka 0, 1, 1, 2, dan 3 akan ditampilkan sebagai angka Fibonacci, dalam urutan itu. Jika n adalah 6, maka 0, 1, 1, 2, 3, dan 5 akan ditampilkan sebagai angka Fibonacci, dalam urutan itu – dan seterusnya.
Fungsi ECMAscript untuk menghasilkan n bilangan bulat Fibonacci (angka) pertama adalah:
< jenis skrip = 'teks/ecmascript' >fungsi fibonacci ( SEBUAH ) {
n = SEBUAH. panjangnya ;
jika ( n > 0 )
SEBUAH [ 0 ] = 0 ;
jika ( n > 1 )
SEBUAH [ 1 ] = 1 ;
untuk ( saya = dua ; saya < n ; saya ++ ) { //n=0 dan n=2 telah dipertimbangkan
tidak ada = SEBUAH [ saya - 1 ] + SEBUAH [ saya - dua ] ;
SEBUAH [ saya ] = tidak ada ;
}
}
Tag skrip penutup belum ditampilkan. Fungsi menerima array. Dua angka Fibonacci pertama ditetapkan pada posisinya. For-loop beralih dari indeks berbasis nol, 2 hingga tepat di bawah n. Pernyataan terpenting dalam for-loop adalah:
currNo = A[i – 1] + A[i – 2];
Ini menambahkan dua nomor sebelumnya langsung dalam array untuk memiliki nomor saat ini. Pada saat fungsi fibonacci() selesai dijalankan, semua elemen array adalah n angka Fibonacci pertama. Kode yang cocok untuk memanggil fungsi fibonacci() dan menampilkan angka Fibonacci adalah:
N = 12 ;arr = baru Himpunan ( N ) ;
fibonacci ( arr ) ;
untuk ( saya = 0 ; saya < N ; saya ++ )
dokumen. menulis ( arr [ saya ] + ' ' ) ;
dokumen. menulis ( '
' ) ;
naskah >
Kode ini menunjukkan tag skrip penutup. Kode diketik di bawah kode di atas. Output yang ditampilkan pada halaman web adalah:
0 1 1 2 3 5 8 13 21 34 55 89
seperti yang diharapkan.
Menghasilkan Satu Angka Fibonacci dalam Waktu O(1)
O(1) adalah waktu konstan. Ini mengacu pada satu operasi utama. Rumus matematika lain untuk menghasilkan bilangan Fibonacci adalah:
Perhatikan bahwa di ruas kanan persamaan, bukan akar kuadrat dari 5 yang dipangkatkan n; itu adalah ekspresi dalam tanda kurung yang dipangkatkan n. Ada dua ekspresi seperti itu.
Jika n adalah 0, Fibn akan menjadi 0. Jika n adalah 1, Fibn akan menjadi 1. Jika n adalah 2, Fibn akan menjadi 1. Jika n adalah 3, Fibn akan menjadi 2. Jika n adalah 4, Fibn akan menjadi 3 – dan seterusnya. Pembaca dapat memverifikasi rumus ini secara matematis dengan mengganti nilai yang berbeda untuk n dan mengevaluasi. n adalah indeks berbasis nol dalam rumus ini. Hasilnya adalah angka Fibonacci yang sesuai.
Kode ECMAScript (JavaScript) untuk rumus ini adalah:
< jenis skrip = 'teks/ecmascript' >fungsi fibTidak ( n ) {
fibN = ( matematika . pow ( ( 1 + matematika . persegi ( 5 ) ) / dua , n ) - matematika . pow ( ( 1 - matematika . persegi ( 5 ) ) / dua , n ) ) / matematika . persegi ( 5 ) ;
kembali fibN ;
}
Tag skrip penutup belum ditampilkan. Perhatikan bagaimana fungsi yang telah ditentukan daya (pow) dan akar kuadrat (sqrt) telah digunakan. Di ECMAScript (JavaScript), modul Math tidak harus diimpor. Fungsi fibNo() mengimplementasikan rumus secara langsung. Panggilan dan tampilan yang cocok untuk fungsi fibNo() pada halaman web adalah:
N = sebelas ;Baik = fibTidak ( N ) ;
dokumen. menulis ( Baik ) ;
naskah >
Kode menunjukkan tag skrip penutup. Outputnya adalah:
890000000000003
Dimungkinkan untuk menghapus angka desimal yang tidak perlu dari jawaban. Namun, itu adalah diskusi untuk beberapa waktu lain.
Jika lebih dari satu angka Fibonacci diperlukan, maka kode tersebut harus memanggil rumus sekali untuk setiap indeks n berbasis nol yang sesuai.
Kesimpulan
Bilangan Fibonacci adalah barisan bilangan bulat positif tertentu, dimulai dari 0. Bilangan bulat adalah bilangan bulat positif. Jadi, bilangan Fibonacci adalah barisan bilangan bulat atau bilangan asli tertentu, dimulai dari 0. Dalam barisan ini, dua bilangan pertama adalah 0 dan 1, dalam urutan itu. Dua angka pertama ini hanya didefinisikan seperti itu. Sisa angka dikembangkan dari sana dengan menambahkan dua angka sebelumnya.
Setelah menghasilkan dua angka Fibonacci pertama, untuk menghasilkan sisa angka Fibonacci, untuk menghasilkan total n angka, for-loop harus digunakan dengan pernyataan:
currNo = A[i – 1] + A[i – 2];
Ini menambahkan dua angka Fibonacci terakhir langsung untuk memiliki angka Fibonacci saat ini.
Saat diberi indeks berbasis nol, untuk mendapatkan angka Fibonacci yang sesuai, gunakan rumus:
