过年前的讨论2！关于天平称球问题的统一解法!
前段时间有几个帖子都是关于天平称球问题的，我也从中学习了不少。
有个哥们提出，可以用信息论解这类的题，可以求出次数的范围，
我按照他们给的方法算了一些小的模型，发现确实如此。
以比较有名的12彩球问题为例，天平有3种状态，因此每次可以获得信息为log3 bit,
12个彩球，由于不知其轻重，因此共12*2 = 24种状态，
2 < log24 / log3 < 3 因此3次可以搞定。并且可以推出3次最多可以称13个球。
用这种方法还可以推算出，假如存在2个坏球(两个坏球质量相同)，那么总共C(12,2) * 2 = 132种状态
因为4 < log132 / log3 < 5，那么只需要5次就能称出，也可以推出5次最多可以从16个球中挑出2个坏球。
到了这里，问题来了，别人会跟我说，5次不可能，除非你告诉我怎么称，我虽然会算次数，但称的过程却说不出来。
如果用程序，应该怎么做呢？我也没什么好的思路，用穷举法，规模太大了......该咋办呢？
[解决办法]
请查看链接：http://bbs.fudan.edu.cn/cgi-bin/bbs/bbs0an?path=/groups/sci.faq/Mathematics/Problems/prob/weightball
这里给出了普通情况的结论
[解决办法]
首先,从信息论得到的结果只是一个下限,4 < log132 / log3 < 5并不一定表示5次肯定能称出来,只是说明4次肯定称不出来.
其次编程的话,感觉最优解只能靠穷举.
不要求最优的话,可以用贪婪算法, 目标是每次称球得到的信息最多.
[解决办法]
称球问题一般会有以下3种变形：
1、n个球，其中有一个坏的，知道是轻还是重，用天平称出坏球来。
2、n个球，其中有一个坏的，不知是轻还是重，用天平称出坏球来。
3、n个球，其中有一个坏的，不知是轻还是重，用天平称出坏球来，并告知坏球是轻还是重。
对于上面3种情况，称量n次，最多可以在几个球中找出坏球来？
答案：分别为：3^n, (3^n - 1)/2, (3^n - 3)/2.
称法体现在下面的证明中：
一、
天平称重，有两个托盘比较轻重，加上托盘外面，也就是每次称重有3个结果，就是ln3/ln2比特信息。n个球要知道其中一个不同的球，如果知道那个不同重量的球是轻还是重，找出来的话那就是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个小球，现在我们来寻求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),即已知的标准球数不小于未知球数;
所以在以后的测量中就相当于任意给定标准球的情况，由前面的引理二可知
对于[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球中质量轻
的为坏球。以上两种情况都可以再用三分法(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)/2，知称m次能解决的最大的小球数
Nmax(m)=(3^m-1)/2。
有兴趣的人可以验证一下m=3,N=13的情况----该情况已经被反复拿出来讨论过了。
[解决办法]
LZ这个想法不就是信息论么?
3进制
k*ln3/ln3>=ln(2n+1)/ln3
没仔细看,上界原来从这里来的
按照3,4楼贴出来的方法是通用的
[解决办法]
mark，期待好的思路。
[解决办法]
学习！
[解决办法]
不知道诶
[解决办法]
Mark!
------解决方案--------------------
up
[解决办法]
up
[解决办法]
很好很强大
[解决办法]
学习了
[解决办法]
学习下
[解决办法]
路过，看看
[解决办法]
12个球, 其中一个是次品, 一架标准天平, 称3次指出哪个是次品球, 重了还是轻了?
方法很简单：
第一次：两边个六个，留下轻的那边的六个。
第二次：两边个三个，留下轻的那边的三个。
第三次：任意放两个上去，如果天平平衡则说明次品没在天平上。如果天平不平衡，则说明次品在轻的一端。
[解决办法]
学习了！谢谢
[解决办法]
