我这里有一个pascal版本的，是以前做的，思路和上面tleon说的一样,我想也许可以给你做个参考。这是做50块银币的找假币问题 program weigh(input,output); var n:integer; function max(c:integer;d:integer):integer; begin if c>=d then max:=c else max:=d; end; function b(n:integer):integer; var i,t,k,xiao,a,c:integer; da:array[1..50] of integer; begin xiao:=6000; for i:=1 to n do da[i]:=0; if (n=0) or (n=1) then b:=0 else if (n=2) or (n=3) then b:=1 else begin t:=n div 2; for k:=1 to t do begin a:=b(n-2*k); c:=b(k); if (da[k]<max(a,c)) then da[k]:=max(a,c); end; for k:=1 to t do if xiao>da[k] then xiao:=da[k]; b:=1+xiao; end; end; begin writeln('please input n:'); read(n); writeln('need weight times:'); writeln(b(n)) end.
标 题: 称小球问题终结----问题的提出 zxl (转寄) (转载)
发信站: BBS 水木清华站 (Fri Mar 29 14:19:19 2002)
来 源: 166.111.83.92
【 以下文字转载自 coolfa 的信箱 】
发信人: idle (回归线), 信区: GreatTurn
标 题: 称小球问题终结----问题的提出
发信站: BBS 水木清华站 (Sat Jul 25 07:34:32 1998)
关于称小球问题，一般是这样的：
有N个小球外形无区别，但是有一个在质量上与其他的球不一样。用天平称最少m次一定将
不同的球找出来。显然随N增大，m不会减小。现在想解决的问题是对于任何给定的次数m,
找出在该次数下能解决的最大的N值,用Nmax来表示。并给出对应于(Nmax,m)的一种解法。
--
玉石 堂 昧，那 靶 悔多。终无咎，笑呵呵。
※ 修改:·idle 於 Jul 25 16:22:48 修改本文·[FROM: 162.105.160.126]
※ 来源:·BBS 水木清华站 bbs.net.tsinghua.edu.cn·[FROM: 162.105.160.126]
寄信人: coolfa (CE工人)
标 题: 称小球问题终结----关于所能解决的上限 zxl (转寄) (转载)
发信站: BBS 水木清华站 (Fri Mar 29 14:19:40 2002)
来 源: 166.111.83.92
【 以下文字转载自 coolfa 的信箱 】
发信人: idle (回归线), 信区: GreatTurn
标 题: 称小球问题终结----关于所能解决的上限
发信站: BBS 水木清华站 (Sat Jul 25 08:29:09 1998)
现在来求m次所能解决的上限Nmax(m)问题。
为解决这个问题，我们给出几个引理。
引理一：无论加上什么其他的附加条件，只要k个球中的任一个都有可能是坏球（概率不
为0），则当k>3^L时，称L次是称不出来的。这里的附加条件包括已知坏球是否重于好球,
除k个未知球外还提供若干个标准球，以及k个球中某些的质量和大于另外一些的和等等，
只要在这些条件下k个球中的任一个都还有可能是坏球就可以是引理所说的附加条件。
证明：很显然，若k>3^L，则哪个球是坏球一共有k中情况，而称L次一共有3^L种情况，
由k>3^L知不可能一定分辨出哪个球是坏球。
引理二：如果另外在提供任意多个标准球（即在N个未知球外还任给标准球作"砝码"用）?
则称m次最多能从N1max(m)=(3^m+1)/2个球中找出坏球来。
证明：对该引理的证明可以采用数学归纳法。
当m=1时，显然若只有两个球，则任挑一个与另外的标准球比较（额外提供的，不是
两个中的），若相等则是剩下那一个，若不等则是这一个。所以N1max(1)>=2。
而对于三个球的情况，如果第一次称用了两个或三个未知球，则无法判断出用
过的球中谁是坏球（只称一次），而如果第一次称只用了一个未知球，则剩下
的两个球无法区分。因此一次不能解决三个球的问题。所以N1max(1)<3。
由N1max(1)<3和N1max(1)>=2知，N1max=2。
设当m<=k-1时命题都成立，则考虑m=k的情况。
第一次称不能使用超过3^(k-1)个未知球，否则如果坏球在这超过3^(k-1)个
球中的话，由引理一，在剩下的(k-1)次中不能肯定找出这个坏球来?
另外，若第一次称碰到的都是好球，则第一次称后的结果就是多提供了一些
标准球（这个结果对已经提供了任意个标准球的情况是毫无意义的）和缩小
坏球的范围到剩下的球中。由归纳假设，剩下的球的数目不超过N1max(k-1)
才能保证一定能称出来。所以：N1max(k)<=3^(k-1)+N1max(k-1)=(3^k+1)/2。
如果有(3^k+1)/2个未知球，则第一次将3^(k-1)个未知球和提供的3^(k-1)个
未知球比较：如果相等，则坏球在剩下的N1max(k-1)个中，由归纳假设能分
出来；如果不等，则坏球在这3^(k-1)个中，但是同时知道了坏球是轻还是
重，由三分法可以很容易用k-1次找出来。所以对于(3^k+1)/2个未知球的情
况，是能够用k次找出坏球来的。即N1max(k)>=(3^k+1)/2.
由前面的推导知，N1max(k)=(3^k+1)/2。所以m=k时命题也成立。
由数学归纳法,所以N1max(k)=(3^k+1)/2对所有的自然数k都成立。
引理二得证。
引理三：Nmax(m)<=(3^m-1)/2。(m>=2)
证明：在原来的称小球问题中，起初没有提供标准球，所以第一次称的数目必须是偶数，
由和引理二中推导N1max(m)时类似，有如下结论：
Nmax(m)<=N1max(m-1) + [3^(m-1)-1]
^^^^^^^^^^ ^^^^^^^^^^^
若第一次称平衡了最多剩下的球数 第一次称最多使用的球数，必须是偶数
所以Nmax(m)<=(3^m-1)/2=N1max(m)-1。命题得证。
到此为止，我们求出了称小球问题的一个上界Nmax(m)<=(3^m-1)/2。（m>=2)
在后面我们将证明这是一个上确界，即Nmax(m)=(3^m-1)/2。
对于m=1的情况，由于必须有两个以上球（否则无所谓好坏球），所以一次是怎么也称不
出来的，因此我们不讨论m=1的情况。
--
玉石 堂 昧，那 靶 悔多。终无咎，笑呵呵。
寄信人: coolfa (CE工人)
标 题: 称小球问题终结----m次称出(3^m-1)/2个球 zxl (转寄) (转载)
发信站: BBS 水木清华站 (Fri Mar 29 14:19:46 2002)
来 源: 166.111.83.92
【 以下文字转载自 coolfa 的信箱 】
发信人: idle (回归线), 信区: GreatTurn
标 题: 称小球问题终结----m次称出(3^m-1)/2个球的解法
发信站: BBS 水木清华站 (Sat Jul 25 09:10:51 1998)
对于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的情况----该情况已经被反复拿出来讨论过了。
--
玉石 堂 昧，那 靶 悔多。终无咎，笑呵呵。
寄信人: coolfa (CE工人)
标 题: 称小球问题终结----如果要求小球轻重必须 zxl (转寄) (转载)
发信站: BBS 水木清华站 (Fri Mar 29 14:19:52 2002)
来 源: 166.111.83.92
【 以下文字转载自 coolfa 的信箱 】
发信人: idle (回归线), 信区: GreatTurn
标 题: 称小球问题终结----如果要求小球轻重必须判决
发信站: BBS 水木清华站 (Sun Jul 26 18:52:10 1998)
与前面的不需判轻重的情况类似的定义和推导，可得：
Nmax(k)=(3^k-3)/2.
N1max(k)=(3^k-1)/2.
意外的发现只比前面不分轻重的情况分别小一！！！
证明过程由于有太多类似，故在此略去，仅举一个例子来说明。
k=3,Nmax=12
共12个球
第一次： 4A ? 4B 剩下4C
如果相等，则A和B都是标准球。
第二次 C1+A ? C2+C3
如果相等，则坏球为C3，再用C3与标准球比较一次即可。
如果不等，再比较C2和C3，可以这两次结果判断C1,C2,C3中哪个是坏球和轻重。 如果不等，不妨设4A>4B.此时C球都是标准球。
第二次 A1+B2+B3+B4 ? B1+C1+C2+C3
如果相等，则坏球在A2,A3,A4中，且重。再比较A2和A3即知。
如果左边小于右边，则在B2,B3,B4中且轻。再比较B2和B3即可。
如果左边大于右边，则是A1且重或是B1且轻 ，再拿A1和标准球即可。
--
玉石 堂 昧，那 靶 悔多。终无咎，笑呵呵。
program weigh(input,output);
var n:integer;
function max(c:integer;d:integer):integer;
begin if c>=d then max:=c
else max:=d;
end;
function b(n:integer):integer;
var i,t,k,xiao,a,c:integer;
da:array[1..50] of integer;
begin
xiao:=6000;
for i:=1 to n do da[i]:=0;
if (n=0) or (n=1) then b:=0
else if (n=2) or (n=3) then b:=1
else
begin t:=n div 2;
for k:=1 to t do
begin a:=b(n-2*k);
c:=b(k);
if (da[k]<max(a,c)) then da[k]:=max(a,c);
end;
for k:=1 to t do
if xiao>da[k] then xiao:=da[k];
b:=1+xiao;
end;
end;
begin
writeln('please input n:');
read(n);
writeln('need weight times:');
writeln(b(n))
end.
-------------------------------------------------------------------------------- 袁哥 于 2000-11-23 20:07:49 加贴在 绿盟科技论坛(bbs.nsfocus.com)--灌水乐园：
称球问题最经典的解法
[email protected] 前段时间大家突然很有兴致的讨论了称球问题，看这么久也没人找出好的解法来，用信息论知识来解简直太容易了，对于这个解法，这些都是一样的，很容易。这种题有两个版本，一个是知道不同球是轻还是重，另一个是不知道轻还是重。其实这样类似的还有很多题。
例如题：现有n个外观一样的小球，其中有一个小球的重量与众不同（不知其轻重或者说知道轻或者重），请问最少称多少次一定可以将这个不同的球找出。
天平称重，有两个托盘比较轻重，加上托盘外面，也就是每次称重有3个结果，就是ln3/ln2比特信息。n个球要知道其中一个不同的球，如果知道那个不同重量的球是轻还是重，找出来的话那就是n个结果中的一种，就是有ln(n)/ln2比特信息，如果不知道轻重，找出来就是2n（n个球中的一个，轻或者重，所以是2n）个结果中的一种，那就是ln(2n)/ln2比特信息。
假设我们要称k次，根据信息理论，那显然两种情况就分别有：
（1） k*ln3/ln2>=ln(n)/ln2, 解得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个球中找出不同的球出来。 具体称法就不说了，其实真的理解了信息论里面的那不等式的等式成立条件就知道称法了，也就是要保证每次称的信息含量ln3/ln2。可以看看相关的一个帖子：http://dell1.cn99.com/thbbs/GreatTurn.AIX/00000042.htm。