珍珠湾ART

标题: 找错药 [打印本页]

作者: ob    时间: 2006-3-19 09:17
标题: 找错药

一人买了5瓶一模一样的药,买回家后,商店打电话来说其中有一瓶拿错了,本来这5瓶里的药应该是每颗1克,但是错的那瓶重,是每颗2克。其他的属性:大小,形状,颜色。。。绝对看不出来的。现你有一杆称,能准确的量出物体的重量(克)。问:最少称几次一定能找出错的那瓶药?
(假设每瓶里的药无限多,拿多少颗去称随便,还可以在药上,作记号,表明是哪一瓶里的药)
www.ddhw.com

 

作者: 有空想想    时间: 2006-3-19 10:08
标题: 这不跟称洗衣粉的题一样么?

一次
www.ddhw.com

 

作者: ob    时间: 2006-3-19 21:23
标题: Same topic, different weight, the sampling should

be different. 1 time is correct. How to do sampling? www.ddhw.com

 

作者: 有空想想    时间: 2006-3-20 01:42
标题: 回复:Same topic, different weight, the sampling shou

给五瓶标号,1,2,3,4,5。
从第一瓶取 1 粒,第二瓶取 2 粒,.... 第五瓶取 5 粒。共 15 粒。
如果是 16 克,第一瓶错;
如果是 17 克,第二瓶错;
18 克,第三瓶;
19 克,第四;
20 克,第五。
www.ddhw.com

 

作者: ob    时间: 2006-3-20 03:21
标题: You are right[:-Q]To make the question more

complicated, how about if there are 10 bottles. Two bottles have problem.
www.ddhw.com

 

作者: 有空想想    时间: 2006-3-20 04:36
标题: in general ...

我们有 n 瓶药,每粒应为 1 克。其中有 m (m = 0 ... n )瓶,每粒为 2 克。www.ddhw.com
我们将 n 瓶药编号,1 到 n。
然后,我们从第一瓶取出 1 粒药,从第二瓶取出 2 粒药,从第三瓶取出 4 粒药,.... 从第 n 瓶中取出 2^(n-1) 粒药。
将这些药放在一起称重,就一次找出那 m  瓶药。
作为例子,数 10 大了点,我们以 5 瓶为例。
1+2+4+8+16 = 31 粒
如果是 31 (31+0) 克:没有两克药瓶,(二进制值: 00000)
如果是 32 (31+1) 克:瓶 1 为 2 克粒,(二进制值: 00001)
如果是 33 (31+2) 克:瓶 2 为 2 克粒,(二进制值: 00010)
34 (31+3) 克:瓶1,2  (00011)
35 (31+4) 克:瓶3 (00100)
36 (31+5):1,3 (00101)www.ddhw.com
37 (31+6):2,3 (00110)
38 (31+7):1,2,3 (00111)
....
62 (31+31):1,2,3,4,5 (11111), 所有药瓶都是两克药瓶。
 
其实用二进制,这种算法非常容易理解。n 瓶,n 个 bit (二进制中的一位)。每位有两个值 0,1 -- 即我们的,要么多出 0克,要么多出 1 克。以上刮号中的值说明二进制算法。(注意,二进制表示瓶子编号是从右至左)。
www.ddhw.com

 

  本贴由[有空想想]最后编辑于:2006-3-20 11:31:40  


作者: ob    时间: 2006-3-20 23:44
标题: Good![@};-]

  Good!









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