Seri Fibonacci di Jawa

1. Ikhtisar

Dalam tutorial ini, kita akan melihat deret Fibonacci.

Secara khusus, kami akan menerapkan tiga cara untuk menghitung suku ke - n dari deret Fibonacci, yang terakhir adalah solusi waktu-konstan.

2. Deret Fibonacci

Deret Fibonacci adalah deret angka di mana setiap suku adalah jumlah dari dua suku sebelumnya . Dua suku pertamanya adalah 0 dan 1 .

Misalnya, 11 suku pertama dari deretan tersebut adalah 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, dan 55 .

Dalam istilah matematika, urutan S n dari bilangan Fibonacci ditentukan oleh relasi pengulangan:

S(n) = S(n-1) + S(n-2), with S(0) = 0 and S(1) = 1

Sekarang, mari kita lihat cara menghitung suku ke - n dari deret Fibonacci. Tiga metode yang akan kita fokuskan adalah rekursif, berulang, dan menggunakan rumus Binet.

2.1. Metode Rekursif

Untuk solusi pertama kita, mari kita ekspresikan relasi pengulangan secara langsung di Java:

public static int nthFibonacciTerm(int n) { if (n == 1 || n == 0) { return n; } return nthFibonacciTerm(n-1) + nthFibonacciTerm(n-2); }

Seperti yang bisa kita lihat, kita memeriksa apakah n sama dengan 0 atau 1. Jika benar, maka kita mengembalikan nilai itu. Dalam kasus lain, kita secara rekursif memanggil fungsi tersebut untuk menghitung suku (n-1) dan suku (n-2) dan mengembalikan jumlahnya.

Meskipun metode rekursif mudah diterapkan, kami melihat bahwa metode ini melakukan banyak penghitungan berulang. Misalnya, untuk menghitung suku ke - 6 , kami melakukan panggilan untuk menghitung suku ke - 5 dan ke - 4 . Selain itu, panggilan untuk menghitung suku ke - 5 membuat panggilan untuk menghitung suku ke - 4 lagi. Karena fakta ini, metode rekursif melakukan banyak pekerjaan yang berlebihan.

Ternyata, ini membuat kompleksitas waktunya menjadi eksponensial; O (Φn) tepatnya.

2.2. Metode Iteratif

Dalam metode iteratif, kita dapat menghindari penghitungan berulang yang dilakukan dalam metode rekursif. Sebagai gantinya, kami menghitung suku-suku deret dan menyimpan dua suku sebelumnya untuk menghitung suku berikutnya.

Mari kita lihat implementasinya:

public static int nthFibonacciTerm(int n) { if(n == 0 || n == 1) { return n; } int n0 = 0, n1 = 1; int tempNthTerm; for (int i = 2; i <= n; i++) { tempNthTerm = n0 + n1; n0 = n1; n1 = tempNthTerm; } return n1; }

Pertama, kita periksa apakah istilah yang akan dihitung adalah istilah ke - 0 atau istilah ke - 1 . Jika demikian, kami mengembalikan nilai awal. Jika tidak, kami menghitung suku ke - 2 menggunakan n0 dan n1 . Kemudian, kami memodifikasi nilai variabel n0 dan n1 untuk menyimpan suku pertama dan suku kedua masing-masing. Kami terus melakukan iterasi sampai kami menghitung persyaratan yang diperlukan.

Metode iteratif menghindari pekerjaan berulang dengan menyimpan dua suku Fibonacci terakhir dalam variabel. Kompleksitas waktu dan kompleksitas ruang dari metode iteratif masing-masing adalah O (n) dan O (1) .

2.3. Formula Binet

Kami hanya mendefinisikan angka Fibonacci ke - n dalam dua istilah sebelumnya. Sekarang, kita akan melihat rumus Binet untuk menghitung angka Fibonacci ke - n dalam waktu konstan.

Istilah Fibonacci mempertahankan rasio yang disebut rasio emas yang dilambangkan dengan Φ , karakter Yunani diucapkan 'phi' .

Pertama, mari kita lihat bagaimana rasio emas dihitung:

Φ = ( 1 + √5 )/2 = 1.6180339887...

Sekarang, mari kita lihat rumus Binet :

Sn = Φⁿ–(– Φ⁻ⁿ)/√5

Sebenarnya, ini berarti kita bisa mendapatkan angka Fibonacci ke - n hanya dengan beberapa aritmatika.

Mari kita ekspresikan ini di Jawa:

public static int nthFibonacciTerm(int n) { double squareRootOf5 = Math.sqrt(5); double phi = (1 + squareRootOf5)/2; int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5); return nthTerm; }

Kami pertama kali menghitung squareRootof5 dan phi dan menyimpannya dalam variabel. Nanti, kami menerapkan rumus Binet untuk mendapatkan istilah yang dibutuhkan.

Karena kita berurusan dengan bilangan irasional di sini, kita hanya akan mendapatkan perkiraan. Akibatnya, kita harus memegang lebih banyak tempat desimal untuk angka Fibonacci yang lebih tinggi untuk memperhitungkan kesalahan pembulatan.

Kita melihat bahwa metode di atas menghitung suku Fibonacci ke - n dalam waktu konstan, atau O (1).

3. Kesimpulan

Dalam artikel singkat ini, kita melihat deret Fibonacci. Kami melihat solusi rekursif dan berulang. Kemudian, kami menerapkan rumus Binet untuk membuat solusi waktu-konstan.

Seperti biasa, kode sumber lengkap dari contoh yang berfungsi tersedia di GitHub.