达拉崩吧的酒宴 | 感受算法的魅力

约定不等于承诺〃 2022-12-03 09:58 159阅读 0赞

> ## 1. 达拉崩吧的酒宴 ##
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>成绩</td> 
>    <td>10</td> 
>    <td>开启时间</td> 
>    <td>2019年07月29日 星期一 10:00</td> 
>   </tr> 
>   <tr> 
>    <td>折扣</td> 
>    <td>0.8</td> 
>    <td>折扣时间</td> 
>    <td>2019年08月6日 星期二 00:00</td> 
>   </tr> 
>   <tr> 
>    <td>允许迟交</td> 
>    <td>否</td> 
>    <td>关闭时间</td> 
>    <td>2019年10月8日 星期二 00:00</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **Description**
> 
> 很久很久以前，巨龙突然出现，带来灾难带走了公主又消失不见，王国十分危险，世间谁最勇敢，一位勇者赶来大声喊：“我要带上最好的剑，翻过最高的山，闯进最深的森林，把公主带回到面前”……最后，英雄 *达拉崩巴斑得贝迪卜多比鲁翁**** ***，他战胜了巨龙 *昆图库塔卡提考特苏瓦西拉松**** ***，国王把公主 *米娅莫拉苏娜丹妮谢莉红  *嫁给了 *达拉崩巴斑得贝迪卜多比鲁翁** **。*
> 
> 于是国王第二天要在 *蒙达鲁克硫斯伯古比奇巴勒城****  ***举办酒宴，一共准备了 N 桶酒。此时一位忠诚的仆人来报，有人在其中一桶酒里下毒，并且此毒要经过24小时后才会毒发身亡。现在距离晚会酒宴开始还有正好24小时，为在酒宴开始前找出哪一桶酒有毒，国王决定找一些小白鼠来试酒。（仆人不可能说谎，即**一定有且只有一桶酒有毒**）
> 
> 聪明的 *达拉崩巴斑得贝迪卜多比鲁翁****  ***本着善良的天性，决定用尽量少的小白鼠来试酒。
> 
> 请问最少需要多少只小白鼠试酒？
> 
> **Input**
> 
> 样例输入有多组。
> 
> 第一行输入整数 T，表示有 T 组用例，
> 
> 接下来 T 行， 对于魅族测试用例输入一个正整数 n 表示一共有 n 桶酒。
> 
> **Output**
> 
> 对于每个用例输出一行一个数字，代表所需的最少小白鼠数量。
> 
> **Sourse**
> 
> 北京理工大学2018年暑假集训算法总结赛 - Problem D
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>&nbsp;</th> 
>    <th>测试输入</th> 
>    <th>期待的输出</th> 
>    <th>时间限制</th> 
>    <th>内存限制</th> 
>    <th>额外进程</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>测试用例 1</td> 
>    <td>&nbsp; 
>     <ol> 
>      <li>3↵</li> 
>      <li>2↵</li> 
>      <li>3↵</li> 
>      <li>4↵</li> 
>     </ol></td> 
>    <td>&nbsp; 
>     <ol> 
>      <li>1↵</li> 
>      <li>2↵</li> 
>      <li>2↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>  </tbody> 
> </table>

--------------------

### 一、编码法来理解 ###

本题本质是一个**编码计数**的问题，但是你不知道也不太要紧（我第一次做也很懵）...

这么分析吧：每一桶酒都有两种状态 —— 被喝/不被喝，每一只喝了酒的小白鼠都有两种状态 —— 死亡/存活。那么就会想到**用二进制编码来对每一桶酒进行区分**。下面以1000桶酒为例分析~

**1、对酒编号**

先按照二进制数字大小，对每一桶酒贴上标签：

0000000000（第1桶）  
0000000001 （第2桶）  
0000000010 （第3桶）  
......  
1111100111 （第1000桶）  
......  
1111111111  （第1024桶）

不难计算，因为![2^9 <1000<2^\{10\}][2_9 _1000_2_10]，所以1000桶酒需要10位二进制数来表示。

**2、小鼠试毒**

为每一只小白鼠用数字编号，1、2、3、4...主要是为了区分。然后让小鼠试毒：

从编号倒数第1位是1的所有的桶里面取出1滴混在一起，给编号为1的小白鼠喝。  
从编号倒数第2位是1的所有的桶里面取出1滴混在一起，给编号为2的小白鼠喝。  
从编号倒数第3位是1的所有的桶里面取出1滴混在一起，给编号为3的小白鼠喝。

以此类推...比如说：第一桶酒不会给到小白鼠喝，第二桶酒只会给到第1只小白鼠喝，第三桶酒只会给到第2只小白鼠喝......第1000桶酒会给到第1、2、3、6、7、8、9、10只小鼠喝。

1000桶酒的编码是10位，所以我们需要10只小白鼠来试毒。那么真的10只小鼠就可以区分出那一桶毒酒吗？怎么通过最后的小鼠死亡结果分析，你接着往下看。

**3、结果分析**

24小时过去了，就可以来验尸了。记下有哪些编号的小白鼠悲惨地死掉了，就能推出毒酒。

如果没有小白鼠死亡。即00000 00000，那么肯定是第1桶酒有毒。  
如果只有第1个小白鼠死了。即00000 00001，则第2桶有毒。  
如果只有第1、4个小白鼠死了。即00000 01001，则第10桶有毒。

或者这样更好理解：如果编号为1000100011的酒是毒酒，则对应喝酒的只有第一只，第二只，第六只，第十只死亡。

**4、加深理解**

由于每一桶酒的编码都是独一无二的，所以每一桶酒给小鼠喝的分配情况都是独一无二的（不会出现某两桶酒都是给同样几只小鼠喝的情况），所以某桶如果是有毒的话对应最后小鼠死亡的结果是独一无二的，故我们一定可以这样来确认出那一桶独一无二的毒酒。

如果上面没看太懂，你就先理解这个，再反复看：10只小鼠有![2^\{10\}][2_10]种最后死亡的结果，所以最多可以对应1024桶酒。

**5、总结**

N桶酒，老鼠所能表示的状态数目为M，则需要的老鼠个数为 ![K=log\_M\{N\}][K_log_M_N]

而具体实验的操作方法为：

1.  每种状态按照 M 进制进行编码，编码长度为 K
2.  每个老鼠分别去拿自身的 M 中状态去实验 N 的 M 进制编码的某一位
3.  所以 K 个老鼠，等同于是 K 长度 M 进制的对应的每一位
4.  这样试验完后，就确定了每一位上面的数字，找到对应的那种状态就好。

--------------------

### 二、二分法来理解 ###

上面的理解不了，可以看看简单一点的二分法：

还是以1000桶为例，具体喝法如下：  
第一只：1-500  
第二只：1-250，501-750  
第三只：1-125，251-375，501-625，751-875  
…  
这还是一个取对数的计算，所以最少需要10只老鼠。

--------------------

### 三、代码实现 ###

方法理解了后，那就可以直接上代码了，就是一个算对数的程序，对于输入酒的桶数n，需要 ![log\_\{2\}n][log_2_n](向上取整) 只小白鼠。

主要注意，c语言中 log 函数默认以e为底，计算2为底数需要用到换底公式。

#include<stdio.h>
    #include<math.h>
    
    int main() {
        int T, i;
        long long int n;
        double m;
        scanf("%d", &T);
        for (int i = 1; i <= T; i++) {
            scanf("%lld", &n);
            m = log(n) / log(2);   //采用换底公式
            if (m != (int) m)  //若有小数部分，需要进1
                m++;
            printf("%d\n", (int) m);
        }
    }

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]

## ##

[2_9 _1000_2_10]: https://private.codecogs.com/gif.latex?2%5E9%20%3C1000%3C2%5E%7B10%7D
[2_10]: https://private.codecogs.com/gif.latex?2%5E%7B10%7D
[K_log_M_N]: https://private.codecogs.com/gif.latex?K%3Dlog_M%7BN%7D
[log_2_n]: https://private.codecogs.com/gif.latex?log_%7B2%7Dn
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20221123/d88cdd0708064fe1b27779c495552db8.png