Malah, dua nombor Fibonacci yang pertama telah dipratakrifkan. Nombor Fibonacci pertama ialah 0 dan nombor Fibonacci kedua ialah 1. Dengan pengindeksan berasaskan sifar dan mengandaikan nombor Fibonacci berada dalam tatasusunan, maka:
pada indeks 0 , nombor Fibonacci ialah 0 , ( dipratentukan ) ;pada indeks 1 , nombor Fibonacci ialah 1 , ( dipratentukan ) ;
pada indeks dua , nombor Fibonacci ialah 1 = 1 + 0 , ( mengikut takrifan ) ;
pada indeks 3 , nombor Fibonacci ialah dua = 1 + 1 , ( mengikut takrifan ) ;
pada indeks 4 , nombor Fibonacci ialah 3 = dua + 1 , ( mengikut takrifan ) ;
pada indeks 5 , nombor Fibonacci ialah 5 = 3 + dua , ( mengikut takrifan ) ;
pada indeks 6 , nombor Fibonacci ialah 8 = 5 + 3 , ( mengikut takrifan ) ;
pada indeks 7 , nombor Fibonacci ialah 13 = 8 + 5 , ( mengikut takrifan ) ;
pada indeks 8 , nombor Fibonacci ialah dua puluh satu = 13 + 8 , ( mengikut takrifan ) ;
pada indeks 9 , nombor Fibonacci ialah 3. 4 = dua puluh satu + 13 , ( mengikut takrifan ) ;
dan sebagainya.
Dalam pengaturcaraan, pembolehubah n, dan bukan i digunakan untuk indeks berasaskan sifar untuk nombor Fibonacci ini. Dan dengan itu, dua belas nombor Fibonacci pertama ialah:
| 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 |
Baris kedua dalam jadual memberikan indeks berasaskan sifar, setiap satunya akan mempunyai pembolehubah n dalam pengaturcaraan. Baris pertama memberikan nombor Fibonacci yang sepadan. Jadi, nombor Fibonacci bukan sebarang nombor. Takrif teras bermula dengan 0, untuk nombor Fibonacci pertama dan 1 untuk nombor Fibonacci kedua. Selebihnya nombor dihasilkan dari sana.
Nombor Fibonacci boleh dihasilkan dalam masa O(n) dan juga dalam masa O(1). Untuk masa O(n), jika n ialah 12 sebagai contoh, maka dua belas nombor Fibonacci pertama akan dihasilkan. Untuk masa O(1), hanya satu nombor Fibonacci dihasilkan. Sebagai contoh, jika n ialah 6, maka nombor Fibonacci 8 akan dihasilkan.
Artikel ini menerangkan dua cara ini untuk menghasilkan nombor Fibonacci di Jawa.
Formula untuk Nombor Fibonacci
Terdapat formula matematik untuk nombor Fibonacci. Formula ini boleh ditulis dalam tiga baris atau satu baris. Dalam tiga baris, ia ditulis sebagai:
di mana F n ialah nombor Fibonacci pada n berasaskan sifar ke indeks. Inilah cara nombor Fibonacci ditakrifkan.
Menghasilkan Nombor Fibonacci dalam Masa O(n).
Jika nombor Fibonacci akan dihasilkan dalam O(3) kali, nombor, 0, 1, 1 akan dihasilkan; itu adalah tiga nombor Fibonacci pertama. n berasaskan sifar terakhir ke indeks di sini, ialah 2. Jika nombor Fibonacci akan dihasilkan dalam O(7) kali, nombor, 0, 1, 1, 2, 3, 5, 8 akan dihasilkan; itu ialah tujuh nombor Fibonacci yang pertama. n berasaskan sifar terakhir ke indeks di sini, ialah 6. Jika nombor Fibonacci akan dihasilkan dalam masa O(n), nombor, 0, 1, 1, 2, 3, 5, 8 – – -, akan dihasilkan; itu adalah n nombor Fibonacci pertama. n berasaskan sifar terakhir ke indeks di sini ialah n-1.
Kaedah Java dalam kelas untuk menghasilkan n nombor Fibonacci pertama ialah:
kelas Fibonacci {batal fibonacci ( int [ ] P ) {
int n = P. panjang ;
jika ( n > 0 )
P [ 0 ] = 0 ;
jika ( n > 1 )
P [ 1 ] = 1 ;
untuk ( int i = dua ; i < n ; i ++ ) { //n=0 dan n=2 telah dipertimbangkan
int currNo = P [ i - 1 ] + P [ i - dua ] ;
P [ i ] = currNo ;
}
}
}
Kelas, Fibonacci adalah peribadi. The fibonacci() kaedah mengambil tatasusunan P dan mengembalikan batal. Kaedah bermula dengan menentukan panjang tatasusunan. Panjang n ini ialah bilangan nombor Fibonacci yang diperlukan. Nombor Fibonacci pertama dan kedua ditentukan secara eksplisit dan dimasukkan ke dalam kedudukan pertama dan kedua dalam tatasusunan.
Selebihnya nombor Fibonacci bermula dari ketiga (indeks, n = 2) ditentukan dalam gelung untuk dan dimasukkan ke dalam kedudukannya dalam tatasusunan. Jadi, fungsi itu perlu mengembalikan batal. Pernyataan utama dalam gelung untuk menambah dua nombor sebelumnya.
Pembolehubah indeks, i, telah digunakan sebagai ganti n, untuk tujuan kejelasan.
Kelas Utama Java yang sesuai (dengan kaedah utama Java) ialah:
awam kelas Utama {awam statik batal utama ( Tali args [ ] ) {
int m = 12 ;
int [ ] arr = baru int [ m ] ;
Fibonacci obj = baru Fibonacci ( ) ;
obj. fibonacci ( arr ) ;
untuk ( int i = 0 ; i < m ; i ++ )
Sistem . keluar . cetak ( arr [ i ] + ' ' ) ;
Sistem . keluar . println ( ) ;
}
}
Selepas nombor telah dihasilkan oleh kaedah fibonacci(), kaedah utama Java membacanya.
Menghasilkan Satu Nombor Fibonacci dalam Masa Malar
Terdapat formula matematik yang boleh digunakan untuk menghasilkan nombor Fibonacci, apabila diberi indeks berasaskan sifar yang sepadan, n. Formulanya ialah:
di mana n ialah indeks berasaskan sifar dan Fib n ialah nombor Fibonacci yang sepadan. 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, Fib n akan menjadi 0. Jika n ialah 1, Fib n akan menjadi 1. Jika n ialah 2, Fib n akan menjadi 1. Jika n ialah 3, Fib n akan menjadi 2. Jika n ialah 4, Fib n akan menjadi 3 - dan seterusnya. Pembaca boleh mengesahkan formula ini secara matematik, dengan menggantikan nilai yang berbeza untuk n dan menilai.
Apabila dikodkan, formula ini akan menghasilkan hanya satu nombor Fibonacci untuk n. Jika lebih daripada satu nombor Fibonacci diperlukan, kod untuk formula perlu dipanggil sekali untuk setiap indeks sepadan yang berbeza.
Di Jawa, kaedah untuk menghasilkan hanya satu nombor Fibonacci ialah:
import java.lang.* ;kelas Fib {
berganda fibNo ( int n ) {
berganda FibN = ( Matematik . pow ( ( 1 + Matematik . persegi ( 5 ) ) / dua , n ) – Matematik . pow ( ( 1 - Matematik . persegi ( 5 ) ) / dua , n ) ) / Matematik . persegi ( 5 ) ;
kembali FibN ;
}
}
Pakej java.lang.* perlu diimport pada permulaan program. Ini kerana pakej tersebut mempunyai kelas Matematik, yang mempunyai kaedah kuasa (pow) dan punca kuasa dua (sqrt). Kaedah Java tersuai di sini melaksanakan formula matematik secara langsung.
Kerumitan masa untuk fungsi ini ialah O(1), jinak berterusan bagi satu operasi utama. Kelas Utama Java yang sesuai, dengan kaedah utama Java untuk kaedah di atas ialah:
awam kelas Utama {awam statik batal utama ( Tali args [ ] ) {
int N = sebelas ;
Fib obj = baru Fib ( ) ;
berganda betul = obj. fibNo ( N ) ;
Sistem . keluar . println ( betul ) ;
}
}
Indeks n = 11 dihantar dan nombor Fibonacci, 89 dikembalikan. Outputnya ialah:
89.00000000000003Angka perpuluhan yang tidak diperlukan boleh dialih keluar, tetapi itu adalah perbincangan untuk beberapa waktu yang lain.
Kesimpulan
Nombor Fibonacci ialah urutan tertentu bagi nombor bulat. Untuk mendapatkan nombor semasa, tambah dua nombor yang sepadan sebelum ini. Dua nombor Fibonacci pertama, 0 diikuti dengan 1, telah diisytiharkan terlebih dahulu, untuk keseluruhan jujukan. Selebihnya nombor Fibonacci dihasilkan dari sana.
Untuk menghasilkan nombor Fibonacci daripada indeks 2, kepada nombor yang sepadan dengan indeks n-1, gunakan gelung untuk dengan pernyataan utama:
int currNo = P [ i - 1 ] + P [ saya - dua ] ;dengan currNo ialah nombor Fibonacci semasa dan P ialah tatasusunan untuk menyimpan n nombor.
Untuk menghasilkan hanya satu nombor Fibonacci daripada sebarang indeks berasaskan sifar n, gunakan formula matematik:
