虫骑吧 关注:5贴子:403
  • 4回复贴,共1

一个比较火的算法题

只看楼主收藏回复

最近一道比较火的算法题,因为互联网信息繁杂,可能衍生出了多个变种版本,总之就以我看到的版本为准吧。
题目:现有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药,无法通过重量、外观、颜色、气味来判断区别,任何喝下毒药的生物都会在一星期之后死亡。现在你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?


IP属地:湖南1楼2023-02-15 09:08回复
    原题目还有一个条件,还有足量的空瓶子可供使用。
    毒性发作需1周、只有1周时间,从这些条件联想到什么?实际上这几个条件等价于每只老鼠只有一次试吃机会。
    刚开始看到题目的时候,思路也是常规的办法,比如分组,但是一看没那么简单,因为只有一次机会,就算分成10组确定了范围仍然只排除了900瓶,还有100瓶没法区分。
    之后突然灵光一闪:既然不能一次找出毒药,何不分步进行呢?要知道可是有10只老鼠啊。
    说来思路也简单。
    第一步,仍然是分组,1000瓶分成十组,每组100瓶,首先将十组进行编号,第一组表示1-100瓶,第二组表示101-200瓶,以此类推。
    第二步,将第一组的100瓶,每一瓶都取少许几滴液体放入一个空瓶进行混合,反复操作100次后会得到1瓶混合了第一组100瓶的混合液,记为a1。考虑到有足够的空瓶可用,那么第二组到第十组也如法炮制,分别记为a2-a10,这样就得到了10瓶混合物。
    第三步,a1-a10分别喂给10只老鼠,其中必有1只老鼠死亡,那么毒药在这瓶混合液对应的100瓶中。
    第四步,再将死老鼠这100瓶平均分成10组,每组每瓶都取少许几滴混合放入1个空瓶,又得10瓶混合药水,其中9瓶给9只老鼠喝,不论这9只是否死亡,都可将范围进一步缩小到1/10。
    第五步,然后这10瓶平均分成5组,每组每瓶都取少许几滴放入1个空瓶,再5瓶混合药水,分给5只老鼠喝,1只老鼠死,得到混有毒药的2瓶药水;再取出给2只老鼠喝,得到毒药。
    检查一遍思路没问题,但是,违背题目条件,就算不考虑分组、操作的时间,因为只有一周的检测时间,所以还是行不通。


    IP属地:湖南2楼2023-02-15 10:33
    回复
      最后实在是想不到答案,在网上搜寻答案,原来还是跟二进制有关。
      可以先看一个简化版的该问题:有八个瓶子,一瓶有毒七瓶是水,只能通过饮用判断是否有毒,老鼠若饮下毒药即刻死亡,现有三只活老鼠和若干空瓶,每只老鼠只有一次试吃机会,问如何快速找到毒药?
      老鼠的状态有两种,死和活(1和0),而三只老鼠的状态有2^3 种组合,正好表征8个瓶子。这关系不就建立起来了吗?
      000---------1
      001---------2
      010---------3
      011---------4
      100---------5
      101---------6
      110---------7
      111---------8
      比如101就表示第2只老鼠存活,011表示第1只老鼠存活,110表示第3只老鼠存活。
      但是具体要怎么操作呢?注意看1-8的二进制表示,其中5678的第一位都是1,3478第二位都是1,2468的第三位都是1,那么按这种规则制取三瓶混合液(5678每瓶取少许几滴,3478每瓶取少许几滴,2468每瓶取少许几滴),分别给第一、第二、第三只老鼠吃,观察最后的结果即可得到毒药在哪个瓶子里。比如最后只有第三只老鼠死亡,二进制表示为001,即表示毒药是第2瓶。


      IP属地:湖南3楼2023-02-15 11:01
      回复
        推广到原题目,实际上就是用10只老鼠去试2^10次方个瓶子,找出有毒的那一瓶,因为2的10次方=1024>1000,因此该算法在原题目中仍然有效,无非就是实际操作的时候麻烦一点。
        接下来是重点,为什么这个算法是可行的呢?逻辑关系是什么?
        首先我验证了简化版的情况,用穷举法,将1-8号瓶分别有毒的情况作了推演,发现完全符合算法预期,那么根据演绎推理,将数量从2的3次方推广到2的10次方肯定是ok的,则实际上得出了这么一个结论:n位二进制数可以表示2^n个数,这是显然的。
        那么逻辑呢?为什么要这么操作,这实际上还是因为二进制,再来看1-8的二进制表示,有没有发现,第一位是1的有四种组合,第二位是1的也是四种,第三位是1还是四种,反过来第一位是0的也是一样的。所以这不就出来了吗,把第一位是1的四种混到一起,第二位是1的四种混到一起,第三位是1的四种混一起,分别给三只吃,这里面就把8种情况全部都囊括进去了,所以只需看最后结果就能知道哪瓶有毒,是不是很神奇?


        IP属地:湖南4楼2023-02-15 11:33
        收起回复