Code analysis of solving rabbit problem with Java language

1. Thinking

The rabbit problem is a visual expression of Fisher's sequence. It is a problem put forward by a mathematician named Fibonacci in his works.

2. Description

The problem of other body technology is: if there is an immune child, a small immune child will be born every month, and the small immune child will also begin to produce a month later. At first, there was only one immune son, two immune sons in a month, three immune sons in two months, and five immune sons in three months (small immune sons put into production)

We express it mathematically, which is the following series of numbers:

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

Note: it will take a month for the newborn baby to grow up before it is put into production! And these rabbits are immortal!!!

3. Law

When we are inexplicably exposed to this problem, it is difficult to find the law, but to think about this problem according to the law of sequence in mathematics, equal ratio? Isometric? Or something else? Since this is a question raised by mathematicians, should there be some mathematical laws? What is the law? Carefully analyze the above set of numbers, and you already have the answer. Yes, it is expressed in one sentence. Starting from the third term, the sum of the first two terms is equal to the third term.

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

4. Pseudo code

The so-called pseudo code is not real code. It can not be executed on the machine. It is just a meaningful symbol expressing program logic between natural language and programming language. For the pseudo code of rabbit problem, we use the recursive method of the above formula here, and there can be the following pseudo code:

According to the concept of recursion described in the previous article, for details, please refer to the previous tower of Hanoi problem. Compared with the fact that we are not too unfamiliar with recursion, it will be very concise to deduce such recursive pseudo code according to the above mathematical formula. But, uh, as you might have guessed, I want to say but. Do you find a problem that when our n value is too large, the program will be slow?

If you find it, it means that you have seriously considered this problem. Compared with you, you should also solve the doubts in your heart. If there is no doubt, follow me to solve everyone's doubts. Why is it slower? The reason is that when we calculate the n-th item, we need to calculate the N-1 and n-2 items again, and these two items have been calculated before. When we calculate the next number, we still have to do a lot of useless work on the side of calculation. Virtually, we have done a lot of useless work.

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

Ha ha, is there a moment when you suddenly see the light? Yes! We use space for time, which can greatly improve efficiency! I won't write pseudo code here.

5. Code

OK, the pass is sold out. Go directly to the code:

6. Thinking

Here, we propose a thinking problem. If a rabbit doesn't give birth to one rabbit, how to solve it? Of course, what we say is a fixed number. One rabbit won't give birth to more and one rabbit will give birth to less, otherwise it won't be solved.

There is no code here. You can find the appropriate resources on the Internet and see how to solve them.

summary

The above is all about the code analysis of solving rabbit problem in Java language. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message and point out!