Topic describes

There were 1000 bottles of liquid medicine, one of which was poison. If you drank a drop of it, you would die a day later. Now provide a batch of rabbits to test poison, then how do we spend the least rabbits, the least time, to find this bottle of poison?

Think about it in terms of time

In a nutshell, it’s making rabbits. Take 1000 rabbits directly to test the poison, one rabbit is responsible for a bottle of potion. The result, of course, is 1000 rabbits, and the results come out in a day. This advantage is obvious, is fast; Disadvantages are also obvious: the use of too many rabbits, occupy resources.

Think about it from a spatial point of view

If we save rabbits for environmental reasons, then we can consider using 2 points. The first round is divided into 500 bottles of poison for a group, first put a rabbit, drink one drop of each bottle of potion, so you can eliminate 500 bottles. If alive, continue to use the rabbit, if dead, replace the rabbit. Let’s take the worst-case scenario: one rabbit at a time.

The next round of 250 bottles, loop iteration, 1000 – > 500 – > 250 – > 125 – > 63-32-16-8 – > > > > 4 – > 2 – > 1

So 10 arrows, that’s 10 times, that’s 10 days. In this way, we only used 10 rabbits, which was very economical, but we had to wait too much.

Think in terms of programming

Is there a better way? Short time, high efficiency.

Of course, since we can drink multiple bottles at once, we can simulate 1024 scenarios with 10 rabbits.

Number the potions from 1-1000, rabbits numbered, 1-10, 1000 bottles numbered, all converted to binary numbers, 1 is 000, 000, 0001,1000 is 111, 110, 1000.

In this case, the number one is given to the rabbit to drink a drop of the potion. Because the number is unique, so finally according to the dead rabbit, reverse combination, is the potion number.

In this way, 10 rabbits can successfully test the poison in just one day. Both space and time are the fastest.

The topic was obtained from the wechat public number niuniumaite. This article is excerpted and deleted for my personal interest.