Mortal Fibonacci Rabbits (Rosalind)

           

Halo teman-teman, apa kabar? Kali ini saya ingin membahas sedikit tentang salah satu problem yang ada di web rosalind.info. Judulnya ialah "Mortal Fibonacci Rabbits". Sebagai acuan, teman-teman bisa cek dahulu problem yang akan kita bahas (disini). 

Gambar diatas ialah analogi dari perkembangan populasi kelinci dewasa dan muda.

Di problem ini kita akan disajikan 2 buah bilangan bulat (integer) yang mewakili "bulan ke-berapa" dan "umur dari kelinci", sebut saja n dan m. Tugas kita ialah mengkalkulasi jumlah total pasangan kelinci yang ada (dewasa dan muda) pada bulan ke-n jika setiap bulannya setiap pasang kelinci dewasa menghasilkan satu pasang kelinci muda, kelinci muda menjadi dewasa, dan kelinci yang sudah berumur m akan mati. 

Berikut kode untuk pengerjaannya (dalam bahasa java) :

01. static void solve() {

02.  int n = ni();

03.  int m = ni();

04.  long[][] dp = new long[2][n];

05.  dp[0][0] = 1;

06.  dp[1][0] = 0;

07.  for (int i = 1; i < n; i++) {

08.         dp[0][i] = dp[1][i - 1];

09. dp[1][i] = dp[0][i - 1] + dp[1][i - 1];

10. if (i >= m) {

11. dp[1][i] -= dp[0][i - m];

12. }

13. }

14. out.println(dp[0][n - 1] + dp[1][n - 1]);

15. }

Seperti yang teman-teman lihat, disini saya menggunakan teknik dynamic programming untuk mengkalkulasi jumlah total pasang kelinci. Dynamic programming diatas terdiri dari 2D array (2 baris dan n kolom): baris pertama untuk menghitung jumlah pasangan kelinci muda (tidak menghasilkan keturunan), baris kedua untuk pasangan kelinci dewasa (menghasilkan keturunan); sedangkan kolomnya (1, .., n) mewakili jangka waktu (dalam bulan). Semakin kolom bergeser ke kanan maka yang terjadi ialah: kelinci dewasa menghasilkan sepasang keturunan (baris 8), kelinci kecil berubah menjadi kelinci dewasa (baris 9), dan kelinci yang sudah berumur akan mati (baris 10-12). 

Disini saya memakai fungsi ni() untuk meng-input data integer. Fungsi tersebut adalah modifikasi dari salah satu sistem input yang ada di java (BufferedReader). Sedangkan untuk output-nya saya memakai fungsi out.println() . Fungsi tersebut juga adalah modifikasi dari fungsi System.out.println()  yang merupakan fungsi default di java. Untuk lebih jelasnya teman-teman bisa melihat kode tambahan untuk memodifikasi fungsi tersebut (input maupun output) di versi lengkap kode saya di github. 

Sekian dari saya. Jika teman-teman ingin menanyakan sesuatu, teman-teman bisa menulisnya di kolom komentar. Semoga bermanfaat dan sampai jumpa di artikel berikutnya!

Referensi :

Sumber gambar 1 :https://www.facebook.com/ProjectRosalind/

Sumber gambar 2 :http://rosalind.info/problems/fibd/