2.2.2. Mencari Bilangan FIBONACCI
Bilangan FIBONACCI adalah suatu deret bilangan bulat positif (integer) tak berhingga yang secara berurutan adalah didefinisikan sebagai berikut ini :
1 1 2 3 5 8 13 21 34 58 89 . . . dst
Jika diamati deret bilangan FIBONACCI di atas, maka dapat dipahami bahwa nilai bilangan FIBONACCI suku ke-n dalam deret tersebut dapat dihitung dengan menjumlahkan dua bilangan terdekat pada urutan sebelumnya.
Sebagai contoh, suku bilangan ke-6 dapat dihitung dengan menjumlahkan suku bilangan ke-5 dan ke-4. Nilai bilangan FIBONACCI suku-5 dapat dihitung dengan cara menjumlahkan suku bilangan ke-4 dan ke3. Nilai bilangan FIBONACCI suku-4 dapat dihitung dengan cara menjumlahkan suku bilangan ke-3 dan ke-2. Nilai bilangan FIBONACCI suku-3 dapat dihitung dengan cara menjumlahkan suku bilangan ke-2 dan ke-1.
Secara umum nilai bilangan FIBONACCI suku-n dapat dihitung dengan menjumlahkan nilai-nilai bilangan FIBONACCI suku-(n-1) dan ke-(n-2). Dengan demikian, nilai-nilai bilangan FIBONACCI untuk n=1 dan n=2 merupakan nilainilai awal yang perlu ditetapkan sebelumnya. Nilai-nilai awal tersebut digunakan sebagai dasar untuk menghitung nilai-nilai bilangan FIBONACCI untuk suku-suku berikutnya, yaitu bernilai 1 (lihat deret FIBONACCI di atas).
Pencarian nilai suku bilangan FIBONACCI secara rekursi dapat dinotasikan sebagai berikut ini :
FIBONACCI(n)= n ; jika n=1 atau n=2
FIBONACCI(n)= FIBONACCI(n-1)+FIBONACCI(n-2) ; jika n>2
Contoh :
Mencari bilangan FIBONACCI suku ke-4 dapat dihitung secara rekursi dengan cara sebagai berikut :
nilai bilangan FIBONACCI suku ke-2 dan ke-1 adalah 1, sehingga dari hasil perhitungan diperoleh harga FIBONACCI suku ke-4 adalah sama dengan 3. Untuk harga-harga bilangan FIBONACCI pada suku-suku selanjutnya dapat dihitung dengan cara yang sama seperti di atas.
Flowchart prosedur untuk mencari nilai bilangan FIBONACCI suku ke-n secara rekursi ditunjukkan diatas. Sedangkan, solusi dalam bentuk algoritmanya dapat dituliskan sebagai berikut ini :
Masukan suku bilangan FIBONACCI yang akan dicari (=n).
FIBONACCI merupakan variabel untuk menyimpan harga suku bilangan Fibonacci yang dicari.
1. Mulai
2. Baca n
3. Proses berulang langkah-2
Cek harga n
IF (n=1) OR (n=2)
Jika ya, FIBONACCI(n) = 1, lanjutkan ke langkah-4
Jika tidak, FIBONACCI(N) = FIBONACCI(n – 1) + FIBONACCI(n – 2)
4. Cetak hasil
FIBONACCI(n)
5. Selesai