老鼠喝农药及类似问题

菠萝饭 196 2021-12-13

前言

最近爱看科普视频,有一个很喜欢的up主——李永乐老师讲的科普视频十分有趣。通俗易懂又涨姿势。今天看到他一个讲算法、进制的科普视频——《老鼠喝农药》。以及留的作业。自己研究了下,做一记录。

  • 老鼠喝农药问题:

    说,现有100瓶液体,其中99瓶是无毒液体,只有1瓶是农药,老鼠喝了有毒农药一周后会死去。请问,最少需要几只老鼠就可找出无毒的液体。

解法:
1. 将1-100瓶液体分别用二进制数字编号,可编辑为:
0000001 - 1100100 这100个7位二进制数字。(为对比方便,将不到7位的二进制用0补全) 
2. 使用7只老鼠并编号,分别对应七位数(从前到后)。让其喝掉各自位上数字为1的液体,然后培养一周
3. 一周后将死亡小鼠编号统计。即可得到农药液体的编号。

计算:
假设,死掉的老鼠是1、4、6,则表示:
1:首位,该农药编号首位为1,
4:该农药第四位上编号为1,
6:该农药第四位上编号为1。
其他老鼠存活,说明该农药其他位上不为1,为0:

所以,该农药二进制编号为:1001010,转换为十进制:74

课后作业

  • 老师最后又给布置了一个课后作业: 如果有100个人,排队报数。如果是奇数就会被击毙,如果是偶数就留下,继续排队报数。直到留下最后一个人,请问站在几号位置可以活到最后?
个人解答
还是利用二进制将数据处理再求解:
已知有100个人,最后要仅留下一人(偶数),则该人每次排队时都得要是偶数才可留到最后。

因为总共100人,可以用7位的二进制数将该100人编号都表示。(0000001 - 1100100)
因为每次排队后都是进行了减半处理(如果是2的倍数,更好理解,如32),直至为1。

所以,该数x满足:
1. x<=100,即:x <= 1100100
2. x的二进制数除首位都为0(2的倍数==偶数)

联立可知: x = 1000000, x=64

思考:

这种通过进制转换方法求解问题,类似于傅里叶变换对声音或图像的处理解决方法。用另一种方法或角度描述同一个信息(农药编号、存活人编号)。而同一信息的另一种描述数据更容易被处理和求解。也就达到了快速高效求解复杂问题的目的。