【 Intellectual problems of Dachang 】 Toxic problem of bottle water

There are many variants of the toxic problem of bottled water ：

* 1000 Bottle of water 1 Bottle water is toxic , A drop of water will kill the mouse , But it takes a month , How many mice do you need to find the poisonous water .
* 1000 Bottle of liquid medicine ,1 Bottle toxic , Rat hair 24h, How to use the least mice 24h Find poison inside .
* …
Anyway, rats don't die right away （ mouse ： I'm too hard ）. So when it's practical , Not available 1 Which bottle of water was poisonous was detected by a mouse .

It's time to think . If you know about the bloom filter , So that's a question for you , It's easier （ We can learn from it ）.

This intellectual question , Focus on your application of binary life scenarios .

We know 2 Of 10 The power is equal to 1024,1024 All natural numbers within can be used 10 Binary number of digits .1000 <= 1024. That's easy ,

We will 1000 Bottle water from water[0] reach water[999] Number separately , And into 10 Binary number of digits .

9 8 7 6 5 4 3 2 1 0 digit

0 0 0 0 0 0 0 0 0 0 Corresponding number 0
0 0 0 0 0 0 0 0 0 1 Corresponding number 1
1 1 1 1 1 0 0 1 1 1 Corresponding number 999

We will 10 Mice from mouse[0] reach mouse[9] Number

* Let No mouse[0] A mouse drinks the first 0 Bit is 1 Water of
* Let No mouse[1] Mice drink the first 1 Bit is 1 All the water of
* Let No mouse[2] Mice drink the first 2 Bit is 1 All the water of
* And so on
In the end, according to the rat's death , Figure out the number n. from mouse[0] reach mouse[9] The living mouse corresponds to 0, The corresponding bit of the dead mouse is 1.

• « 上一篇： Yes 1000 Bottle of water , One of them is toxic ...( Intelligence questions )
• » 下一篇： A programmer is leaving Chongqing