找错药

ob · 发表于 2006-3-19 09:17:48

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

ob · 发表于 2006-3-20 23:44:09

Good!

有空想想 · 发表于 2006-3-20 04:36:52

我们有 n 瓶药，每粒应为 1 克。其中有 m （m ＝ 0 ... n ）瓶，每粒为 2 克。

我们将 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）

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 克。以上刮号中的值说明二进制算法。（注意，二进制表示瓶子编号是从右至左）。

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

ob · 发表于 2006-3-20 03:21:52

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

有空想想 · 发表于 2006-3-20 01:42:46

给五瓶标号，1，2，3，4，5。

从第一瓶取 1 粒，第二瓶取 2 粒，.... 第五瓶取 5 粒。共 15 粒。

如果是 16 克，第一瓶错；

如果是 17 克，第二瓶错；

18 克，第三瓶；

19 克，第四；

20 克，第五。

ob · 发表于 2006-3-19 21:23:16

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

有空想想 · 发表于 2006-3-19 10:08:50

一次

		自动登录	找回密码
密码			立即注册

动态微博

找错药

Good![@};-]

in general ...

You are right[:-Q]To make the question more

回复：Same topic, different weight, the sampling shou

Same topic, different weight, the sampling should

这不跟称洗衣粉的题一样么？