jl123 (老是学) :这是以前的帖子,粘一下:回复人: xpg(座上宾) (2001-8-16 14:10:39) 得5分 对不起,上次看得太快了,看错了!抱歉! 不过12球跟13球是一样的这是真的,我套用goodfood(被迫卖素馅包的前人肉包贩子)的方法如下: 将十三个球分成A,B,C三组,每组四个球. 分别编号为: A组:A1,A2,A3,A4 B组:B1,B2,B3,B4 C组:C1,C2,C3,C4,C5先将A组与B组进行比较(第一次用天平称). 可能的情况有以下三种:一.A组=B组 此时可以断定不同的球在C组中。 将A1A2A3与C1C2C3进行比较(第二次用天平称). 可能的情况有以下三种:1.A1A2A3=C1C2C3 则不同的球在C4,C5中. 将C4与其他球进行比较(第三次用天平称),如相等答案是C5,如不等答案是C4. ###由于不需要判断轻重,故就在这儿改了一下!其他一样! 2.A1A2A3>C1C2C3 则不同的球在C1C2C3中,且偏轻. 将C1与C2进行比较(第三次用天平称). IF C1=C2 THEN 不同的球为C3; IF C1>C2 THEN 不同的球为C2; IF C1<C2 THEN 不同的球为C1.3.A1A2A3<C1C2C3 则不同的球在C1C2C3中,且偏重. 将C1与C2进行比较(第三次用天平称). IF C1=C2 THEN 不同的球为C3; IF C1>C2 THEN 不同的球为C1; IF C1<C2 THEN 不同的球为C2.二.A组>B组 将A1A2C1与A3A4B1进行比较(第二次用天平称). 可能的情况有以下三种:1.A1A2C1=A3A4B1 则不同的球在B2B3B4中,且偏轻. 将B2与B3进行比较(第三次用天平称). IF B2=B3 THEN 不同的球为B4; IF B2>B3 THEN 不同的球为B3; IF B2<B3 THEN 不同的球为B2.2.A1A2C1>A3A4B1 在A组>B组的前提下,A3或者A4不可能偏轻. 可能的情况有以下三种: (1).A1偏重; (2).A2偏重; (2).B1偏轻. 将A1与A2进行比较(第三次用天平称). IF A1=A2 THEN 不同的球为B1; IF A1>A2 THEN 不同的球为A1; IF A1<A2 THEN 不同的球为A2.3.A1A2C1<A3A4B1 在A组>B组的前提下,A1或者A2不可能偏轻,B1不可能偏重. 可能的情况有以下两种: (1).A3偏重; (2).A4偏重. 将A3与A4进行比较(第三次用天平称). IF A3>A4 THEN 不同的球为A3; IF A3<A4 THEN 不同的球为A4.三.A组<B组 将A1A2C1与A3A4B1进行比较(第二次用天平称). 可能的情况有以下三种:1.A1A2C1=A3A4B1 则不同的球在B2B3B4中,且偏重. 将B2与B3进行比较(第三次用天平称). IF B2=B3 THEN 不同的球为B4; IF B2>B3 THEN 不同的球为B2; IF B2<B3 THEN 不同的球为B3.2.A1A2C1>A3A4B1 在A组<B组的前提下,A1或者A2不可能偏重,B1不可能偏轻. 可能的情况有以下两种: (1).A3偏轻; (2).A4偏轻. 将A3与A4进行比较(第三次用天平称). IF A3>A4 THEN 不同的球为A4; IF A3<A4 THEN 不同的球为A3.3.A1A2C1<A3A4B1 在A组<B组的前提下,A3或者A4不可能偏重. 可能的情况有以下三种: (1).A1偏轻; (2).A2偏轻; (3).B1偏重. 将A1与A2进行比较(第三次用天平称). IF A1=A2 THEN 不同的球为B1; IF A1>A2 THEN 不同的球为A2; IF A1<A2 THEN 不同的球为A1.
12个球分别记为A,B,C,D,E,F,G,H,J,J,K,L; Q(A+B)代表A、B球重量和 if (Q(A+B+C)=Q(D+E+F)) if (Q(G+H)=Q(I+J)) if (Q(j)=Q(k)) 不同重量球是L else 不同重量球是K else if (Q(G+H)<Q(I+J)) if (Q(G+I)<Q(A+H)) 不同重量球是G,比普通球轻 else if (Q(G+I)>Q(A+H)) 不同重量球是I,比普通球重 else 不同重量球是j,比普通球重 else //Q(G+H)>Q(i+J) if (Q(G+I)<Q(A+H)) 不同重量球是H,比普通球重 else if (Q(G+I)>Q(A+H)) 不同重量球是I,比普通球重 else 不同重量球是j,比普通球轻 else if (Q(A+B+C)<Q(D+E+F)) if (Q(A+B+C)<Q(G+H+I)) //不同重量球比普通球轻 if (Q(A)=Q(B)) 不同重量球是C,比普通球轻 else if (Q(A)<Q(B)) 不同重量球是A,比普通球轻 else 不同重量球是B,比普通球轻 else if (Q(A+B+C)>Q(G+H+I)) //不同重量球比普通球重 if (Q(A)=Q(B)) 不同重量球是C,比普通球重 else if (Q(A)<Q(B)) 不同重量球是B,比普通球重 else 不同重量球是A,比普通球重 else //Q(A+B+C)=Q(G+H+I) 不同重量球比普通球重 if (Q(D)=Q(E)) 不同重量球是F,比普通球重 else if (Q(D)<Q(E)) 不同重量球是E,比普通球重 else 不同重量球是D,比普通球重 else //(Q(A+B+C)>Q(D+E+F))和(Q(A+B+C)<Q(D+E+F))比较差不多,不重述拉
我的主要错误不是从这里体现的
现在我知道可以从其余的球里面借用一个或者多个,正在思考
情况1:
一样重,则X球在剩下的一组中.任取两个比较,两种情况:
情况1.1:
一样重,则X球在剩下的两球中,再比较一次即可找出X球.
情况1.2:
一轻一重,则其中一个事X球,再比较一次即可得解;
情况2:
一轻一重,则两边各拿出两个球作交换,比较,两种情况
情况2.1
平衡关系不变,则小球在未作交换的小球中.再在未交换的小球中各取一个作交换,比较.两种情况;
情况2.1.1
平衡关系不变,则最后一个未作交换的小球即为X,轻重关系就是目前的平衡关系
情况2.1.2
平衡关系改变,明显X球即为交换的小球.
情况2.2
平衡关系改变,明显X球在交换的小球中.再比较一次即可的解.
1)称完之后剩下4个,不同的肯定在这里面
2)分成两组,称完之后肯定知道不同的在这2个里面,然后天平两边各取走一个,如果天平平衡,则不同的在手中,如果不平衡,不用说了,反正能够区分这个球,例如 1 2 3 4
12 34
------------ 34重
取走1 3
2 4 平衡
------------
可以知道3重或者1轻
3)从不平衡的两个中任取1个,放在天平上从其他的球中选择一个称量,就能够知道结果了
编号为1-12
分成3组,每组4个编号为a,b,c1)现在取a,b称,如果a,b平衡,则未知球在c中,去除8个
2)把现有的4个球重新编号为1,2,3,4
平均分成两组,假设假设假设假设假设1,2一组,3,4一组,放在天平上称,有两种情况
1)12重
2)34重
假设34重,我们从天平两边各取走一个球,例如取走1和4,现在有两种情况
1)天平平衡了,可以断定1比较轻或者4比较重
2)天平不平衡,可以断定3比较重或者2比较轻
3)现在把这两个球的任意一个(这里假设我们放的是4)放在天平的一边,另一边从a,b两个组中任选一个(他们都是等质量的)
1)平衡,可以断定1比较轻
2)不平衡,4比较重
一样重,则在另外6个中取出3个和A组比较,
一样重,则在未比较3球中有不同球,
3球中找不同球简单把
不一样重,重量大于A组,球重,重量小于A组,球轻
3球中找不同球简单把
不一样重,(A<B)则在另外6个中取出3个和天平上的A组3个比较
一样重,则不同球在B组中,在B组取2球比较
一样重,则未比较球是不同球,重
不一样重,则重的是不同球
不一样重,重量大于A组,球重,重量小于A组,球轻
3球中找不同球简单把
将12个球编号,为1--12,未知轻重的球位x.
先拿出1,2,3,4,和5,6,7,8,比较,如果一样重,很简单,用1,2,3和9,10,11比较......很简单,我不推了,主要看下面。
当1,2,3,4,和5,6,7,8不一样时:(两种情况,先假设1,2,3,4轻,5,6,7,8重,不这样假设也可以,推理方法一样,9,10,11,12为标准球)。
拿3,4,5,6,7为A组,8,9,10,11,12为B组:
如果:
A重:可肯定x在5,6,7中为重,在比一次出来了。
A轻:可知3,4轻或8重,把3,4一比,如果一样重,x为8球重;3,4不一样,x为3,4中轻的那个。
一样重:
x球为1,2中轻的那个。
对不起,上次看得太快了,看错了!抱歉!
不过12球跟13球是一样的这是真的,我套用goodfood(被迫卖素馅包的前人肉包贩子)的方法如下:
将十三个球分成A,B,C三组,每组四个球.
分别编号为:
A组:A1,A2,A3,A4
B组:B1,B2,B3,B4
C组:C1,C2,C3,C4,C5先将A组与B组进行比较(第一次用天平称).
可能的情况有以下三种:一.A组=B组
此时可以断定不同的球在C组中。
将A1A2A3与C1C2C3进行比较(第二次用天平称).
可能的情况有以下三种:1.A1A2A3=C1C2C3
则不同的球在C4,C5中.
将C4与其他球进行比较(第三次用天平称),如相等答案是C5,如不等答案是C4.
###由于不需要判断轻重,故就在这儿改了一下!其他一样!
2.A1A2A3>C1C2C3
则不同的球在C1C2C3中,且偏轻.
将C1与C2进行比较(第三次用天平称).
IF C1=C2 THEN 不同的球为C3;
IF C1>C2 THEN 不同的球为C2;
IF C1<C2 THEN 不同的球为C1.3.A1A2A3<C1C2C3
则不同的球在C1C2C3中,且偏重.
将C1与C2进行比较(第三次用天平称).
IF C1=C2 THEN 不同的球为C3;
IF C1>C2 THEN 不同的球为C1;
IF C1<C2 THEN 不同的球为C2.二.A组>B组
将A1A2C1与A3A4B1进行比较(第二次用天平称).
可能的情况有以下三种:1.A1A2C1=A3A4B1
则不同的球在B2B3B4中,且偏轻.
将B2与B3进行比较(第三次用天平称).
IF B2=B3 THEN 不同的球为B4;
IF B2>B3 THEN 不同的球为B3;
IF B2<B3 THEN 不同的球为B2.2.A1A2C1>A3A4B1
在A组>B组的前提下,A3或者A4不可能偏轻.
可能的情况有以下三种:
(1).A1偏重;
(2).A2偏重;
(2).B1偏轻.
将A1与A2进行比较(第三次用天平称).
IF A1=A2 THEN 不同的球为B1;
IF A1>A2 THEN 不同的球为A1;
IF A1<A2 THEN 不同的球为A2.3.A1A2C1<A3A4B1
在A组>B组的前提下,A1或者A2不可能偏轻,B1不可能偏重.
可能的情况有以下两种:
(1).A3偏重;
(2).A4偏重.
将A3与A4进行比较(第三次用天平称).
IF A3>A4 THEN 不同的球为A3;
IF A3<A4 THEN 不同的球为A4.三.A组<B组
将A1A2C1与A3A4B1进行比较(第二次用天平称).
可能的情况有以下三种:1.A1A2C1=A3A4B1
则不同的球在B2B3B4中,且偏重.
将B2与B3进行比较(第三次用天平称).
IF B2=B3 THEN 不同的球为B4;
IF B2>B3 THEN 不同的球为B2;
IF B2<B3 THEN 不同的球为B3.2.A1A2C1>A3A4B1
在A组<B组的前提下,A1或者A2不可能偏重,B1不可能偏轻.
可能的情况有以下两种:
(1).A3偏轻;
(2).A4偏轻.
将A3与A4进行比较(第三次用天平称).
IF A3>A4 THEN 不同的球为A4;
IF A3<A4 THEN 不同的球为A3.3.A1A2C1<A3A4B1
在A组<B组的前提下,A3或者A4不可能偏重.
可能的情况有以下三种:
(1).A1偏轻;
(2).A2偏轻;
(3).B1偏重.
将A1与A2进行比较(第三次用天平称).
IF A1=A2 THEN 不同的球为B1;
IF A1>A2 THEN 不同的球为A2;
IF A1<A2 THEN 不同的球为A1.
袁哥 于 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。
Q(A+B)代表A、B球重量和
if (Q(A+B+C)=Q(D+E+F))
if (Q(G+H)=Q(I+J))
if (Q(j)=Q(k))
不同重量球是L
else
不同重量球是K
else if (Q(G+H)<Q(I+J))
if (Q(G+I)<Q(A+H))
不同重量球是G,比普通球轻
else if (Q(G+I)>Q(A+H))
不同重量球是I,比普通球重
else 不同重量球是j,比普通球重
else //Q(G+H)>Q(i+J)
if (Q(G+I)<Q(A+H))
不同重量球是H,比普通球重
else if (Q(G+I)>Q(A+H))
不同重量球是I,比普通球重
else 不同重量球是j,比普通球轻
else if (Q(A+B+C)<Q(D+E+F))
if (Q(A+B+C)<Q(G+H+I)) //不同重量球比普通球轻
if (Q(A)=Q(B))
不同重量球是C,比普通球轻
else if (Q(A)<Q(B))
不同重量球是A,比普通球轻
else
不同重量球是B,比普通球轻
else if (Q(A+B+C)>Q(G+H+I)) //不同重量球比普通球重
if (Q(A)=Q(B))
不同重量球是C,比普通球重
else if (Q(A)<Q(B))
不同重量球是B,比普通球重
else
不同重量球是A,比普通球重
else //Q(A+B+C)=Q(G+H+I) 不同重量球比普通球重
if (Q(D)=Q(E))
不同重量球是F,比普通球重
else if (Q(D)<Q(E))
不同重量球是E,比普通球重
else
不同重量球是D,比普通球重
else //(Q(A+B+C)>Q(D+E+F))和(Q(A+B+C)<Q(D+E+F))比较差不多,不重述拉