珍珠湾ART

标题: 香水有毒——找出有毒的水 [打印本页]

作者: 海姑娘    时间: 2007-5-27 17:08
标题: 香水有毒——找出有毒的水

50杯无色透明的水,其中3杯有毒,用一种试纸可以检验水是否有毒,最不理想的情况下,最少需要检验多少次才能找出有毒的三杯水?
www.ddhw.com

 

www.ddhw.org---
---
海姑娘个人网站
 
http://www.tianxianmeimei.com/xuehua/xhindex.html

作者: 那些花儿    时间: 2007-5-27 17:58
标题: 看到这种题目就晕,不多想了,我猜我猜我猜猜猜,你别踩[:-D]

我猜想啊,最糟糕的情况就是,第一杯不是,第二杯不是,第三....到47杯都不是。所以要47次才知道剩下三杯有毒。是这个意思吗? 


 

作者: HF:    时间: 2007-5-27 18:40
标题: 回复:香水有毒——找出有毒的水

The integer part of log_2(C(50,3)) +1


 

作者: yinyin    时间: 2007-5-28 12:22
标题: 回复:香水有毒——找出有毒的水

楼上是从信息量的角度来估计所需测试次数所得的下界:15。它也可表为┌ log2C(50,3)┐,其中┌ ... ┐为  ceiling function 。但具体如何安排测试,还得考虑。直觉让我选择第一步为分50杯成16、16、16、2这四摊。

www.ddhw.com

 

作者: M.E.D    时间: 2007-5-28 17:42
标题: 回复:香水有毒——找出有毒的水

关键分几组才能达到最优?感觉应该是每次分两组,取样,混合,测试,这样的话,应该五次吧
www.ddhw.com

 

作者: husonghu    时间: 2007-5-29 00:56
标题: 回花儿,随便试试,M.E.D........

我想, HF和yinyin的思路对。方法大致是(比如):

把50个样分成5组:10,10,10,10,10。同组内取样混合,得5份样,最多试5次(更正:其实这里最多试4次就够了),可至少排除两组(20个样)是清白的,不用再试,

剩下在30个样中用类似的方法再分组, 再试......

如yinyin说,关键是每次如何组合才好。为使次数最少,每次分组的组合法很有讲究(使前后次相关).

HF和yinyin, 我的理解对吗?

总之,总共不需47次;但总共5次太少,也不可能。www.ddhw.com

(题意是有点不清。实际上,上述那样分组混合其实够烦的,可能还不如一个一个试更方便呢)



 

  本贴由[husonghu]最后编辑于:2007-5-28 20:35:28  


作者: yinyin    时间: 2007-5-30 11:41
标题: 分法{16、16、16、2}不可行。[:%]

从信息量的观点考虑,仅一种分法{12、12、12、12、2}可行。进一步思考中。

www.ddhw.com

 

作者: ob    时间: 2007-5-31 03:59
标题: 回复:香水有毒——找出有毒的水

It seems one needs 24 times to find the cups with poison water.
8, 8, 8, 8, 8, 10 need 6 times
4, 4, 4, 4, 4, 4, 4 need 7 times
2, 2, 2, 2, 2, 2 need 6 times
1, 1, 1, 1, 1, 1 need 5 times

www.ddhw.com

 





欢迎光临 珍珠湾ART (http://zzwav.com/) Powered by Discuz! X3