称球问题一般解法.doc

《称球问题一般解法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、称球问题一般会有以下3种变形：1、n个球，其中有一个坏的，知道是轻还是重，用天平称出坏球来。2、n个球，其中有一个坏的，不知是轻还是重，用天平称出坏球来。3、n个球，其中有一个坏的，不知是轻还是重，用天平称出坏球来，并告知坏球是轻还是重。对于上面3种情况，称量n次，最多可以在几个球中找出坏球来？答案：分别为：3^n,(3^n-1)/2,(3^n-3)/2.称法体现在下面的证明中：一、天平称重，有两个托盘比较轻重，加上托盘外面，也就是每次称重有3个结果，就是ln3/ln2比特信息。n个球要知道其中一个不同的球，如果

2、知道那个不同重量的球是轻还是重，找出来的话那就是n个结果中的一种，就是有ln(n)/ln2比特信息，假设我们要称k次，根据信息理论：k*ln3/ln2>=ln(n)/ln2,解得k>=ln(n)/ln3这是得到下限，可以很轻易证明满足条件的最小正整数k就是所求。比如称3次知道轻重可以从3^3=27个球中找出不同的球出来。具体称法就是：每次再待定的n个球中取[(n+2)/3]个球，放在天平左边；[(n+2)/3]个球放在天平右边。（注：[x]表示不大于x的最大整数。）二、对于N(m)=(3^m-1)/2个小球，现在

3、我们来寻求m次的解法。首先，对于m=2的情况，相当于四个小球来称两次的情况，这个已经讨论过多次了，也很简单，在此略去其次，若m<=k-1时，假定对于N(k-1)=(3^(k-1)-1)/2个球的情况我们都有解法。现在来考虑m=k的情况。第一次称取[3^(k-1)-1]个球放在天平天平两端，则：如果平衡，获得[3^(k-1)-1]个标准球，坏球在剩下的[3^(k-1)+1]/2个中。由于[3^(k-1)-1]>=[3^(k-1)+1]/2，（k>=2),即已知的标准球数不小于未知球数;所以在以后的测量中就相当于任意

4、给定标准球的情况，由前面的引理二可知对于[3^(k-1)+1]/2的情况(k-1)次可解。如果不平衡，大的那方记做A,小的那方记作B。标准球记做C.则现在我们有[3^(k-1)-1]/2个A球和B球，有[3^(k-1)+1]/2个C球。第二次用3^(k-2)个A球加[3^(k-2)-1]/2个B球放左边;3^(k-2)个C球加[3^(k-2)-1]/2个A球放右边。如果左边大于右边，则说明是在左边的3^(k-2)个A球中质量大的为坏球；如果左边等于右边，则说明是在第二次称时没用的3^(k-2)个B球中质量轻的为坏

5、球。以上两种情况都可以再用三分法(k-2)次解决，加上前两次共k次解决。如果左边小于右边，则坏球在左边的[3^(k-2)-1]/2个B球中或在右边的同样数目的A球中。此时的情况和第二次开始时类似（只不过是k-1变成k-2).用相同的办法一直往下追溯到一个A球和一个B球一次区分的情况，这时只需拿A球和标准球比较以下就行了。因此在这种情况下也是可以最终用k次解决的。由以上两步加上数学归纳法知，对于N(m)=(3^m-1)/2的情况，称m次是可以称出来的。由这个解法加上前面所给出的上界Nmax(m)<=(3^m-1)/

6、2，知称m次能解决的最大的小球数Nmax(m)=(3^m-1)/2。有兴趣的人可以验证一下m=3,N=13的情况----该情况已经被反复拿出来讨论过了。--------------------------------------------------------------------大家好，我们来继续昨天的问题。现在我要给出通解啦。为了简化下面的过程，我们假设小球的个数正好是(3t-3)/2。首先我们把小球分成数量相等的三组A1～An

7、B1～Bn

8、C1～Cn，其中n=(3t-1-1)/2。第一次使用天平的时候

9、，不妨把A组和B组分别放在天平左右盘。如果天平左低右高，那么有可能因为左边n个小球之一较重，也可能因为右边n个小球之一较轻。反过来也是一样。这种时候，转到下面的情况(1)处理。而天平平衡的时候，则坏球一定在剩下n个小球中，(2)讨论了这种问题。【情况1】这时的条件是：已知A1～An中一个球较重，或者B1～Bn中一个球较轻，其中n=(3t-1-1)/2。我们把可以在C中任意拿出一个好球（C中的都是好球嘛）放到B中去。然后由情况(3)讨论接下来的处理方法。【情况2】这时的条件是：已知坏球C1～Cn中，且不知轻重关系，

10、其中n=(3t-1-1)/2。我们把C分作三组a1～am

11、b1～bm

12、c1～cm+1，其中m=(3t-2-1)/2。注意看啦，c组要比a，b两组多出一个。怎么？我们昨天不是说这种情况没办法完成吗？但是，我们现在多了一项武器－－好球。对，我们可以从已经判断为一定是好球的A，B组中任意拿出一个好球，和a一起放到天平左盘，把c组放到天平右盘，如果天平左低右高，那么一定是a组中m