Readme - Leetcode — ContextQMD

根据信息论，要从N个桶里面挑出有毒的那一个，需要的信息量是 log_2^(N).

根据题意，对于一个猪，它在一个小时内可以进行t次尝试 t = 60min/15min = 4.

对于一个猪的t次尝试，总共会有t+1种结果，即不中毒、第15min中毒、第30min中毒、... 第60min中毒。根据信息论，从中可以抽取的信息量是 log_2^(t+1)。

所以总共需要猪的个数是: log_2^(N) / log_2^(t+1) = log_(t+1)^N.

先思考一只猪，在题意的15min/60min的条件下，能鉴别出几桶水？答案是5. 因为这5瓶水对应了这只猪第15分钟死（第一桶有毒）、第30分钟死（第二桶有毒）、第45分钟死（第三桶有毒）、第60分钟死（第四桶有毒）、不死（前四桶都没毒，根据题意，必然是第五桶有毒）。

既然一只猪能鉴别五桶，那么两只猪就是25桶，为什么？因为这25桶水可以按照五进制编码两个bit：比如01，表示这瓶水不给A猪喝，但给B猪第一批次喝；又比如34，表示这瓶水给A猪第三批次喝，给B猪第四批次喝。最后，根据AB两只猪死亡的状态（死或不死、在什么时候死）可以鉴别出有毒的那一桶的编码。

同理引申，那么三只猪就是可以鉴别5^3=125桶。最后，想鉴别1000桶就话，需要log(5)(1000)=5只猪。