Shulou(Shulou.com)06/02 Report--

This article mainly explains the "Magic Index example analysis", the content of the article is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in depth, together to study and learn "Magic Index example analysis" bar!

Interview questions:

Given an array A, there is a position called Magic Index, meaning: if I is Magic Index, then A [I] = I. Assuming that the elements in An are incrementally ordered and do not repeat, give a way to find this Magic Index. Further, what if repeating elements are allowed in A?

Egg hold up body analysis:

Description of the original topic

Two eggs with the same soft and hard degree but unknown may be broken on the first floor, or they may fall off a hundred stories. There is a 100-story building that asks you to use these two eggs to determine which floor is where the eggs can safely fall through the least number of times. You can break two eggs.

Method analysis

The safest way to see this problem is to test it layer by layer, but only one egg is needed. We now have two eggs, which can be used in a faster way.

What's further? The possible test method is binary search, for example, * eggs are dropped on the 50th floor, if broken, the second egg is tested layer by layer from 1 to 49; if it is not broken, * eggs are thrown on the 75th floor, if broken, the second egg is tested layer by layer from 51 to 74. However, this method can easily be tragic, for example, when the 49th floor can be safely dropped, it needs to be tried 50 times. The effect is even worse than if there is only one egg.

The above analysis is all from the perspective of eggs, and it seems difficult to get the least number of attempts. What if we look at it from a different point of view, from each height of the floor? If a floor can fall safely, how many attempts will it take at least? Look at the following analysis

In the process of programming to solve problems, if we encounter problems, we can often try the method of dynamic planning first. In the method of dynamic programming, the first thing we need to do is to find the sub-problems that make up this problem. So, in the following analysis, we first try the method of dynamic programming, how to solve this problem, which is also the thinking of a typical programmer; secondly, among the many problems, many can be directly attributed to mathematical equations. if we can write mathematical equations, then the answer will be more concise and wonderful. So, the second method will try if you sum up the mathematical equation.

Method based on dynamic programming

As mentioned earlier, if you want to adopt the method of dynamic planning, the most important thing is to find the sub-problems. Do the following analysis, assuming that f {n} means throwing eggs from the nth floor without breaking the minimum number of attempts. * eggs, possible drop position (1 ~ n), * eggs dropped from floor I, there are two cases:

Broken, the second egg, we need to start the experiment from the * layer, there is a chance for iMurray.

Unbroken, two eggs, and nmuri layer. So, when * eggs fall from the I position, the number of attempts is 1 + max (I-1, f {nmuri}), then for each I, the value of f {n} is the least number of attempts. The state transition equation is as follows: F {n} = min (1 + max (I-1, f {n-1})), where the range of I is (1, n), f {1} = 1 is over.

Promotion

The method of dynamic programming can be extended to n floors and m eggs. The analysis is as follows: suppose f {nrecom} represents the minimum number of attempts to find a * floor when you find a floor with n floors and m eggs. When * eggs are dropped from floor I, if they are broken, there will be one egg left. In order to determine the security floor in the lower floor, you need to find the sub-problem 1 times. If it is not broken, there is also a nMui layer above, and f [nMum] times, another sub-problem is needed. The state transition equation is as follows: F {n, m} = min (1 + max (f {n-1, m-1}, f {n-I, m})), where I is (1, n), f {I, 1} = 1

Method based on mathematical equation

Assuming that the minimum number of attempts is x, then * eggs must be dropped from the x floor, because: if broken, there is a floor of xmuri in front to try, and if it is not broken, there is a chance of xmuri. If the egg is not broken, you can try it from the x + (x-1) layer for the second time, why add x-1, because, when the * * egg is broken, the second egg can be tried from x-1 to x + (x-1)-1 for x-2 times. If it is not broken, then * eggs, try from the x + (x-1) + (x-2) layer for the third time. Broken or unbroken, there are x-3 attempts, and so on. So, what is the floor that can be determined with at least x attempts? X + (x-1) + (x-2) + … + 1 = x (xylene 1) / 2 the reverse question is, when the floor is 100, how many times does it take at least? X (xylene 1) / 2 > = 100, get x > = 14, at least 14 attempts.

Thank you for your reading, the above is the content of "Magic Index example Analysis", after the study of this article, I believe you have a deeper understanding of Magic Index example analysis of this problem, the specific use of the situation also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.