微软的一道面试题

Question

12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。（不允许用其他的工具）

Answer 1

A B C D
3 3 3 3
3 3 3 3
3 3 3 3
3 3 3 3
A:B A:B A:B A:B
A:C A:C A:C A:C
A(1:1) B(1:1) C(1:1) D(1:1)
按照以上方法既可。

Answer 2

编号后 3 VS 3
就可以知道在哪六个当中
交错称三次
算一算就可以！
并不能直接找出。
问题个关键在于编号和 3 vs 3 称

Answer 3

分2种大情况
先把求分3堆 4个一堆,  A1,A2,A3,A4,   B1,B2,B3,B4, C1,C2,C3,C4
if A堆=B堆 then 
  { A堆或B堆中那2个球 比如 A1,B2}
  if C1,C2 = A1,B2 then 
    if A1 = C3 then 
      C4 假球 
    else
      C3假球
  else
    if A1 = C1 then 
      C2 假球
    else
      C1 假球  
else   //  麻烦了
下面写来

Answer 4

else if A堆>B堆  //这种情况最复杂, 应为 A堆 <> B堆 所以我们要在2次情况下面在8个球
里面判断出假球所以要用  C堆来做参照物
   if A1,A2,B2 = B1,A3,C1 then    //剩余A4,B3,B4 为做比较
     if B3 = B4 then  
        A4假球
     if B3> B4 then    //应为A堆>B堆所以轻的球是B4假球
        B4假球
     else
       B3假球
  if A1,A2,B2 > B1,A3,C1 then   //有嫌疑的球的范围缩小到A1,A2,B1因为
A堆>B堆
  if 
if A1,A2,B2 < B1,A3,C1 then 
   if B2 = A3 then 

Answer 5

上面还没有写完
  if A1,A2,B2 > B1,A3,C1 then   //有嫌疑的球的范围缩小到A1,A2,B1因为
A堆>B堆
   if A1=A2 then   //肯定B1是贾球了
       B1假球
   if A1 > A2 
      A1 假球  //应为A堆 >B堆
   else
     A2 假球 
   if A1,A2,B2,< B1,A3,C3 then  ////有嫌疑的球的范围缩小到B2,A3因为
      A堆>B堆
     if B2< A3 then 
       A3假球
     else
       B2 假球
if A堆<B堆   和A堆> B堆方法一样  //我就不写了
总结:
  A堆 > B堆 以后有8个球有嫌疑 A1,A2,A3,A4, B1,B2,B3,B4
  要在2次搞定着8个球,一定要采用参照物 C堆
  但是如果比较的球都在 1堆中那,那么怎么也没有办法得到答案
  所以用 A1,A2,B2 和 A3,B1,C1 比较
  如果  A1,A2,B2 = A3,B1,C1 则有3个球有嫌疑那就是没有拿来比的球
     A4,B3,B4
  因为A堆 > B堆 所以  用 B3和B4比 
     if B3=B4 then  
       还用讲吗? A4假球
     if B3> B4 还用讲吗? A堆大于B堆  肯定是B4假球了
        B4假球
     else
        B3假球
 if  A1,A2,B2 > A3,B1,C1 then //应为A堆>B堆 所以范围是A1,A2,B2,肯定有假球 
   if A1=A2 then  所以  B2假球肯定为轻的假球,是吗? ^_^
   if A1> A2  then 应为A堆重嘛 所以重的球为假球
   else   还用讲吗?
if A1,A2,B2 < A3,B1,C1 then 那假球就在 B2 A3
为什么呢? 因为B堆轻,如果A3在 左边那么肯定是A1,A2,A3> B1,B2,C1 是吧
所以假球就在 B2,A3 重,还有一次机会你可以在B2, A3中找到 假球.
不要告诉我你不会哦
        
      
       

Answer 6

分成4堆，各3个。A、B、C、D
A和B称，如果相等，则，假球在C和D中（1），否则在A和B中（2），
然后，A和C称，如果相等，则对于（1），假球在D中，对于（2），假球在B；
否则，对于（1），假球在C中，对于（2），假球在A。同时也可以知道假球是轻还是重，第三次称就很简单了。三个球，已知轻重。

Answer 7

zsy_good(只要坚定不移的走下去，那一定会成功) 应该是对的

Answer 8

to ： SQL5560(末日之刃.EXE) 
我的方法是对的.大家不信的话可以提问.我都可以回答出来.

Answer 9

不好意思，没有仔细看leaf_zhy(弄影) 所说的，他的是对的。以前在一个MUD游戏中有这样的一道题，当时好象是16个球

Answer 10

leaf_zhy(弄影)  的方法到处都是漏洞
先来谈一下
球分4堆,3个一堆
A和B称，如果相等，则，假球在C和D中，否则在A和B中，
然后，A和C称，如果相等， 那么D的三个球是假球, 你如何用一次得到假球呢?
A,B,C三堆都是真球,但是现在3个嫌疑的球,如何得到
如果A C 不等, 那么你还有一次办法得到6个嫌疑球中的假球.没有办法!!!

Answer 11

leaf_zhy(弄影) 的方法和我说的一样，但是也不正确。
对于A=B AND A=C的情况，分不出球的轻重，所以也就分不出D中哪个球了。

Answer 12

A堆=B堆,  假球在C,D 中,然后用 A ,C 称, 如果相等
我们想一下,  D现在有3个球,如何得到,
方法1  从 A,B,C  中 取一个 D 取一个, 如果他们相等,  D中还有2个球没有判断,如何得到.
方法1  从 A,B,C  中 取2个 D 取2个, 如果他们相等,  D中还有1个球可以得到
如果他们不等呢, 2个球不等,你已经没有机会了,你不知道那个球是假的同理,下面的那个方法还是同样的错误

Answer 13

哦，是呀，是我疏忽了，leaf_zhy(弄影)有个漏洞，就是三个球中无法知道谁是假的

Answer 14

我的办法你们仔细看看考虑了所有的情况用if else分开了.
没有漏洞.

Answer 15

对于zsy_good(只要坚定不移的走下去，那一定会成功) 的方法，
也有不正确的地方，例如：
if  A1,A2,B2 > A3,B1,C1 then //应为A堆>B堆 所以范围是A1,A2,B2,肯定有假球 
这肯定吗？如果是B1轻呢？

Answer 16

分三堆: A    B    C 各四個.
第一次: 任意兩組,兩种情況:
        重量一樣:

Answer 17

zsy_good的方法我沒有看完，但只要看
先把求分3堆 4个一堆,  A1,A2,A3,A4,   B1,B2,B3,B4, C1,C2,C3,C4
就知道有正確的希望了，哈哈

Answer 18

to ： D_Q(A.Dai)(阿呆) 
题目没有告诉假球是重的,难就难在这里.

Answer 19

重点是要知道假球是较重或是较轻.我的想法和先前差不多:
12 Balls = 3 Groups;
GroupA=[A1,A2,A3,A4];
GroupB=[B1,B2,B3,B4];
GroupC=[C1,C2,C3,C4];Weigh GroupA & GroupB
Case 1: GroupA = GroupB  (Defective Ball in GroupC)
Weigh [C1,C2] & [A1,A2]
  if equal {defective ball in [C3,C4]}
    weigh [C3] & [A1]
      if equal then Defective ball is C4
       else Defective is C3Case 2: GroupA <> GroupB 
        {便要多称一次来决定假球在那堆中}
         Weigh GroupA & GroupC
         if equal then Defective Ball in GroupB
            else Defective Ball in GroupA
         Repeat Case 1  请多指教.

Answer 20

这个题我已经搞定了！
分3堆：
a1,a2,a3,a4
b1,b2,b3,b4
c1,c2,c3,c4①a堆和b堆称，如果相等，假的在c中(用2次很容易找出来，不多说了)，如果不等，则必不在c中。记住a,b中哪堆中，哪堆轻！
②取a1,b2,b3(编号为X)和b1,a2,a3(编号为Y)称，如果相等，必在a4,b4中(很容易找出来)，如果不等，则记住哪一堆中，哪一堆轻！
比较，如果(a比b重)and(X比Y重)or(a比b轻)and(X比Y轻)，那么，假球必在a1,b1中(再称一次也很容易找出来)，如果(a比b重)and(X比Y轻)or(a比b轻)and(X比Y重)，那么假球肯定是X，Y重除了a1,b1的4个球中。
③同2理，再交叉取球很容易就得出答案了（我就不继续说了，大家取试试吧！）
虽然不知道假球轻重，但是，通过前面2次称得的结论，很容易判断了，后面的关键就是在2堆中交叉取球。
楼主，你说对不对？

Answer 21

1 先分成两组a,b，6 v 6称一下。记住哪方重（假设为a重）
2 然后从每组中各拿出3个，交换。如果还是第一步那样的结果(a)，那么肯  定a剩下的那3个球中有一个重的。否则剩下的3个球中有一个轻的（假设为轻）。3将a 中剩下的3个球拿出2个，称第3次，如果相同，剩下的那个，
否则称上的轻的哪个为结果。

Answer 22

zsy_good的方法我沒有看完，但只要看
先把求分3堆 4个一堆,  A1,A2,A3,A4,   B1,B2,B3,B4, C1,C2,C3,C4
就知道有正確的希望了，哈哈

Answer 23

to wanas(wanas) 你知道假球是重还是轻吗?
题目没有告诉,分为2堆
就算A > B 你知道假球在A 还是在B 呵呵/
你还有2次机会可以得到在有嫌疑的12个球中的假球,
你第一次称的方法完全没有作用,你的方法错误在你架设了假球重,用一种方法解决 这是对的
你的方法错误在你架设了假球轻,用一种方法解决 这也是对的
但是在不知道假球重轻的情况下需要使用 ,一种通用的办法解决这个问题.所以你的办法错误.你的办法只局限于知道球的情况下.

Answer 24

to  erickleung() 你的方法只对了一半
最关键,最复杂的 这个错了
Case 2: GroupA <> GroupB 
        {便要多称一次来决定假球在那堆中}
         Weigh GroupA & GroupC  //这里不能用A和C比如果这样
          if equal then Defective Ball in GroupB  //这里你还有一次机会怎么可以得到 4个球中的假球, 你应该看看我的方法,用C的一个做为参照物.
            else Defective Ball in GroupA
         Repeat Case 1  else if A堆>B堆  //这种情况最复杂, 应为 A堆 <> B堆 所以我们要在2次情况下面在8个球里面判断出假球所以要用  C堆来做参照物
   if A1,A2,B2 = B1,A3,C1 then    //剩余A4,B3,B4 为做比较
     if B3 = B4 then  
        A4假球
     if B3> B4 then    //应为A堆>B堆所以轻的球是B4假球
        B4假球
     else
       B3假球
   if A1,A2,B2 > B1,A3,C1 then   //有嫌疑的球的范围缩小到A1,A2,B1因为
     A堆>B堆
   if A1=A2 then   //肯定B1是贾球了
       B1假球
   if A1 > A2 
      A1 假球  //应为A堆 >B堆
   else
     A2 假球 
   if A1,A2,B2,< B1,A3,C3 then  ////有嫌疑的球的范围缩小到B2,A3因为
      A堆>B堆
     if B2< A3 then 
       A3假球
     else
       B2 假球
if A堆<B堆   和A堆> B堆方法一样  //我就不写了

Answer 25

分3堆：A: a1,a2,a3,a4
B: b1,b2,b3,b4
C: c1,c2,c3,c4第一次: 任取兩組(假設B,C):
        1. B = C:   取B或C中任一個(假設c2),取A中任三個(假設a1,a2,a4),組成新組D.
                 第二次: 分D組, c2与a1,a2,a4任一個組成一組(假設a2), if c2 + a2 = a1 + a4 then result := a3
else result := a2;             
                     
        2. B <> C:  
                 第二次:  if A = B then 取A或B中任一個(假設b2),取C中任三個(假設c1,c2,c4),組成新組D
else 取C或A中任一個(假設a2),取B中任三個(假設b1,b2,b4),組成新組D
                 第二次: 同1 第二次:
                             

Answer 26

abcdef六个球
首先拿其中两个球A,B，分别放到天平上，（一步)
如果A,B一样重,那么这两个球排除(A,B不是）
如果A,B不一样重,把其中的A拿下来，从C，D，E，F中任取一个放进去，我取C,如果B,C一样重那么刚才拿下来那个A就是,否则B就是.
 
如果A，B，不是，取C，D到盘上          (二步)
如果C=D那么C，D不是否则C<>D 把C拿下来,从E,F中任拿一个我取E,
如果D=E 那么C是如果D<>E 那么D是.如果A,B,C,D,都不是,那么显然在E,F中,   (三步)
随意从A,B,C,D,中取一个取A,在随意从E,F,中取一个,取E
如果相等,则F是,
如果不等,则E是.
   

Answer 27

哇靠，怎么这么乱。 一个看不清楚。自己写个：     12个分成     4     4      4    选2组比一下 找出不同的一组该组  4个分成     1     1      1      1
                  a     b      c      d 
     选  a  b 比较 
         若相同   
              a  与  c  比     
               相同   就是 d 
               不同   就是 c
         若不同
              a  与  c  比
               相同   就是 b
               不同   就是 a 

Answer 28

不好意思，从头到尾仔细看了一篇。
同意 AirFish(铁甲飞鱼)， 可能真的是无解 。
如果无解的话。那就找一个最优解 ：
    使三次能分出的可能性最大。

Answer 29

to xiamang(瞎忙)  我的方法看了吗?
讲出你看我方法是我的漏洞.

Answer 30

最简单方法
分四堆 A(a1,a2,a3) B(b1,b2,b3) C(c1,c2,c3) D(d1,d2,d3)
第一次:A与B
  1.  A>B (假的重在 A 中,或者假的轻在 B 中)
  2.  A<B (假的重在 B 中,或者假的轻在 A 中)
  3.  A=B ( A 或 B 中的全是真的,假的不知道轻重,但肯定在 C 或 D 中)
第二次:
  1. A与C (不是固定的,但不可以是A与B或C与D)
    (1). A>C (假的重,在 A 中,再一次,从三个球中选出较重的应该没问题吧)
    (2). A=C (假的轻,在 B 中,......)
    (3). A<C (不可能出现的情况.除非他给你球的时候出问题了)
  2. A与C (同 1 一样的道理)
  3. A与C (不固定,但不可以是A与B或C与D)
    (我想结果不用我说了吧)
第三次:
  应该知道了吧

Answer 31

分2种大情况
先把求分3堆 4个一堆,  A1,A2,A3,A4,   B1,B2,B3,B4, C1,C2,C3,C4
if A堆=B堆 then 
  if C1,C2 = A1,B2 then   { A堆或B堆中那2个球 比如 A1,B2}
    if A1 = C3 then 
      C4 假球 
    else
      C3假球
  else
    if A1 = C1 then 
      C2 假球
    else
      C1 假球  
else if A堆>B堆  //这种情况最复杂, 应为 A堆 <> B堆 所以我们要在2次情况下面在8个球里面判断出假球所以要用  C堆来做参照物
   if A1,A2,B2 = B1,A3,C1 then    //剩余A4,B3,B4 为做比较
     if B3 = B4 then  
        A4假球
     if B3> B4 then    //应为A堆>B堆所以轻的球是B4假球
        B4假球
     else
       B3假球
  if A1,A2,B2 > B1,A3,C1 then   //有嫌疑的球的范围缩小到A1,A2,B1因为
A堆>B堆
   if A1=A2 then   //肯定B1是贾球了
       B1假球
   if A1 > A2 
      A1 假球  //应为A堆 >B堆
   else
     A2 假球 
   if A1,A2,B2,< B1,A3,C3 then  ////有嫌疑的球的范围缩小到B2,A3因为
      A堆>B堆
     if B2< A3 then 
       A3假球
     else
       B2 假球
if A堆<B堆   和A堆> B堆方法一样  //我就不写了 

Answer 32

leaf_zhy(弄影)想的一样
不过好像都错了.

Answer 33

to zsy_good(只要坚定不移的走下去，那一定会成功) : 請閣下屈尊看看我的解法:分3堆：A: a1,a2,a3,a4
B: b1,b2,b3,b4
C: c1,c2,c3,c4第一次: 任取兩組(假設B,C):
        1. B = C:   取B或C中任一個(假設c2),取A中任三個(假設a1,a2,a4),組成新組D.
                 第二次: 分D組, c2与a1,a2,a4任一個組成一組(假設a2), if c2 + a2 = a1 + a4 then result := a3
else result := a2;             
                     
        2. B <> C:  
                 第二次:  if A = B then 取A或B中任一個(假設b2),取C中任三個(假設c1,c2,c4),組成新組D
else 取C或A中任一個(假設a2),取B中任三個(假設b1,b2,b4),組成新組D
                 第三次: 同1 第二次:

Answer 34

to  chutian(kiss you) 
第一次取得的2组如果他们重量相同很容易.
关键就是不等于的情况.
你的方法如何在 第2次 A=B时候 你只能确定假球在C中对吗?
那么你还有一次机会怎么从4个球中找出1个假球,切记,一定要在最后一次判断机会
的情况下剩下少于等于3个球,要不没有办法判断
第2次
因该不拿A=B比较,   因该打乱来因为 B<>C 了 你剩下2次机会判断8个球中
的那个假球.
所以你要在没有假秋的里面去一个参照物

Answer 35

to tryibest(编の魂) 
可以得到.怎么没有人认真想想再来看呢,

Answer 36

称球问题——经典智力题推而广之三     　　　　　　 异调
　　　　　　　　说明　　这篇文章试图给出称球问题的一个一般
的和严格的解答。正因为需要做到一般和严
格，就要考虑许多平时遇不到的特别情形，
所以叙述比较繁琐。如果对读者对严格的证
明没有兴趣，可以只阅读介绍问题和约定记
号的第一、第二节，以及第三节末尾27个球
的例子，和第五节13个球和40个球的解法。
事实上所有的技巧都已经表现在这几个例子
里了。　　　　　　　　　　　　一、问题　　称球问题的经典形式是这样的：　　“有十二个外表相同的球，其中有一个坏球，它的重量和其它十
一个有轻微的（但是可以测量出来的）差别。现在有一架没有砝码的
很灵敏的天平，问如何称三次就保证找出那个坏球，并知道它比标准
球重还是轻。”　　这可能是网上被做过次数最多的一道智力题了。它的一种解法如
下：将十二个球编号为1-12。第一次，先将1-4号放在左边，5-8号放在右边。
　　1.如果右重则坏球在1-8号。
　　　　第二次将2-4号拿掉，将6-8号从右边移到左边，把9-11号放
　　　　在右边。就是说，把1,6,7,8放在左边，5,9,10,11放在右边。
　　　　　　1.如果右重则坏球在没有被触动的1,5号。如果是1号，
　　　　　　　则它比标准球轻；如果是5号，则它比标准球重。
　　　　　　　　第三次将1号放在左边，2号放在右边。
　　　　　　　　　　1.如果右重则1号是坏球且比标准球轻；
　　　　　　　　　　2.如果平衡则5号是坏球且比标准球重；
　　　　　　　　　　3.这次不可能左重。
　　　　　　2.如果平衡则坏球在被拿掉的2-4号，且比标准球轻。
　　　　　　　　第三次将2号放在左边，3号放在右边。
　　　　　　　　　　1.如果右重则2号是坏球且比标准球轻；
　　　　　　　　　　2.如果平衡则4号是坏球且比标准球轻；
　　　　　　　　　　3.如果左重则3号是坏球且比标准球轻。
　　　　　　3.如果左重则坏球在拿到左边的6-8号，且比标准球重。
　　　　　　　　第三次将6号放在左边，7号放在右边。
　　　　　　　　　　1.如果右重则7号是坏球且比标准球重；
　　　　　　　　　　2.如果平衡则8号是坏球且比标准球重；
　　　　　　　　　　3.如果左重则6号是坏球且比标准球重。
　　2.如果天平平衡，则坏球在9-12号。
　　　　第二次将1-3号放在左边，9-11号放在右边。
　　　　　　1.如果右重则坏球在9-11号且坏球较重。
　　　　　　　　第三次将9号放在左边，10号放在右边。
　　　　　　　　　　1.如果右重则10号是坏球且比标准球重；
　　　　　　　　　　2.如果平衡则11号是坏球且比标准球重；
　　　　　　　　　　3.如果左重则9号是坏球且比标准球重。
　　　　　　2.如果平衡则坏球为12号。
　　　　　　　　第三次将1号放在左边，12号放在右边。
　　　　　　　　　　1.如果右重则12号是坏球且比标准球重；
　　　　　　　　　　2.这次不可能平衡；
　　　　　　　　　　3.如果左重则12号是坏球且比标准球轻。
　　　　　　3.如果左重则坏球在9-11号且坏球较轻。
　　　　　　　　第三次将9号放在左边，10号放在右边。
　　　　　　　　　　1.如果右重则9号是坏球且比标准球轻；
　　　　　　　　　　2.如果平衡则11号是坏球且比标准球轻；
　　　　　　　　　　3.如果左重则10号是坏球且比标准球轻。
　　3.如果左重则坏球在1-8号。
　　　　第二次将2-4号拿掉，将6-8号从右边移到左边，把9-11号放
　　　　在右边。就是说，把1,6,7,8放在左边，5,9,10,11放在右边。
　　　　　　1.如果右重则坏球在拿到左边的6-8号，且比标准球轻。
　　　　　　　　第三次将6号放在左边，7号放在右边。
　　　　　　　　　　1.如果右重则6号是坏球且比标准球轻；
　　　　　　　　　　2.如果平衡则8号是坏球且比标准球轻；
　　　　　　　　　　3.如果左重则7号是坏球且比标准球轻。
　　　　　　2.如果平衡则坏球在被拿掉的2-4号，且比标准球重。
　　　　　　　　第三次将2号放在左边，3号放在右边。
　　　　　　　　　　1.如果右重则3号是坏球且比标准球重；
　　　　　　　　　　2.如果平衡则4号是坏球且比标准球重；
　　　　　　　　　　3.如果左重则2号是坏球且比标准球重。
　　　　　　3.如果左重则坏球在没有被触动的1,5号。如果是1号，
　　　　　　　则它比标准球重；如果是5号，则它比标准球轻。
　　　　　　　　第三次将1号放在左边，2号放在右边。
　　　　　　　　　　1.这次不可能右重。
　　　　　　　　　　2.如果平衡则5号是坏球且比标准球轻；
　　　　　　　　　　3.如果左重则1号是坏球且比标准球重；　　够麻烦的吧。其实里面有许多情况是对称的，比如第一次称时的
右重和右轻，只需考虑一种就可以了，另一种完全可以比照执行。我
把整个过程写下来，只是想 呕 吓唬大家。　　稍微试一下，就可以知道只称两次是不可能保证找到坏球的。如
果给的是十三个球，以上的解法也基本有效，只是要有个小小的改动，
就是在这种情况下，在第一第二次都平衡的时候，第三次还是有可能
平衡（就是上面的第2.2.2步），那么我们可以肯定坏球是13号球，可
是我们没法知道它到底是比标准球轻，还是比标准球重。如果给的是
十四个球，我们会发现无论如何也不可能只称三次，就保证找出坏球。　　一个自然而然的问题就是：对于给定的自然数N，我们怎么来解有
N个球的称球问题？　　在下面的讨论中，给定任一自然数N，我们要解决以下问题：
⑴找出N球称球问题所需的最小次数，并证明以上所给的最小次数的确
　是最小的；
⑵给出最小次数称球的具体方法；
⑶如果只要求找出坏球而不要求知道坏球的轻重，对N球称球问题解决
　以上两个问题；　　还有一个我们并不是那么感兴趣，但是作为副产品的问题是：
⑷如果除了所给的N个球外，另外还给一标准球，解决以上三个问题。

Answer 37

其实这道题不难，做法大概是：
　　分成三堆，就称A、B、C吧,每堆四个球(1、2、3、4）
然后就称其中的两堆（不妨设称A与B)，如果A与B重相同，坏球在C，问题很简单了，不说。(用了一次天平）
　　如果A的重量不同，不妨设A的重量小于B的重量，记为A<B，（坏球可能在A和B两堆之中的任何一堆）。
　　在这里，我们得到一个重要的结论，如果坏球的重量小于其它的球，则球在A1、A2、A3、A4之中，相反，则在B1、B2、B3、B4之中。
   接下来，求角的过程很长，我说个大概吧：将球重新分为三堆大概是
A:A1、B2、C1、B4，　B：B1、A2、C2、C3，　C：C1、A3、A4、B3　　称A与B，如果A＝B，则坏球在A3,A4和B3，如果A＜B，则坏球在A1，B1，如果A＞B，则球A2、B2、B4。（用两次天平)
　　下来的方法联系第一次天平的结论，用一次天平完全可以分出那一个是坏球。不说了。

Answer 38

tryibest 说的那么详细了还有必要猜嘛！！