java language solves rabbit problem code analysis

1, thinking,

The rabbit problem, a visualization of the Fay sequence, is a problem posed by a mathematician named Fibonacci in his work.

2, description,

The problem with this technique is that if a baby is born every month, the baby will start to give birth after a month. At the beginning, there was only one free seed, after one month, there were two free seeds, after two months, there were three free seeds, after three months, five free seeds (small free seeds into production)......

We express it mathematically, as follows:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Note: the new baby will not be put into production until it has grown for 1 month! And these rabbits are immortal!!

3, regular

It's hard to find a pattern when we get to this problem somehow, but think about it in terms of the sequence of numbers in mathematics. Geometric? Arithmetic? Or something else? Since this is a problem posed by a mathematician, there must be a definite mathematical law in it, right? What is the pattern? Take a closer look at the first sequence of numbers and you have the answer. That's right, it's expressed in 1 sentence, starting with the third term, the sum of the first two terms is equal to the third term.

Assuming that the value of n is fn, the regularity of the sequence is expressed by the mathematical formula as follows:

4. Pseudocode

Pseudocode is not real code that can't be executed on a machine, but is a meaningful symbol between a natural language and a programming language that expresses program logic. For the pseudo-code of rabbit problem, we use the recursive method of the above formula here, and the pseudo-code can be as follows:

Procedure FIB(N) [ 
  IF (N < 0)  
    PRINT (" Input error ");  
 
  IF (N = 0 OR N = 1)  
    RETURN (N);  
  ELSE  
    RETURN ( FIB(N-1) + FIB(N-2) );  
] 

According to the recursion concept described in the previous article, you can refer to the previous "Tower of Hannock Problem" for details. Compared with the recursion is not too strange to everyone, then according to the above mathematical formula we get, deducing such recursive pseudocode will be very simple and clear. But, well, as you might have guessed, I'm going to say but. Have you noticed that when our n value is too high, the program will slow down?

If you find out, you've thought about the problem, and you should be able to solve it. If there are any questions that haven't been answered, follow me to answer them. Why is it slower? And the reason for that is, when we compute the next n term, we have to compute the es33EN-1 and n-2 terms, both of which have been computed before, and when we compute the next number, we still have to compute the 1 side, so we're doing a lot of wasted work.

So, do we have a good way to solve this problem? The answer is yes. According to the above analysis, when we are solving for the n term, the previous n-1 and ES39en-2 terms have already been solved, so why don't we save it???

Ha ha, was there a moment of enlightenment, yes! Here we are using space for time, can greatly improve efficiency oh! I'm not going to write any pseudo-code here.

5, code,

Okay, we're out of business, so just code it:

public class Fibonacci { 
  public static void main(String[] args) { 
    int[] fib = new int[20];  
 
    fib[0] = 0;  
    fib[1] = 1;  
 
    for(int i = 2; i < fib.length; i++) { 
      fib[i] = fib[i-1] + fib[i-2];  
    } 
 
    for(int i = 0; i < fib.length; i++){  
      System.out.print(fib[i] + " ");  
    } 
    System.out.println(); 
  } 
} 

6, think

So here, we're going to ask ourselves a question, if the rabbit, instead of having one rabbit, has more than one rabbit, how do we solve it? And, of course, when we say more than one is a fixed number, it's not going to be 1 rabbit that has more than one, and 1 rabbit that has less than one, otherwise we wouldn't be able to solve it.

I'm not going to do the code here, but you can look up the appropriate resources on the Internet and see how to solve it.

conclusion

The above is the Java language to solve the rabbit problem code analysis, I hope to help you. Interested friends can continue to refer to other relevant topics in this site, if there is any deficiency, welcome to leave a message!