[猫] N <= (3的K次方 - 1) /2

Question

以前csdn上面看到一个问题：有13个球，其中有1个球和其他12个球不一样，可能重，也可能轻。
给你一个天平，最少要称几次才能把那个异常球取出来。记得当时有很多的争论。
昨天看了《程序员》2006合订本。有位老兄给了个公式N <= (3的K次方 - 1) /2
N为小球的数量， k为称得次数。
由此推论 k = 3 正好满足条件。推理方法还算精密，有兴趣可以看看，挺有意思的。

Answer 1

TO:shan1119(大天使) 
假设给四个球编号ABCD
取AB先称 如果平衡说明CD中有一个不一样，取AC称，如果平衡，说明不一样是D，不平衡是C
         如果不平衡说明AB有一个不一样，取AC称，如果平衡，说明不一样是B，不平衡是A

Answer 2

shan1119(大天使) ( ) 信誉：101    Blog 照你这么说4个球称两次可以得出结果，怎么称啊，没想出来。
======================================ABCD分成3组。
第一组A
第二组B
第三组CD
如果A ！= B 很简单。
如果A == B 则 从 CD 中拿出一个到 第二组， 原来第二组的拿到第一组，原来第一组的拿出来。
又构成3组。
。
我是看懂了，描述起来比较困难。
《程序员》 2006 合订本 下册 有讲解的，很不错

Answer 3

如果A == B,怎么判断C,D中哪个轻，或重？你们说的只能找出来，但不能确定轻重啊

Answer 4

靠，我那天只在想13个球，4个球的case竟然出bug了。shan1119(大天使) ( ) 信誉：101    Blog 我再理理思路哦

Answer 5

汗~
abcd四球：
a----------b
if(平衡){
a----------c
if(平衡){
得d
}else{
得c
}
}else{
a----------c
if(平衡){
得b
}else{
得a
}
}

Answer 6

myzee(曾经是 zh-cn) ( ) 信誉：100    Blog ====================关键要知道 异常那个球是轻了还是重了。