民科吧 关注:415,140贴子:5,131,854

回复:提一个问题,求解答

只看楼主收藏回复

有没有可能,8093瓶水挨个给一只小白鼠喝就行了,哪瓶喝死了,哪瓶就有毒,因为没有限制时间,所以有大量的时间去实验


IP属地:湖南来自Android客户端44楼2022-05-18 11:54
回复
    对"二分法不是最快的"存疑.
    设有水 n 瓶,小白鼠 m 只.
    每次试毒能够提供 1bit 的信息,它最多只能够使得可能情况数量的最大可能值变成原来的一半. 而任何一次能够提供有用信息的试毒都存在小白鼠死亡的可能性,所以为保证能够分辨出有毒的那瓶水,试毒次数至多为 m 次. 因此对于 n > 2^m,此题无解. 对于 n <= 2^m,试毒次数 q 必有 ceil(log_2(n)) <= q <= m, 其中 ceil(x) 表示不小于 x 的最小整数.
    下面构造使得 q = ceil(log_2(n)) (记作 Q) 的方法.
    将毒药按自然数由小到大编号,并写成二进制. 显然二进制位数不超过 Q. 对第 k 次试毒 (k = 1, 2, 3, ..., Q-1),选取二进制编号的 2^(Q-1) 位 (即从右往左第 Q-1 位) 为 1 的瓶子,将其中液体在试管中混合,进行试毒. 若有毒,写作 1,反之写作 0. 将各次结果从右往左写,测试完毕后读取写出的数,它就是有毒的瓶子对应的二进制编号.
    因此,现在我们得出,这个方法的试毒的最大次数次数最少. (因为不存在试毒次数一定小于该方法的方法)


    IP属地:上海来自Android客户端45楼2022-05-18 12:29
    收起回复
      2026-08-06 02:59:08
      广告
      不感兴趣
      开通SVIP免广告
      最少一次,刚好抽中有毒的那瓶就一次


      IP属地:印尼来自Android客户端46楼2022-05-18 13:22
      回复
        31楼正解,老梗了


        IP属地:浙江来自Android客户端49楼2022-05-18 15:13
        回复
          小白鼠生10000只小白鼠,然后是一次就行了啊


          IP属地:西藏来自Android客户端50楼2022-05-18 16:44
          收起回复
            先挑出来1只“幸运观众”,然后...
            之后哪位鼠鼠那啥了就说fake news


            IP属地:美国来自iPhone客户端52楼2022-05-18 18:17
            回复
              太多了会把耗子撑死


              来自Android客户端53楼2022-05-18 18:18
              回复
                1次


                IP属地:福建来自Android客户端55楼2022-05-19 10:59
                回复
                  2026-08-06 02:53:08
                  广告
                  不感兴趣
                  开通SVIP免广告
                  之前在b站看到一个大佬用的矩阵的方法,根据矩阵设计一个分配方法,一步就可以出结果,不过设计矩阵的过程比较麻烦,尤其是数量多了之后。理论上应该也适用于这个题,不过不知道数据能不能符合那个模型。


                  IP属地:江苏来自Android客户端56楼2022-05-19 12:03
                  回复
                    倒掉一瓶,宣布已经处理掉了


                    IP属地:湖南来自Android客户端57楼2022-05-19 17:16
                    回复
                      最少不是一次?第一瓶直接就死了?


                      IP属地:青海来自iPhone客户端58楼2022-05-19 18:05
                      回复
                        简单
                        2^13等于8192
                        一次就搞定了


                        IP属地:辽宁来自iPhone客户端59楼2022-05-19 21:01
                        回复
                          一次是指只能测试一瓶水?


                          IP属地:广东来自Android客户端60楼2022-05-20 04:53
                          回复