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 nilai-
nilai 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(2)+FIBONACCI(1)+ 1
= 1 + 1 + 1
=3
Ingat 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. Tentu bukan hal yang sulit untuk
melakukannya, tetapi perlu kecermatan untuk mendapatkan hasil akhir
perhitungan yang benar.
Gambar 2.3 : Flowchart prosedur mencari bilangan FIBONACCI secara rekursi
Flowchart prosedur untuk mencari nilai bilangan FIBONACCI suku ke-n secara
rekursi ditunjukkan Gambar 2.3. 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
Cara lain untuk menghitung nilai suku bilangan FIBONACCI adalah dengan
menggunakan teknik iterasi. Dalam teknik iterasi nilai suku bilangan FIBONACCI
dihitung dengan melaksanakan suatu proses perulangan yang memanfaatkan
nilai bilangan FIBONACCI suku ke-1 sebagai dasar perhitungan untuk mencari
nilai pada suku ke-2. Nilai pada suku ke-2 digunakan sebagai dasar mencari nilai
suku ke-3. Nilai pada suku ke-3 digunakan sebagai dasar mencari nilai suku ke-
4. Demikian seterusnya hingga nilai bilangan FIBONACCI pada suku ke-n yang
dikehendaki ditemukan. Flowchart prosedur untuk mencari nilai bilangan
FIBONACCI suku ke-n dengan teknik iterasi ditunjukkan pada Gambar 2.4.
Logika proses yang terjadi pada teknik iterasi untuk mencari nilai bilangan
FIBONACCI suku ke-n adalah dimulai dengan penetapan harga-harga awal
untuk variabel I, FIBONACCI, dan TERAKHIR. I digunakan sebagai variabel
pencacah (counter) dalam proses perulangan. FIBONACCI digunakan sebagai
variabel bilangan FIBONACCI yang mempunyai harga awal 1 pada suku ke-1.
TERAKHIR digunakan sebagai variabel untuk menyimpan harga hasil
perhitungan bilangan FIBONACCI terakhir pada setiap kali perulangan. Harga
awal untuk variabel TERAKHIR adalah 1.
Langkah selanjutnya adalah pengecekan harga n yang merupakan variabel
untuk menyimpan data suku ke berapa yang akan dicari. Jika n=1, artinya akan
dihitung harga bilangan FIBONACCI suku ke-1, maka nilainya adalah 1 yaitu
harga awal yang telah ditetapkan. Sebaliknya, jika n>1, maka akan dilakukan
proses berulang selama harga pancacah I kurang dari atau sama dengan n.
Variabel BANTU digunakan sebagai variabel bantuan untuk menyimpan nilai
sementara suku terakhir dalam deret FIBONACCI selama proses perulangan.
Pada akhirnya proses akan berhenti dan nilai yang dicari akan diketemukan jika
I=n, dan hasil perhitungannya tersimpan dalam variabel FIBONACCI.
Algoritma untuk mencari nilai bilangan FIBONACCI suku ke-n dengan
menerapkan teknik iterasi adalah dituliskan sebagai berikut ini :
Masukkan harga suku bilangan FIBONACCI yang akan akan dicari (n).
FIBONACCI merupakan variabel untuk menyimpan harga bilangan fibonacci
yang dicari.
BANTU merupakan variabel bantuan untuk menampung hasil perhitungan
sementara.
1. Mulai
2. Tentukan harga-harga awal I, FIBONACCI, dan TERAKHIR
I = 1
FIBONACCI = 1
TERAKHIR = 0
3. Cek harga n
IF n = 1
Jika ya, maka FIBONACCI = 1, lanjutkan ke langkah-6
4. Cetak hasil
FIBONACCI(n)
5. Selesai
Cara lain untuk menghitung nilai suku bilangan FIBONACCI adalah dengan
menggunakan teknik iterasi. Dalam teknik iterasi nilai suku bilangan FIBONACCI
dihitung dengan melaksanakan suatu proses perulangan yang memanfaatkan
nilai bilangan FIBONACCI suku ke-1 sebagai dasar perhitungan untuk mencari
nilai pada suku ke-2. Nilai pada suku ke-2 digunakan sebagai dasar mencari nilai
suku ke-3. Nilai pada suku ke-3 digunakan sebagai dasar mencari nilai suku ke-
4. Demikian seterusnya hingga nilai bilangan FIBONACCI pada suku ke-n yang
dikehendaki ditemukan. Flowchart prosedur untuk mencari nilai bilangan
FIBONACCI suku ke-n dengan teknik iterasi ditunjukkan pada Gambar 2.4.
Logika proses yang terjadi pada teknik iterasi untuk mencari nilai bilangan
FIBONACCI suku ke-n adalah dimulai dengan penetapan harga-harga awal
untuk variabel I, FIBONACCI, dan TERAKHIR. I digunakan sebagai variabel
pencacah (counter) dalam proses perulangan. FIBONACCI digunakan sebagai
variabel bilangan FIBONACCI yang mempunyai harga awal 1 pada suku ke-1.
TERAKHIR digunakan sebagai variabel untuk menyimpan harga hasil
perhitungan bilangan FIBONACCI terakhir pada setiap kali perulangan. Harga
awal untuk variabel TERAKHIR adalah 1.
Langkah selanjutnya adalah pengecekan harga n yang merupakan variabel
untuk menyimpan data suku ke berapa yang akan dicari. Jika n=1, artinya akan
dihitung harga bilangan FIBONACCI suku ke-1, maka nilainya adalah 1 yaitu
harga awal yang telah ditetapkan. Sebaliknya, jika n>1, maka akan dilakukan
proses berulang selama harga pancacah I kurang dari atau sama dengan n.
Variabel BANTU digunakan sebagai variabel bantuan untuk menyimpan nilai
sementara suku terakhir dalam deret FIBONACCI selama proses perulangan.
Pada akhirnya proses akan berhenti dan nilai yang dicari akan diketemukan jika
I=n, dan hasil perhitungannya tersimpan dalam variabel FIBONACCI.
Algoritma untuk mencari nilai bilangan FIBONACCI suku ke-n dengan
menerapkan teknik iterasi adalah dituliskan sebagai berikut ini :
Masukkan harga suku bilangan FIBONACCI yang akan akan dicari (n).
FIBONACCI merupakan variabel untuk menyimpan harga bilangan fibonacci
yang dicari.
BANTU merupakan variabel bantuan untuk menampung hasil perhitungan
sementara.
1. Mulai
2. Tentukan harga-harga awal I, FIBONACCI, dan TERAKHIR
I = 1
FIBONACCI = 1
TERAKHIR = 0
3. Cek harga n
IF n = 1
Jika ya, maka FIBONACCI = 1, lanjutkan ke langkah-6
4. Proses berulang langkah-4 hingga langkah-5 untuk menghitung FIBONACCI
Hitung
BANTU = FIBONACCI
I = I + 1
5. Hitung
FIBONACCI = FIBONACCI + TERAKHIR
TERAKHIR = BANTU
6. Cetak Hasil
FIBONACCI
7. Selesai
Gambar 2.4. : Flowchart prosedur mencari bilangan FIBONACCI secara iterasi
Sebagaimana terjadi dalam perkalian dua bilangan integer, dalam contoh kasus
perhitungan nilai bilangan FIBONACCI ini, secara umum teknik iterasi mampu
melaksanakan proses perhitungan secara lebih efisien
dibandingkan jika
diselesaikan dengan menerapkan teknik rekursi. Dan tentu saja, hasil
perhitungannya akan dapat ditemukan secara lebih cepat.
Cobalah untuk menghitung berapa kali proses perulangan yang harus dilakukan
untuk mencari nilai bilangan FIBONACCI suku ke-1, ke-2, ke-3, ke-4, dan ke-5
apabila diselesaikan secara rekursi. Bandingkan hasilnya jika diselesaikan
secara iterasi, prosedur manakah yang lebih baik untuk diterapkan dalam
perhitungan bilangan FIBONACCI tersebut
Tidak ada komentar:
Posting Komentar