s*i
发帖数: 5025 | 1 现有酒 n 瓶。其中可能有少量几瓶 （m） 含有铊毒 (n > m)。
作为一个千老，你有老鼠若干。
你可以取多瓶酒滴混合喂老鼠。有毒就死。
求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。 |
M******n
发帖数: 43051 | 2 不用老鼠，既然n
【在 s*i 的大作中提到】
: 现有酒 n 瓶。其中可能有少量几瓶 （m） 含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。
|
f*******i
发帖数: 1049 | 3 m小于n吧，如果m够小，用二分法大概log n时间吧
千老，你有老鼠若干。="" :="" 你可以取多瓶酒滴混合喂老鼠。有毒就死。="" :=""
求解，怎么做才能最节省老鼠而验出哪瓶有毒。="">
【在 s*i 的大作中提到】
: 现有酒 n 瓶。其中可能有少量几瓶 （m） 含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。
|
s*i
发帖数: 5025 | 4 n > m
原文已经改了
[发表自未名空间手机版 - m.mitbbs.com]
【在 M******n 的大作中提到】
: 不用老鼠，既然n
|
s*i
发帖数: 5025 | 5 不是说复杂度。说具体的算法。显然跟m有关。
"
[发表自未名空间手机版 - m.mitbbs.com]
【在 f*******i 的大作中提到】
: m小于n吧，如果m够小，用二分法大概log n时间吧
:
: 千老，你有老鼠若干。="" :="" 你可以取多瓶酒滴混合喂老鼠。有毒就死。="" :=""
: 求解，怎么做才能最节省老鼠而验出哪瓶有毒。="">
|
J**0
发帖数: 1634 | |
s******s
发帖数: 13035 | 7 m+1?
【在 s*i 的大作中提到】
: 现有酒 n 瓶。其中可能有少量几瓶 （m） 含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。
|
a***a
发帖数: 4195 | 8 这个还是一瓶一瓶灌比较省老鼠吧？
要不然，两瓶一混，老鼠死了，拿出一瓶灌，老鼠还是死了，你还得灌剩下那瓶，结果
又死了，弄死三个 才鉴别出两瓶，更浪费了。 |
s*i
发帖数: 5025 | 9 显然不是啦。比如最多就1瓶有毒。总共16瓶。你的方法最差情况要测试16次呢。
二分法最多9次就搞定了
【在 a***a 的大作中提到】
: 这个还是一瓶一瓶灌比较省老鼠吧？
: 要不然，两瓶一混，老鼠死了，拿出一瓶灌，老鼠还是死了，你还得灌剩下那瓶，结果
: 又死了，弄死三个 才鉴别出两瓶，更浪费了。
|
J**0
发帖数: 1634 | 10 问题是你要省老鼠，不是省灌的次数
【在 s*i 的大作中提到】
: 显然不是啦。比如最多就1瓶有毒。总共16瓶。你的方法最差情况要测试16次呢。
: 二分法最多9次就搞定了
|
|
|
a*****3
发帖数: 10373 | 11 hehe, you are talking about the worst case. The best case is both are good,
you can save one attempt without losing one mouse with mixed drink.
【在 a***a 的大作中提到】
: 这个还是一瓶一瓶灌比较省老鼠吧？
: 要不然，两瓶一混，老鼠死了，拿出一瓶灌，老鼠还是死了，你还得灌剩下那瓶，结果
: 又死了，弄死三个 才鉴别出两瓶，更浪费了。
|
a***a
发帖数: 4195 | 12 要是只有1瓶没毒呢？ 你二分怎么把那瓶没毒的找出来？ 要废掉多少老鼠？
【在 s*i 的大作中提到】
: 显然不是啦。比如最多就1瓶有毒。总共16瓶。你的方法最差情况要测试16次呢。
: 二分法最多9次就搞定了
|
s*i
发帖数: 5025 | 13 有道理。我改了原文。改成用老鼠的次数。
[发表自未名空间手机版 - m.mitbbs.com]
【在 J**0 的大作中提到】
: 问题是你要省老鼠，不是省灌的次数
|
s*i
发帖数: 5025 | 14 按照某牛的做法：
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
灌四只老鼠，按列混合。根据结果可以得出哪个有毒的。
[发表自未名空间手机版 - m.mitbbs.com]
【在 a***a 的大作中提到】
: 要是只有1瓶没毒呢？ 你二分怎么把那瓶没毒的找出来？ 要废掉多少老鼠？
|
j****k
发帖数: 27 | 15 http://www.matrix67.com/blog/archives/4361/comment-page-2
大家应该都听说过这个老题目：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的
水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只
小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10
位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子，让第二只老鼠
喝掉所有二进制数右起第二位是 1 的瓶子，等等。一星期后，如果第一只老鼠死了，
就知道毒药瓶子的二进制编号中，右起第一位是 1 ；如果第二只老鼠没死，就知道毒
药瓶子的二进制编号中，右起第二位是 0 ……每只老鼠的死活都能确定出 10 位二进
制数的其中一位，由此便可知道毒药瓶子的编号
了。
现在，有意思的问题来了：如果你有两个星期的时间（换句话说你可以做两轮实验
），为了从 1000 个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死
掉的老鼠，就无法继续参与第二次实验了。
答案：7 只老鼠就足够了。事实上，7 只老鼠足以从 37 = 2187 个瓶子中找出毒
药来。首先，把所有瓶子从 0 到 2186 编号，然后全部转换为 7 位三进制数。现在，
让第一只老鼠喝掉所有三进制数右起第一位是 2 的瓶子，让第二只老鼠喝掉所有三进
制数右起第二位是 2 的瓶子，等等。一星期之后，如果第一只老鼠死了，就知道毒药
瓶子的三进制编号中，右起第一位是 2 ；如果第二只老鼠没死，就知道毒药瓶子的三
进制编号中，右起第二位不是 2，只可能是 0 或者 1 ……也就是说，每只死掉的老鼠
都用自己的生命确定出了，三进制编号中自己负责的那一位是 2 ；但每只活着的老鼠
都只能确定，它所负责的那一位不是 2 。于是，问题就归约到了只剩一个星期时的情
况。在第二轮实验里，让每只活着的老鼠继续自己未完成的任务，喝掉它负责的那一位
是 1 的所有瓶子。再过一星期，毒药瓶子的三进制编号便能全部揭晓了。
类似地，我们可以证明， n 只小白鼠 t 周的时间可以从 (t+1)n 个瓶子中检验出
毒药来。 |
f*******i
发帖数: 1049 | 16 以前大概看过这类解法，楼主给的条件太宽泛了
10
【在 j****k 的大作中提到】
: http://www.matrix67.com/blog/archives/4361/comment-page-2
: 大家应该都听说过这个老题目：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的
: 水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只
: 小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
: 这个问题的答案也堪称经典：把瓶子从 0 到 999 依次编号，然后全部转换为 10
: 位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子，让第二只老鼠
: 喝掉所有二进制数右起第二位是 1 的瓶子，等等。一星期后，如果第一只老鼠死了，
: 就知道毒药瓶子的二进制编号中，右起第一位是 1 ；如果第二只老鼠没死，就知道毒
: 药瓶子的二进制编号中，右起第二位是 0 ……每只老鼠的死活都能确定出 10 位二进
: 制数的其中一位，由此便可知道毒药瓶子的编号
|
J**0
发帖数: 1634 | 17 但m可以等于upto n-1：）
【在 s*i 的大作中提到】
: 有道理。我改了原文。改成用老鼠的次数。
:
: [发表自未名空间手机版 - m.mitbbs.com]
|
r*********n
发帖数: 4553 | 18 log(n)只老鼠
这是PDA版学术化的开端吗？
【在 s*i 的大作中提到】
: 现有酒 n 瓶。其中可能有少量几瓶 （m） 含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。
|
M******n
发帖数: 43051 | 19 m不等于1哦
【在 r*********n 的大作中提到】
: log(n)只老鼠
: 这是PDA版学术化的开端吗？
|
n******7
发帖数: 12463 | 20 你显然是千老
因为m是不确定的，所以跟你这里说的完全不是一回事
【在 s*i 的大作中提到】
: 显然不是啦。比如最多就1瓶有毒。总共16瓶。你的方法最差情况要测试16次呢。
: 二分法最多9次就搞定了
|
|
|
t**t
发帖数: 27760 | 21 上ICP，一个老鼠都不要。
【在 s*i 的大作中提到】
: 现有酒 n 瓶。其中可能有少量几瓶 （m） 含有铊毒 (n > m)。
: 作为一个千老，你有老鼠若干。
: 你可以取多瓶酒滴混合喂老鼠。有毒就死。
: 求解，怎么做才能最节省用老鼠的次数而验出哪瓶有毒。
|
a***e
发帖数: 27968 | 22 一瓶有毒4次搞定吧
【在 s*i 的大作中提到】
: 显然不是啦。比如最多就1瓶有毒。总共16瓶。你的方法最差情况要测试16次呢。
: 二分法最多9次就搞定了
|
l*******s
发帖数: 7316 | 23 F(n,m) = 当m为已知数时，最少试验次数。
T(n,m) = 当m为已知上限时，1为下限时，最少试验次数。
F(n,m)=MIN{ F1(n,m), F2(n,m),…}
T(n,m)=MIN{ T1(n,m), T2(n,m),…}
F1,T1: 逐瓶试验，
F2,T2: 两分法。
其他方法估计不会优于这两种方法中较少的试验次数。
F1(n,m) =n-m,
T1(n,m) =n-1,
F2(n,1) =log2(n)
F2(n,m)=2*(m-1)*( log2(n)-P)+2^(P+1)-2, P=CEIL[log2(m-1)]
T2(n,m)= F2(n,m)+m-1
有按照可能的试验结果给出 F(n,m)=log2[C(n,m)],
这是理论上的最低上限，但除了m=1, 设计不出可行的方案。
最简单的例子是n=4, m=3. log2[C(4,3)]= log2[4]=2. 设计不出可行的2次试验的方
案。 |
s*i
发帖数: 5025 | 24 大牛！赞。我觉得最后一个例子特别说明问题。
【在 l*******s 的大作中提到】
: F(n,m) = 当m为已知数时，最少试验次数。
: T(n,m) = 当m为已知上限时，1为下限时，最少试验次数。
: F(n,m)=MIN{ F1(n,m), F2(n,m),…}
: T(n,m)=MIN{ T1(n,m), T2(n,m),…}
: F1,T1: 逐瓶试验，
: F2,T2: 两分法。
: 其他方法估计不会优于这两种方法中较少的试验次数。
: F1(n,m) =n-m,
: T1(n,m) =n-1,
: F2(n,1) =log2(n)
|
