بسم الله الرحمن الرحيم
Kita semua pasti sudah tau apa itu barisan Fibonacci. Yaitu barisan yang sukunya adalah jumlah 2 suku sebelumnya. Tapi kenapa bisa gitu dan gimana problem ini muncul ? Coba simak narasi di bawah.
Misal kita beli seekor anak kelinci. Anak kelinci itu akan dewasa setelah setahun. Lalu pada tahun berikutnya kelinci dewasa tadi akan melahirkan seekor anak kelinci. Tiap tahun si kelinci dewasa akan melahirkan anak terus-menerus. Dan si anak kelinci ini akan mengikuti pola yang sama dengan induknya. Dewasa setelah setahun lahir, lalu melahirkan seekor anak tiap tahun -dengan asumsi kelinci tidak akan mati dan beranak tanpa pasangan selamanya hihi
Jika kita lihat polanya, anak kelinci pada tiap tahun :
Pada tahun pertama, 1 ekor (anak kelinci yang baru dibeli)
Pada tahun kedua, 1 ekor (anak kelinci sudah dewasa)
Pada tahun ketiga, 2 ekor (kelinci dewasa melahirkan seekor anak)
Pada tahun keempat, 3 ekor (kelinci dewasa melahirkan seekor anak dan si anak kelinci yang tadi sudah dewasa)
dan seterusnya yang dapat kita simpulkan menjadi
1, 1, 2, 3, 5, 8, 13, 21 ...
Ternyata pola yang didapat yaitu jumlah kelinci pada tahun ini adalah kelinci pada tahun lalu ditambah kelinci dua tahun lalu. Kok bisa?
Coba diingat lagi, kelinci bisa melahirkan ketika dia sudah berumur minimal 2 tahun.
Maka jumlah kelinci dewasa saat ini sejumlah kelinci dewasa tahun lalu plus kelinci yang dilahirkan tahun lalu yang baru saja dewasa.
\[D_{n} = D_{n-1} + A_{n-1} = F_{n-1}\]
Lalu jumlah kelinci muda sekarang sejumlah kelinci dewasa dua tahun lalu dan jumlah kelinci yang baru dewasa tahun lalu/kelinci muda dua tahun lalu.
\[A_{n} = D_{n-2} + A_{n-2} = F_{n-2}\]
Maka jumlah kelinci sekarang = jumlah kelinci muda sekarang + jumlah kelinci dewasa sekarang.
\[F_{n}=D_{n} + A_{n}= F_{n-1} + F_{n-2}\]
Pembuktian sudah beres. Sekarang kita coba terapkan pola ini ke salah satu soal OSK 2013 (bidang informatika) yang telah dimodif sedemikian rupa. Check this out!!
Sebuah katak berada pada salah satu sisi sungai ingin menyeberangi sungai dengan melewati 5 buah batu yang berada di sepanjang aliran sungai (lihat gambar di bawah). Katak ingin menghitung berapa kemungkinan cara yang dia gunakan untuk menyeberangi sungai. Karena katak jago melompat, katak mampu melompat dari batu satu ke batu sebelahnya, atau melompati satu batu tersebut dan mendarat di sampingnya lagi. Coba bantu katak menghitung berapa kemungkinan langkah yang diambil untuk bisa ke ujung satunya!
Jawab :
Coba kita lihat jumlah cara yang bisa diambil untuk mendarat di batu ke-n
Pada batu ke-1 : hanya 1 cara
Pada batu ke-2 : karena bisa dari batu pertama atau dari ujung, maka jumlah cara ada 1+1=2 cara
Pada batu ke-3 : idem di atas, 2+1=3 ( coba cari tahu kenapa 2+1 :) )
Pada batu ke-4 : ada 3+2=5 cara
Pada batu ke-5 : ada 3+5=8 cara
Dan ke ujung kanan ada 8+5=13 cara.
Simpel kan :). Meski begitu banyak masalah dalam bidang ilmu komputer yang melibatkan perhitungan bilangan Fibonacci. Misal, dalam perhitungan kompleksitas algoritma Euclid dalam mencari GCD (Greatest Common Divisor), pembentukan struktur data Fibonacci, dan beberapa masalah komputasi lainnya.
Perlu diketahui meskipun barisan Fibonacci termasuk barisan yang tidak tentu (karena tergantung suku-suku sebelumnya), tapi rasio \(\frac{F_{n+1}}{F_{n}}\) akan mendekati suatu nilai yang disebut Phi / Golden Ratio. Dengan menggunakan Golden Ratio ini kita dapat menghitung barisan Fibonacci secara langsung tanpa harus tahu suku-suku sebelumnya. Tapi kita tidak akan menggunakan ini karena dalam pemrograman perhitungan nilai real (bilangan non bulat) rawan menghasilkan nilai yang salah dalam pembulatan. Dan juga pemrosesan bilangan real cenderung lebih lambat dibanding bilangan bulat.
Lalu bagaimana cara menghitung Fibonacci dengan cepat? Tunggu postingan berikutnya :
About Fibonacci : Fungsi Rekursif dan Dynamic Programming Sederhana - part 2
Coba diingat lagi, kelinci bisa melahirkan ketika dia sudah berumur minimal 2 tahun.
Maka jumlah kelinci dewasa saat ini sejumlah kelinci dewasa tahun lalu plus kelinci yang dilahirkan tahun lalu yang baru saja dewasa.
\[D_{n} = D_{n-1} + A_{n-1} = F_{n-1}\]
Lalu jumlah kelinci muda sekarang sejumlah kelinci dewasa dua tahun lalu dan jumlah kelinci yang baru dewasa tahun lalu/kelinci muda dua tahun lalu.
\[A_{n} = D_{n-2} + A_{n-2} = F_{n-2}\]
Maka jumlah kelinci sekarang = jumlah kelinci muda sekarang + jumlah kelinci dewasa sekarang.
\[F_{n}=D_{n} + A_{n}= F_{n-1} + F_{n-2}\]
Pembuktian sudah beres. Sekarang kita coba terapkan pola ini ke salah satu soal OSK 2013 (bidang informatika) yang telah dimodif sedemikian rupa. Check this out!!
Sebuah katak berada pada salah satu sisi sungai ingin menyeberangi sungai dengan melewati 5 buah batu yang berada di sepanjang aliran sungai (lihat gambar di bawah). Katak ingin menghitung berapa kemungkinan cara yang dia gunakan untuk menyeberangi sungai. Karena katak jago melompat, katak mampu melompat dari batu satu ke batu sebelahnya, atau melompati satu batu tersebut dan mendarat di sampingnya lagi. Coba bantu katak menghitung berapa kemungkinan langkah yang diambil untuk bisa ke ujung satunya!
Jawab :
Coba kita lihat jumlah cara yang bisa diambil untuk mendarat di batu ke-n
Pada batu ke-1 : hanya 1 cara
Pada batu ke-2 : karena bisa dari batu pertama atau dari ujung, maka jumlah cara ada 1+1=2 cara
Pada batu ke-3 : idem di atas, 2+1=3 ( coba cari tahu kenapa 2+1 :) )
Pada batu ke-4 : ada 3+2=5 cara
Pada batu ke-5 : ada 3+5=8 cara
Dan ke ujung kanan ada 8+5=13 cara.
Simpel kan :). Meski begitu banyak masalah dalam bidang ilmu komputer yang melibatkan perhitungan bilangan Fibonacci. Misal, dalam perhitungan kompleksitas algoritma Euclid dalam mencari GCD (Greatest Common Divisor), pembentukan struktur data Fibonacci, dan beberapa masalah komputasi lainnya.
Perlu diketahui meskipun barisan Fibonacci termasuk barisan yang tidak tentu (karena tergantung suku-suku sebelumnya), tapi rasio \(\frac{F_{n+1}}{F_{n}}\) akan mendekati suatu nilai yang disebut Phi / Golden Ratio. Dengan menggunakan Golden Ratio ini kita dapat menghitung barisan Fibonacci secara langsung tanpa harus tahu suku-suku sebelumnya. Tapi kita tidak akan menggunakan ini karena dalam pemrograman perhitungan nilai real (bilangan non bulat) rawan menghasilkan nilai yang salah dalam pembulatan. Dan juga pemrosesan bilangan real cenderung lebih lambat dibanding bilangan bulat.
Lalu bagaimana cara menghitung Fibonacci dengan cepat? Tunggu postingan berikutnya :
About Fibonacci : Fungsi Rekursif dan Dynamic Programming Sederhana - part 2