Mortal Fibonacci Rabbits (Rosalind | English)

            

Hi everyone, how are you? This time, I want to discuss about one problem that exist in rosalind.info's web. The title is "Mortal Fibonacci Rabbits". For the reference, you can first check out the problem what will be discussed (here). 

The image above is an analogy of the rabbit population growth.

In this problem, we will given 2 integers representing "the timeline (in month)" and "the rabbit life span", let's call them n and m. 

Our task is to calculate the total number of rabbit couple (young and adult) exist in the n-th month if every adult couple produce a couple of young rabbits, and the young rabbit turns into an adult, and the m month-old rabbit will die. 

The Code 

This is the code for solving this problem (with java language): 

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. }

As you've seen, here I used the dynamic programming technique to calculate the total number of the rabbit couple. The dynamic programming above consist of a 2D array (2 rows and n column): the first raw is used for calculating the number of young rabbit couple (that don't produce offspring), the second raw is used for calculating the number of adult couple (that produce offspring); while the column (1, ..., n) representing the timeline (in month); the more the column shifts to the right so what happens is: the adult couple produce a young couple of rabbit (line 8), and the young rabbit turns into an adult (line 9), and the m month-old rabbit will die (line 10-12). 

Input and Output

In the code above, I used ni() function for entering the integer-form data. That function is a extend from one of the system inputs which are available in java, called BufferedReader. 

And for the output I used out.println() function. That function is a modification from System.out.println() function which is very familiar in java. You can see the additional code for that modification (input and output) in my complete code at github. 

That's it. If you want to ask something, you can write it in the comment section below. I hope this article is useful and see you in the next article!

Reference :

Source of Image 1 :https://www.facebook.com/ProjectRosalind/

Source of Image 2 :http://rosalind.info/problems/fibd/