问题描述:
有1000个瓶子,其中有1个装的液体是有毒的,其余的999个装的是无毒的,有10只小白鼠用来测试,请找出装有毒的液体的瓶子。
解法1:二分查找
因为小白鼠测试的结果只有存活与死亡两种结果,所以每次测试可以分为两类,用二分查找的话,二叉树有十层,最坏情况下,给小白鼠喂药的次数为500+250+125+63+32+16+8+2+1=1001。
解法2:将1000个瓶子编号,然后转换成二进制,二进制的位数为10位,如果不过10位,高位用0填充,然后将十进制数第一位为1的喂第一个小白鼠,十进制第二位为1的喂给第二个小白鼠,以此类推。。。最后死亡的小白鼠为1,活着的小白鼠为0,组成的二进制数转换成十进制,对应的编号就是有毒的瓶子。这种解法,需要给小白鼠喂药的次数为1到1000转换成二进制后1的个数,我们算1到1024的(因为1到1000的个数约等于1-1024的,而且1-1024的比较好算),因为1到1024的十进制数中,0的个数和1的个数是相等的,总共有1024个十进制数,所以0和1总共的个数为1024*10=10240个,所以1的个数为5120个,也就是说,这种情况下,需要给小白鼠喂药5120次,约是第一种方法的5倍。
问题变种:
如果给上面的问题加些限制,比如小白鼠在吃过之后,一个星期之后才会死亡,如果采用解法1的话,最坏的情况下,将会使用10个星期,但是使用解法2的话,一个星期的时间,将会找出有毒的瓶子。
总结:在解决一些问题的时候,有时候可以在一方面减少复杂度,这就意味着在增加其它方面的复杂度,因为问题就在那里,不管用什么方法,它就在那里,不大不小。
分享到:
相关推荐
幼儿园教案2021-小班综合活动:我和瓶子做朋友.doc
小班综合活动:我和瓶子做朋友.doc
瓶模拟器 Java中的瓶子模拟器
瓶子目标检测 yolov5 瓶子检测数据集, 类别名:bottle; VOCtrainva2012数据集 提取得到,标签类别:txt和 xml两种
初中语文文学讨论名著导读钢琴教师:谁是瓶子里的精灵
OpenCASCADE提供的官方引导教程:画瓶子的PDF。通过这个PDF可以了解OpenCASCADE中的常用类和静态函数的使用方法。例如DynamicType函数。
幼儿园中班游戏:好玩的瓶子.docx
大班体育教案:玩瓶子.doc
中班数学:瓶子宝宝.doc
美术教案:瓶子穿新衣.doc
巴克莱-美股-可持续产业-塑料垃圾:不要丢掉你的瓶子-619-72页.pdf
有这样一道智力题:“某商店规定:三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶,她最多可以换多少瓶汽水喝?”答案是5瓶,方法如下:先用9个空瓶子换3瓶汽水,喝掉3瓶满的,喝完以后4个空瓶子,用3个再换一...
幼儿园教案2021-大班体育教案:玩瓶子.doc
小班科学:瓶子国王的烦恼.docx
大班亲子游戏教案:瓶子游戏.doc
用MATLAB进行瓶子合格检测,基于灰度值的检测
1、YOLO瓶子检测数据集 2、类别名: bottle 3、来源:从 VOCtrainva2012数据集 单类别提取得到 4、标签类别:txt和 xml两种 5、图片数量:812
比较好玩的一个minecraft地图,你要在好几个瓶子中生存,并找到所有的海绵和一个隐藏密室~
幼儿园教案2021-中班数学:瓶子宝宝.doc
1、VOC瓶子检测数据集 2、类别名: bottle 3、来源:从 VOCtrainval2007数据集 单类别提取得到 4、标签类别:txt和 xml两种 5、图片数量:262