看错了，我看成18个球了
M
N#\P1
k6$.pCH 6 ----------------------------------------------
d^,u"Z9P 下边是别人写的公式
&L;0%
yQ h":"$k 例如题：现有n个外观一样的小球，其中有一个小球的重量与众不同（不知其轻重或者说知道轻或者重），请问最少
$My%7S/3 称多少次一定可以将这个不同的球找出。
0<fN<iR`
YQ; ?N66 天平称重，有两个托盘比较轻重，加上托盘外面，也就是每次称重有3个结果，就是ln3/ln2比特信息。n个球要知道
6 fL=2a 其中一个不同的球，如果知道那个不同重量的球是轻还是重，找出来的话那就是n个结果中的一种，就是有ln(n)/ln2比特
} c^ `!9 信息，如果不知道轻重，找出来就是2n（n个球中的一个，轻或者重，所以是2n）个结果中的一种，那就是ln(2n)/ln2
p m@Mlwg`1 比特信息。
]h
aZ T\ 假设我们要称k次，根据信息理论，那显然两种情况就分别有：
t*iKkV^aE （1）k*ln3/ln2>=ln(n)/ln2,解得k>=ln(n)/ln3
r ".*l?= （2）k*ln3/ln2>=ln(2n)/ln2(k>1)解得k>=ln(2n)/ln3
iP)`yB5 ` 这是得到下限，可以很轻易证明满足条件的最小正整数k就是所求。比如称3次知道轻重可以从3^3=27个球中找出不
\QGh@AQp" 同的球出来，如果不知道轻重就只能从（3^3-1)/2=13个球中找出不同的球出来。
C8W#$ a 具体称法就不说了，其实真的理解了信息论里面的那不等式的等式成立条件就知道称法了，也就是要保证每次称的
&{-r 5d23 信息含量ln3/ln2。可以看看相关的一个帖子：
http://dell1.cn99.com/thbbs/GreatTurn.AIX/00000042.htm。
L 7VD ZCV BBS水木清华站∶精华区
+ N n
$ 发信人:idle(回归线),信区:GreatTurn
uGt}H n 标题:称小球问题终结----m次称出(3^m-1)/2个球的解法
", O |uL 发信站:BBS水木清华站(SatJul2509:10:511998)
!:Z
lVIA 对于N(m)=(3^m-1)/2个小球，现在我们来寻求m次的解法。
X} {z7[ 首先，对于m=2的情况，相当于四个小球来称两次的情况，这个已经讨论过多次了，也很
b'r</n
cZ 简单，在此略去
=
y @*vl 其次，若m<=k-1时，假定对于N(k-1)=(3^(k-1)-1)/2个球的情况我们都有解法。
w :nYsuF 现在来考虑m=k的情况。
.q90+9Ek= 第一次称取[3^(k-1)-1]个球放在天平天平两端，则：
p~'iK4[&6 如果平衡，获得[3^(k-1)-1]个标准球，坏球在剩下的[3^(k-1)+1]/2个中。由于
zEVQ[y6BcM [3^(k-1)-1]>=[3^(k-1)+1]/2，（k>=2),即已知的标准球数不小于未知球数?nbsp;
g ?.y7!m 所以在以后的测量中就相当于任意给定标准球的情况，由前面的引理二可知
ObPXVqG"? 对于[3^(k-1)+1]/2的情况(k-1)次可解。
a `e'HQ 如果不平衡，大的那方记做A,小的那方记作B。标准球记做C.
@
D,]v: 则现在我们有[3^(k-1)-1]/2个A球和B球，有[3^(k-1)+1]/2个C球。
Ct][B{ 第二次用3^(k-2)个A球加[3^(k-2)-1]/2个B球放左边?nbsp;
nR]*RIp5 3^(k-2)个C球加[3^(k-2)-1]/2个A球放右边。
pwH*&YU 如果左边大于右边，则说明是在左边的3^(k-2)个A球中质量大的为坏球；
})+iAxR 如果左边等于右边，则说明是在第二次称时没用的3^(k-2)个B球中质量轻
SBy{sbx4&F 的为坏球。以上两种情况都可以再用三分法(k-2)次解决，加上前两
7Ll? #eun 次共k次解决。
**$kW bS 如果左边小于右边，则坏球在左边的[3^(k-2)-1]/2个B球中或在右边的同样
IgjP y5k 数目的A球中。此时的情况和第二次开始时类似（只不过是k-1变成k-2).
#zv&h`gY 用相同的办法一直往下追溯到一个A球和一个B球一次区分的情况，这时
h<V,0sZ&: 只需拿A球和标准球比较以下就行了。
6 .9C 4 因此在这种情况下也是可以最终用k次解决的。
3ZC@q
#R
A 由以上两步加上数学归纳法知，对于N(m)=(3^m-1)/2的情况，称m次是可以称出来的。
n
rA 4N1 由这个解法加上前面所给出的上界Nmax(m)<=(3^m-1)/2，知称m次能解决的最大的小球数
C =CZtjUt Nmax(m)=(3^m-1)/2。
>0[:uu,'> 有兴趣的人可以验证一下m=3,N=13的情况----该情况已经被反复拿出来讨论过了。
A9g/At_
HY eCq9S
+=Q:g,kP
QQ帐号登录
内容互通，快速登录
微博帐号登录
淘宝帐号登录
