Maksud Nombor Fibonacci
Nombor Fibonacci ialah jujukan tertentu bagi integer positif, bermula dari 0. Nombor bulat ialah integer positif. Jadi, nombor Fibonacci ialah urutan tertentu bagi nombor bulat atau nombor asli, bermula dari 0. Dalam urutan ini, dua nombor pertama ialah 0 dan 1, dalam susunan itu. Selebihnya nombor dibangunkan dari sana dengan menambah dua nombor sebelumnya. Dua belas nombor Fibonacci pertama diperoleh seperti 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 nombor Fibonacci pertama ialah:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Sudah tentu, nombor ketiga belas ialah: 144 = 55 + 89. Nombor Fibonacci mungkin dibayangkan berada dalam tatasusunan, seperti:
| 0 | 1 | 1 | dua | 3 | 5 | 8 | 13 | dua puluh satu | 3. 4 | 55 | 89 |
Tatasusunan mempunyai indeks. Dalam jadual berikut, baris kedua menunjukkan indeks berasaskan sifar yang sepadan untuk nombor Fibonacci dalam tatasusunan:
| 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 berasaskan sifar, jika terdapat dua belas elemen, maka indeks terakhir ialah 11.
Nombor Fibonacci boleh dihasilkan dalam masa O(n) atau dalam masa O(1). Dalam ungkapan kerumitan masa ini, n bermaksud n operasi utama, dan 1 bermaksud 1 operasi utama. Dengan O(n), n nombor Fibonacci dihasilkan, bermula dari 0. Dengan O(1), satu nombor Fibonacci dihasilkan daripada indeks yang sepadan. Itulah sebabnya O(1) hanya mengambil satu operasi utama dan bukannya n operasi utama.
Matlamat artikel ini adalah untuk menerangkan cara menghasilkan nombor Fibonacci, sama ada cara, menggunakan JavaScript, yang sebenarnya ECMAScript hari ini.
Persekitaran Pengekodan
Persekitaran node.js tidak akan digunakan seperti yang pembaca mungkin jangkakan. Sebaliknya, penyemak imbas akan digunakan untuk tafsiran kod dan memaparkan hasilnya. Skrip (kod) hendaklah ditulis dalam fail editor teks, yang harus disimpan dengan sambungan '.html.' Skrip harus mempunyai kod minimum:
HTML DOCTYPE >< html >
< kepala >
< tajuk > Nombor Fibonacci dengan JavaScript tajuk >
kepala >
< badan >
< jenis skrip = 'teks/ecmascript' >
skrip >
badan >
html >
Ini ialah anggaran kod minimum yang diperlukan oleh halaman web. Semua pengekodan untuk artikel ini berada di antara teg, .
Untuk menjalankan kod yang ditulis (ditambah), cuma klik dua kali ikon nama fail, dan pelayar komputer akan membukanya.
Definisi Nombor Fibonacci
Terdapat definisi matematik untuk nombor Fibonacci. Ia ditakrifkan seperti berikut:
Di mana Fn ialah nombor Fibonacci yang sepadan dengan indeks berasaskan sifar, n.
Dua nombor pertama: 0 dan 1, adalah pra-diisytiharkan, dalam susunan itu. Baris terakhir fungsi ini menunjukkan bagaimana nombor selebihnya berasal daripada dua nombor pertama dalam susunannya.
Takrifan ini juga merupakan salah satu formula untuk nombor Fibonacci.
Menghasilkan Nombor Fibonacci dalam Masa O(n).
Jika n ialah 1, maka hanya 0 akan dipaparkan sebagai nombor Fibonacci. Jika n ialah 2, maka 0 dan 1 akan dipaparkan sebagai nombor Fibonacci, dalam susunan tersebut. Jika n ialah 3, maka 0, 1, dan 1 akan dipaparkan sebagai nombor Fibonacci dalam susunan tersebut. Jika n ialah 4, maka 0, 1, 1, dan 2 akan dipaparkan sebagai nombor Fibonacci, dalam susunan tersebut. Jika n ialah 5, maka 0, 1, 1, 2, dan 3 akan dipaparkan sebagai nombor Fibonacci, dalam susunan tersebut. Jika n ialah 6, maka 0, 1, 1, 2, 3, dan 5 akan dipaparkan sebagai nombor Fibonacci, dalam susunan tersebut – dan seterusnya.
Fungsi ECMAscript untuk menjana n Fibonacci integer (nombor) pertama ialah:
< jenis skrip = 'teks/ecmascript' >fungsi fibonacci ( A ) {
n = A. panjang ;
jika ( n > 0 )
A [ 0 ] = 0 ;
jika ( n > 1 )
A [ 1 ] = 1 ;
untuk ( i = dua ; i < n ; i ++ ) { //n=0 dan n=2 telah dipertimbangkan
currNo = A [ i - 1 ] + A [ i - dua ] ;
A [ i ] = currNo ;
}
}
Teg skrip penutup belum ditunjukkan. Fungsi menerima tatasusunan. Dua nombor Fibonacci pertama ditetapkan pada kedudukan mereka. Gelung untuk berulang daripada indeks berasaskan sifar, 2 kepada hanya di bawah n. Pernyataan yang paling penting dalam gelung untuk ialah:
currNo = A[i – 1] + A[i – 2];
Ini menambah dua nombor sebelum ini dalam tatasusunan untuk mempunyai nombor semasa. Apabila fungsi fibonacci() selesai dilaksanakan, semua elemen tatasusunan ialah n nombor Fibonacci pertama. Kod yang sesuai untuk memanggil fungsi fibonacci() dan memaparkan nombor Fibonacci ialah:
N = 12 ;arr = baru Susunan ( N ) ;
fibonacci ( arr ) ;
untuk ( i = 0 ; i < N ; i ++ )
dokumen. menulis ( arr [ i ] + '' ) ;
dokumen. menulis ( '
' ) ;
skrip >
Kod ini menunjukkan teg skrip penutup. Kod ditaip di bawah kod di atas. Output yang dipaparkan pada halaman web ialah:
0 1 1 2 3 5 8 13 21 34 55 89
seperti yang diharapkan.
Menghasilkan Satu Nombor Fibonacci dalam Masa O(1).
O(1) ialah masa tetap. Ia merujuk kepada satu operasi utama. Satu lagi formula matematik untuk menghasilkan nombor Fibonacci ialah:
Ambil perhatian bahawa di sebelah kanan persamaan, bukan punca kuasa dua bagi 5 yang dinaikkan kepada kuasa n; ia adalah ungkapan dalam kurungan yang dinaikkan kepada kuasa n. Terdapat dua ungkapan sedemikian.
Jika n ialah 0, Fibn akan menjadi 0. Jika n ialah 1, Fibn akan menjadi 1. Jika n ialah 2, Fibn akan menjadi 1. Jika n ialah 3, Fibn akan menjadi 2. Jika n ialah 4, Fibn akan menjadi 3 – dan sebagainya. Pembaca boleh mengesahkan formula ini secara matematik dengan menggantikan nilai yang berbeza untuk n dan menilai. n ialah indeks berasaskan sifar dalam formula ini. Hasilnya ialah nombor Fibonacci yang sepadan.
Kod ECMAScript (JavaScript) untuk formula ini ialah:
< jenis skrip = 'teks/ecmascript' >fungsi fibNo ( n ) {
FibN = ( Matematik . pow ( ( 1 + Matematik . persegi ( 5 ) ) / dua , n ) - Matematik . pow ( ( 1 - Matematik . persegi ( 5 ) ) / dua , n ) ) / Matematik . persegi ( 5 ) ;
kembali FibN ;
}
Teg skrip penutup belum ditunjukkan. Perhatikan bagaimana kuasa (pow) dan punca kuasa dua (sqrt) fungsi pratakrif telah digunakan. Dalam ECMAScript (JavaScript), modul Matematik tidak perlu diimport. Fungsi fibNo() melaksanakan formula secara langsung. Panggilan dan paparan yang sesuai untuk fungsi fibNo() pada halaman web ialah:
N = sebelas ;betul = fibNo ( N ) ;
dokumen. menulis ( betul ) ;
skrip >
Kod menunjukkan teg skrip penutup. Outputnya ialah:
89.00000000000003
Adalah mungkin untuk mengalih keluar digit perpuluhan yang tidak diperlukan daripada jawapan. Walau bagaimanapun, itu adalah perbincangan untuk masa yang lain.
Jika lebih daripada satu nombor Fibonacci diperlukan, maka kod tersebut perlu memanggil formula sekali untuk setiap indeks n yang sepadan berasaskan sifar.
Kesimpulan
Nombor Fibonacci ialah jujukan tertentu bagi integer positif, bermula dari 0. Nombor bulat ialah integer positif. Jadi, nombor Fibonacci ialah urutan tertentu bagi nombor bulat atau nombor asli, bermula dari 0. Dalam urutan ini, dua nombor pertama ialah 0 dan 1, dalam susunan itu. Dua nombor pertama ini hanya ditakrifkan sedemikian. Selebihnya nombor dibangunkan dari sana dengan menambah dua nombor sebelumnya yang terdekat.
Selepas menghasilkan dua nombor Fibonacci pertama, untuk menghasilkan nombor Fibonacci yang selebihnya, untuk berakhir dengan jumlah n nombor, gelung untuk perlu digunakan dengan pernyataan:
currNo = A[i – 1] + A[i – 2];
Ini menambah dua nombor Fibonacci terakhir serta-merta untuk mempunyai nombor Fibonacci semasa.
Apabila diberi indeks berasaskan sifar, untuk mempunyai nombor Fibonacci yang sepadan, gunakan formula:
