12个球中找坏球

在12个球，称三次，找出一个坏球，并判断轻重 现在把12个球随机分成3组: A[a1,a2,a3,a4],B[b1,b2,b3,b4],C[c1,c2,c3,c4] 对A组与B组进行秤重 Case1:Weight(A)=Weight(B) 说明有问题的球在C组,同时说明A,B组中的球是ok的。 现在取C组中的三个球组成D组，与A,B组中取三个正常球组成E组进行比较 if Weight(D) = Weight(E) { 说明D-C(C组剩下的那个球)是异常球， 拿一个正常球与它秤一下就知道是轻球还是重球 } else if(Weight(D) > Weight(E){ 说明异常球在D组中且是个重球 取D组中的两个球进行比较，结果出来了 } else if (Weight(D) < Weight(E){ 说明异常球在D组中且是个轻球 取D组中的两个球进行比较，结果出来了 } Case2:Weight(A) > Weight(B) 取B中的两个球+A中的一个球组成D组，即D[b1,b2,a1] 用D组(3个球)与B'组(B中剩下的两个球+一个正常球)进行比较，即B'[b2,b3,c1] (一定要是与B'组比，因为它包含了B组中剩下的两个球) if Weight(D) = Weight(B'){ 说明B',D组中的球都是正常的，同时原来的B组全是正常球 根据第一次秤Weight(A) > Weight(B)，说明不正常的的球在 A组剩下来的3个球中(a2，a3，a4)而且是重球 从(a2，a3，a4)取出两个球秤一下，结果出来了 } else if Weight(D) > Weight(B'){ D组： B中两个球+A中一个球，D[b1,b2,a1] B'组： B中两个球+一个正常球，B'[b2,b3,c1] Weight(A) > Weight(B) Weight(D) > Weight(B') 因为Weight(A) > Weight(B), 所以如果A中如果有问题球，只可能是重球；B中有问题球只能是轻球。 Weight(D) > Weight(B') 说明问题球就在D,B'组中 由于B中只能是轻球，所以D组中的那两个B组的球是正常球 如果有问题的球是轻球，那么它就在B'组中的B的两个球 如果有问题的球是重球，那么它一定就是D组中的那个A中的球，即a1 把B'组中的两个球(b2,b3)秤一下， 如果一样，说明问题球是D组中的A中的球，即a1，且是重球 如果重量不一样，轻的那个就是问题球，且是轻球 } else if Weight(D) < Weight(B'){ D组：B中两个球+A中一个球，D[b1,b2,a1] B'组：B中两个球+一个正常球，B'[b2,b3,c1] Weight(A) > Weight(B) Weight(D) < Weight(B') 因为Weight(A) > Weight(B), 所以如果A中如果有问题球，只可能是重球；B中有问题球只能是轻球。 因为Weight(D) < Weight(B') , 说明重量不一样不是因为D组中的A球的问题， 而是D组中的B中的两个球有问题，且问题球是轻球问题 把D组中的B中的两个球秤一下，结果就出来了 } Case3:Weight(A) < Weight(B) { 同Case2 } ： 　 　天平称重，有两个托盘比较轻重，加上托盘外面，也就是每次称重有3个结果，就是ln3/ln2比特信息。n个球要知道其中一个不同的球，如果知道那个不 同重量的球是轻还是重，找出来的话那就是n个结果中的一种，就是有ln（n）/ln2比特信息，如果不知道轻重，找出来就是2n（n个球中的一个，轻或者 重，所以是2n）个结果中的一种，那就是ln（2n）/ln2比特信息。 　　假设我们要称k次，根据信息理论，那显然两种情况就分别有： 　　（1）k*ln3/ln2>=ln（n）/ln2　（k>=1）　解得k>=ln（n）/ln3 　　（2）k*ln3/ln2>=ln（2n）/ln2　（k>1）　解得k>=ln（2n）/ln3 　　这是得到下限，可以很轻易证明满足条件的最小正整数k就是所求。比如称3次知道轻重可以从3^3=27个球中找出不同的球出来，如果不知道轻重就只能从（3^3-1）/2=13个球中找出不同的球出来。 ********* 核心: 替换 abcd efgh ijki 当abcd>efgh时，用fgh替换bcd,用ijk替换fgh，即变成 afgh VS eijk ********* ********* 下面从信息论的角度，更具一般性：http://ww123.net/baby/viewthread.php?tid=21839 分别为a b c d, e f g h, i j k l，取出abcd, efgh 第一种情形： 如果重量相等，则说明所求在 ijkl 中， 称量 i j ， 如果相等，比较 a k ，如果a=k，则所求为 l（但不知轻重）；如果ak不等，则所求为 k 。如果不等，比较 a i ，如果a=i，则所求为 j ；如果不等，则所求为 i 。 第二种： 如果 abcd 轻， 在efgh中取出 fgh ，替掉abcd中 bcd，从ijkl中取出 ijk 个放入 e 中填补空位： 如果afgh轻：则说明所求在a或e，拿 e 和除 a 以外的任意一球比较，如果重量相等，则所求的球是 a ；如果不等，则所求的球是 e 。 如果afgh重：说明所求在 fgh 中，且所求较重；比较 f g ，等重则所求为 h ；不等则重的为所求。 如果一样重：说明所求在 bcd 中，且所求较轻；以下同afgh重的情形。 第三种： 如果 abcd 重， 在efgh中取出 fgh ，替掉abcd中 bcd，从ijkl中取出 ijk 个放入 e 中填补空位： 如果 afgh 重：则说明所求在a或e，拿 e 和除 a 以外的任意一球比较，如果重量相等，则所求的球是 a ；如果不等，则所求的球是 e 。 如果afgh轻：说明所求在 fgh 中，且所求较轻；比较 f g ，等重则所求为 h ；不等则重的为所求。 如果一样重：说明所求在 bcd 中，且所求较重；以下同afgh轻的情形。