a******n 发帖数: 91 | 1 有12个球,已知其中一个和其他的重量不同。给你一个scale, 怎样秤3次称出那个不同
的球来。
我想来想去只能想出称4次的方法来。请高人指点。谢谢!! |
L****t 发帖数: 924 | 2 只知道不同还是知道过重还是过轻。
【在 a******n 的大作中提到】 : 有12个球,已知其中一个和其他的重量不同。给你一个scale, 怎样秤3次称出那个不同 : 的球来。 : 我想来想去只能想出称4次的方法来。请高人指点。谢谢!!
|
J**********g 发帖数: 213 | 3 I remember it's one of problems in following book:
Heard on The Street: Quantitative Questions from Wall Street Job Interviews
Please check the answer in the book. I remember tThe key idea is to make full use of all balls in each scaling...I know this does not make sense, but it's like, for example, after you kick out six balls in the first scaling,
you can borrow some balls back later in following scalings. |
g*******y 发帖数: 1930 | 4 先分三堆,A,B,C
称A vs B
然后根据3种结果:
(1) if A==B 特殊球在C中: 4个球称2次,很简单了
(2) if A>B 特殊球可能是A中的某个偏重,或者是B中的某个偏轻:
接下来,(A中选2个+B中选1个) vs (A中选2个+B中选1个)
这一轮下来,可能性最多为三种,再称一次就搞定了。
(3) if A |
g*******y 发帖数: 1930 | 5 btw
貌似可以证明,对于任意n个球,最小次数是 ceiling(Log_3(2n))
【在 a******n 的大作中提到】 : 有12个球,已知其中一个和其他的重量不同。给你一个scale, 怎样秤3次称出那个不同 : 的球来。 : 我想来想去只能想出称4次的方法来。请高人指点。谢谢!!
|
g*******y 发帖数: 1930 | |
r********g 发帖数: 1351 | 7
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~这个怎么选呢?如果左边大怎么办?
【在 g*******y 的大作中提到】 : 先分三堆,A,B,C : 称A vs B : 然后根据3种结果: : (1) if A==B 特殊球在C中: 4个球称2次,很简单了 : (2) if A>B 特殊球可能是A中的某个偏重,或者是B中的某个偏轻: : 接下来,(A中选2个+B中选1个) vs (A中选2个+B中选1个) : 这一轮下来,可能性最多为三种,再称一次就搞定了。 : (3) if A
|
S******s 发帖数: 5376 | 8 RIGHT
【在 g*******y 的大作中提到】 : 先分三堆,A,B,C : 称A vs B : 然后根据3种结果: : (1) if A==B 特殊球在C中: 4个球称2次,很简单了 : (2) if A>B 特殊球可能是A中的某个偏重,或者是B中的某个偏轻: : 接下来,(A中选2个+B中选1个) vs (A中选2个+B中选1个) : 这一轮下来,可能性最多为三种,再称一次就搞定了。 : (3) if A
|
a*******s 发帖数: 4 | 9 好像有个结果是:m=(3^n - 3)/2个球,其中一个不一样,不知道轻重,可以用n次称出
来。
n=3时,m=12. |
r********g 发帖数: 1351 | 10 我还是觉得楼上的方法到了第二轮就解不出来了,比如如果A>B, 这样 A中的俩偏重,
或者B中的俩骗轻(我理解的是(A
中选2个+B中选1个) vs (A中选1个+B中选2个) ),就没法选了啊。。。google了一下
,还是觉得下面这个答案更标
准???
一、分组 1~12个球分别贴上标签 A1 A2 A3 A4 , B1 B2 B3 B4 , C1 C2 C3 C4
二、A1 + A2 + A3 + A4 ~ B1 + B2 + B3 + B4 (第1次)分下列情况。
1、A1 + A2 + A3 + A4 = B1 + B2 + B3 + B4 ,说明坏球是C1 C2 C3 C4中的一个。
A1 + A2 + A3 ~ C1 + C2 + C3(第2次)
⑴若 A1 + A2 + A3 = C1 + C2 + C3 , 说明坏球是C4, A1 ~ C4(第3次),因为不
可能相等,若A1 > C4,则
C4偏轻;若 A1 < C4,则C4偏重。
⑵若 A1 + A2 + A3 > C1 + C2 + C3 , 说明坏球是C1 C2 C3中的一个并且偏轻,C1
~ C2(第3次
【在 g*******y 的大作中提到】 : 先分三堆,A,B,C : 称A vs B : 然后根据3种结果: : (1) if A==B 特殊球在C中: 4个球称2次,很简单了 : (2) if A>B 特殊球可能是A中的某个偏重,或者是B中的某个偏轻: : 接下来,(A中选2个+B中选1个) vs (A中选2个+B中选1个) : 这一轮下来,可能性最多为三种,再称一次就搞定了。 : (3) if A
|
g*******y 发帖数: 1930 | 11 第二次是
A1+A2+B1 vs A3+A4+B2
if result is equal, then one of B3, B4 is lighter
if result is >, then one of A1, A2 is heavier or B2 is lighter
if result is >, then one of A3, A4 is heavier or B1 is lighter
【在 r********g 的大作中提到】 : 我还是觉得楼上的方法到了第二轮就解不出来了,比如如果A>B, 这样 A中的俩偏重, : 或者B中的俩骗轻(我理解的是(A : 中选2个+B中选1个) vs (A中选1个+B中选2个) ),就没法选了啊。。。google了一下 : ,还是觉得下面这个答案更标 : 准??? : 一、分组 1~12个球分别贴上标签 A1 A2 A3 A4 , B1 B2 B3 B4 , C1 C2 C3 C4 : 二、A1 + A2 + A3 + A4 ~ B1 + B2 + B3 + B4 (第1次)分下列情况。 : : 1、A1 + A2 + A3 + A4 = B1 + B2 + B3 + B4 ,说明坏球是C1 C2 C3 C4中的一个。 : A1 + A2 + A3 ~ C1 + C2 + C3(第2次)
|
r********g 发帖数: 1351 | 12 晕,我还以为你写错了。。。自动理解成A2B1 v.s. A1B2了。。
这个方法更简单一些,不用refer已经比较过的球了,包子一个奖励:)
【在 g*******y 的大作中提到】 : 第二次是 : : A1+A2+B1 vs A3+A4+B2 : if result is equal, then one of B3, B4 is lighter : if result is >, then one of A1, A2 is heavier or B2 is lighter : if result is >, then one of A3, A4 is heavier or B1 is lighter
|
S*****o 发帖数: 4 | 13 这里的scale指的是天平啊,我还以为是秤。那balance是什么? |