Faktanya, dua angka Fibonacci pertama sudah ditentukan sebelumnya. Angka Fibonacci pertama adalah 0 dan angka Fibonacci kedua adalah 1. Dengan pengindeksan berbasis nol dan dengan asumsi angka Fibonacci berada dalam array, maka:
di indeks 0 , bilangan Fibonacci adalah 0 , ( sudah ditentukan sebelumnya ) ;di indeks 1 , bilangan Fibonacci adalah 1 , ( sudah ditentukan sebelumnya ) ;
di indeks dua , bilangan Fibonacci adalah 1 = 1 + 0 , ( Menurut definisi ) ;
di indeks 3 , bilangan Fibonacci adalah dua = 1 + 1 , ( Menurut definisi ) ;
di indeks 4 , bilangan Fibonacci adalah 3 = dua + 1 , ( Menurut definisi ) ;
di indeks 5 , bilangan Fibonacci adalah 5 = 3 + dua , ( Menurut definisi ) ;
di indeks 6 , bilangan Fibonacci adalah 8 = 5 + 3 , ( Menurut definisi ) ;
di indeks 7 , bilangan Fibonacci adalah 13 = 8 + 5 , ( Menurut definisi ) ;
di indeks 8 , bilangan Fibonacci adalah dua puluh satu = 13 + 8 , ( Menurut definisi ) ;
di indeks 9 , bilangan Fibonacci adalah 3. 4 = dua puluh satu + 13 , ( Menurut definisi ) ;
dan seterusnya.
Dalam pemrograman, variabel n, dan bukan i digunakan untuk indeks berbasis nol untuk angka-angka Fibonacci ini. Dan dengan itu, dua belas angka Fibonacci pertama adalah:
| 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 tabel memberikan indeks berbasis nol, yang masing-masing akan memiliki variabel n dalam pemrograman. Baris pertama memberikan angka Fibonacci yang sesuai. Jadi, angka Fibonacci bukan sembarang angka. Definisi inti dimulai dengan 0, untuk angka Fibonacci pertama dan 1 untuk angka Fibonacci kedua. Sisa angka dihasilkan dari sana.
Bilangan Fibonacci dapat dihasilkan dalam waktu O(n) dan juga dalam waktu O(1). Untuk waktu O(n), jika n adalah 12 misalnya, maka dua belas angka Fibonacci pertama akan dihasilkan. Untuk waktu O(1), hanya satu angka Fibonacci yang dihasilkan. Misalnya, jika n adalah 6, maka angka Fibonacci 8 akan dihasilkan.
Artikel ini menjelaskan dua cara menghasilkan angka Fibonacci di Jawa.
Rumus untuk Bilangan Fibonacci
Ada rumus matematika untuk bilangan Fibonacci. Rumus ini dapat ditulis dalam tiga baris atau satu baris. Dalam tiga baris, ditulis sebagai:
dimana F n adalah bilangan Fibonacci pada n berbasis nol th indeks. Ini adalah bagaimana angka Fibonacci didefinisikan.
Memproduksi Bilangan Fibonacci dalam Waktu O(n)
Jika angka-angka Fibonacci akan dihasilkan dalam O(3) kali, angka-angka, 0, 1, 1 akan dihasilkan; itu adalah tiga angka Fibonacci pertama. n . berbasis nol terakhir th indeks di sini, adalah 2. Jika angka-angka Fibonacci akan dihasilkan dalam O(7) kali, angka-angka, 0, 1, 1, 2, 3, 5, 8 akan dihasilkan; itu adalah tujuh angka Fibonacci pertama. n . berbasis nol terakhir th indeks di sini, adalah 6. Jika angka Fibonacci akan diproduksi dalam O(n) kali, angka, 0, 1, 1, 2, 3, 5, 8 – – -, akan dihasilkan; itu adalah n angka Fibonacci pertama. n . berbasis nol terakhir th indeks di sini adalah n-1.
Metode Java dalam sebuah kelas untuk menghasilkan n bilangan Fibonacci pertama adalah:
kelas Fibonacci {ruang kosong fibonacci ( ke dalam [ ] P ) {
ke dalam n = P. panjangnya ;
jika ( n > 0 )
P [ 0 ] = 0 ;
jika ( n > 1 )
P [ 1 ] = 1 ;
untuk ( ke dalam saya = dua ; saya < n ; saya ++ ) { //n=0 dan n=2 telah dipertimbangkan
ke dalam tidak ada = P [ saya - 1 ] + P [ saya - dua ] ;
P [ saya ] = tidak ada ;
}
}
}
Kelas, Fibonacci bersifat pribadi. Itu fibonacci() metode mengambil array P dan mengembalikan void. Metode dimulai dengan menentukan panjang array. Panjang n ini adalah jumlah angka Fibonacci yang dibutuhkan. Angka Fibonacci pertama dan kedua ditentukan secara eksplisit dan dimasukkan ke dalam posisi pertama dan kedua dalam array.
Sisa angka Fibonacci mulai dari ketiga (indeks, n = 2) ditentukan dalam for-loop dan dimasukkan ke dalam posisi mereka dalam array. Jadi, fungsi harus mengembalikan void. Pernyataan utama dalam for-loop menambahkan dua angka sebelumnya.
Variabel indeks, i, telah digunakan sebagai pengganti n, untuk tujuan kejelasan.
Kelas Utama Java yang cocok (dengan metode utama Java) adalah:
publik kelas Utama {publik statis ruang kosong utama ( Rangkaian argumen [ ] ) {
ke dalam m = 12 ;
ke dalam [ ] arr = baru ke dalam [ m ] ;
Fibonacci obj = baru Fibonacci ( ) ;
obj. fibonacci ( arr ) ;
untuk ( ke dalam saya = 0 ; saya < m ; saya ++ )
Sistem . keluar . mencetak ( arr [ saya ] + ' ' ) ;
Sistem . keluar . println ( ) ;
}
}
Setelah angka dihasilkan oleh metode fibonacci(), metode utama Java membacanya.
Menghasilkan Satu Angka Fibonacci dalam Waktu Konstan
Ada rumus matematika yang dapat digunakan untuk menghasilkan bilangan Fibonacci, jika diberikan indeks berbasis nol yang sesuai, n. Rumusnya adalah:
di mana n adalah indeks berbasis nol dan Fib n adalah angka Fibonacci yang sesuai. 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, Fib n akan menjadi 0. Jika n adalah 1, Fib n akan menjadi 1. Jika n adalah 2, Fib n akan menjadi 1. Jika n adalah 3, Fib n akan menjadi 2. Jika n adalah 4, Fib n akan menjadi 3 - dan seterusnya. Pembaca dapat memverifikasi rumus ini secara matematis, dengan mengganti nilai yang berbeda untuk n dan mengevaluasi.
Ketika dikodekan, rumus ini hanya akan menghasilkan satu angka Fibonacci untuk n. Jika lebih dari satu angka Fibonacci diperlukan, kode untuk rumus harus dipanggil sekali untuk masing-masing indeks terkait yang berbeda.
Di Java, metode untuk menghasilkan hanya satu angka Fibonacci adalah:
impor java.lang.* ;kelas Bikinan {
dobel fibTidak ( ke dalam n ) {
dobel fibN = ( matematika . pow ( ( 1 + matematika . persegi ( 5 ) ) / dua , n ) - matematika . pow ( ( 1 - matematika . persegi ( 5 ) ) / dua , n ) ) / matematika . persegi ( 5 ) ;
kembali fibN ;
}
}
Paket java.lang.* harus diimpor di awal program. Ini karena paket tersebut memiliki kelas Math, yang memiliki metode pangkat (pow) dan akar kuadrat (sqrt). Metode Java kustom di sini mengimplementasikan rumus matematika secara langsung.
Kompleksitas waktu untuk fungsi ini adalah O(1), penjinakan konstan dari satu operasi utama. Kelas Utama Java yang cocok, dengan metode utama Java untuk metode di atas adalah:
publik kelas Utama {publik statis ruang kosong utama ( Rangkaian argumen [ ] ) {
ke dalam N = sebelas ;
fib obj = baru Bikinan ( ) ;
dobel Baik = obj. fibTidak ( N ) ;
Sistem . keluar . println ( Baik ) ;
}
}
Indeks n = 11 dikirim dan angka Fibonacci, 89 dikembalikan. Outputnya adalah:
890000000000003Digit desimal yang tidak perlu dapat dihapus, tetapi itu adalah diskusi untuk waktu lain.
Kesimpulan
Bilangan Fibonacci adalah barisan bilangan bulat tertentu. Untuk mendapatkan nomor saat ini, tambahkan dua nomor yang sesuai sebelumnya. Dua angka Fibonacci pertama, 0 diikuti oleh 1, telah dideklarasikan sebelumnya, untuk seluruh urutan. Sisa angka Fibonacci dihasilkan dari sana.
Untuk menghasilkan angka Fibonacci dari indeks 2, ke yang sesuai dengan indeks n-1, gunakan for-loop dengan pernyataan utama:
ke dalam tidak ada = P [ saya - 1 ] + P [ saya - dua ] ;di mana currNo adalah angka Fibonacci saat ini dan P adalah array untuk menyimpan n angka.
Untuk menghasilkan hanya satu angka Fibonacci dari indeks berbasis nol n, gunakan rumus matematika:
