论述12小球问题：
原题目如下：
有一架天平和12个小球，其中有11个重量相同，1个与另外11个不同（不清楚这个球是轻还是重），天平没有游标（只能分出轻重），要求最多称3次，就可以将其中重量特殊的小球找出来。
解法略~~
很多人都可以想到答案，但是你知道答案是怎么来的吗？大部分人可能都觉得是"妙手偶得之",是个人智力问题, 但是我认为,无论什么问题,只要你想出答案,一定在脑子里有一个隐式的推理过程,就算隐藏的再深,也有一条线索存在!
本文就是我整理该问题的思路所得，力争把该问题由智力题变成推理题！！
现在来看看更一般的问题：
有一架天平和N个小球，其中有N-1个重量相同，1个与另外N-1个不同（不清楚这个球是轻还是重），天平没有游标（只能分出轻重），要求称最少次数，将其中重量特殊的小球找出来。
思路：
要点A: 要称最少次数，那么我们必须最大程度利用每次称量取得的信息，减少坏球存在的范围！
1：一开始，所有的球在我们的眼里都是一样的,都标记为O，坏球存在的可能性有：(O.重) or (O.轻) 共2*N种可能性；
这时候的称法只有一种：O(i) : O(i)，i<N/2，左右各放i个小球。该操作把所有球分成了3部分：在天平上的A和B,剩下的部分C
进行该操作后的结果是：
(1)：O(i) = O(i) 说明坏球在剩下的C部分中，C部分有N-2*i个；
(2)：O(i)!=O(i) 说明坏球在天平上，我们把重的一端标记为A,轻的为B；
要点B：根据2分法原理，我们要尽可能让各种情况下取得信息平均，使得最坏情况的称量次数最少，才符合题意！
2：在1操作的结果上我们初步判断：
(1) 坏球在C部分中;(2)坏球在A和B部分中
大部分人都考虑到这一步!然后根据B原则. 会让(A)+(B)=(C)使其平分, 这就是原题3:3:6答案的由来!
这种判断下: (A+B)=(C)=N/2个; 坏球存在的可能性为:2*(N/2)=N种;
但是!!!!! 这个判断不符合A原则!!!!他漏掉不少信息,请看更好判断:
(1) 坏球在C部分中;(2)坏球在A中并且A重(重的被标记为A),或者坏球在B中并且B重
这种判断下: (1) 坏球存在的可能性为:2*(C)种
(2) 坏球存在的可能性为:(A.重)+(B.轻)种
根据B原则: 2*(C)=(A.重)+(B.轻) 因为(A)=(B),(C)+(A)+(B)=N, 所以: (A)=(B)=(C)=N/3
坏球存在的可能性为:2*(N/3)种;
3: 在2的结果上:
(1) 恢复到原命题,递归调用本处理过程,取N=原N/3; 根据递归思想,只考虑递归出口!
N=1 该球就是坏球, 已经得到答案, 但是不知道是轻是重
N=2时 取一个与标准球比较, 相等则另一个是坏球,但是不知道是轻是重,否则该球是坏球,并知道是轻还是重.
重要的是情况(2):
(2) 这时候的称法有三种"基本"的称法：取N=原N/3
A(i) : B(i);
A(i) : C(i);
C(i) : B(i); i<N
A(i) : C(i)可推出:
A(i) 等于 C(i) => 坏球在B(i) 或 A(N-i) 或 B(N-i)中, 坏球存在的可能性为2N-i
A(i) 大于 C(i) => 坏球在A(i) 或 B(N-i)中, 坏球存在的可能性为N
A(i) 小于 C(i) 不可能!
根据B原则: 2N-i=N => i=N , 最优时坏球存在可能性为N
B(i) : C(i)可推出:
B(i) 等于 C(i) => 坏球在A(i) 或 A(N-i) 或 B(N-i)中, 坏球存在的可能性为2N-i
B(i) 大于 C(i) 不可能
B(i) 小于 C(i) => 坏球在B(i) 或 A(N-i)中; 坏球存在的可能性为N
根据B原则: 2N-i=N => i=N , 最优时坏球存在可能性为N
可以发现 A(i) : C(i) 和 C(i) : B(i) 两者可推结论一样!!差别不大
A(i) : B(i)可推出:
A(i) 等于 B(i) => 坏球在A(N-i)或B(N-i)中,坏球存在的可能性为2*(N-i)
A(i) 大于 B(i) => 坏球在A(i)或B(i)中; 坏球存在的可能性为2*i
A(i) 小于 B(i) 不可能
根据B原则: 2*(N-i)=2*i => i=N/2 , 最优时坏球存在可能性为N
接下来考虑2元复合称法
2元"复合"称法共有以下6种:
a: A(i1)+A(i2):B(i1)+C(i2);
b: A(i1)+C(i2):B(i1)+A(i2);
c: A(i1)+C(i2):B(i1)+B(i2);
d: A(i1)+B(i2):B(i1)+C(i2);
e: A(i1)+C(i2):C(i1)+B(i2);
f: A(i1)+B(i2):C(i1)+C(i2);
i1+i2<=N;
分析:(i3=N-i1-i2)
a方法:A(i1)+A(i2):B(i1)+C(i2)
A(i1)+A(i2) = B(i1)+C(i2); 坏球在B(i2)中或者坏球在A(i3),B(i3)中;
坏球存在可能性为i2+i3+i3;
A(i1)+A(i2) > B(i1)+C(i2); 坏球在A(i1),A(i2),B(i1)中;
坏球存在可能性为i2+i1+i1;
A(i1)+A(i2) < B(i1)+C(i2); 不可能;
坏球存在可能性为0;
根据原则B: i2+i3+i3=i2+i1+i1 => i2=0 && i1=i3, 最优时坏球存在可能性为N
b方法:A(i1)+C(i2):B(i1)+A(i2)
A(i1)+C(i2) = B(i1)+A(i2); 坏球在B(i2)中或者坏球在A(i3),B(i3)中;
坏球存在可能性为i2+i3+i3;
A(i1)+C(i2) > B(i1)+A(i2); 坏球在A(i1),B(i1)中;
坏球存在可能性为i1+i1;
A(i1)+C(i2) < B(i1)+A(i2); 坏球在A(i2)中;
坏球存在可能性为i2;
根据原则B: i2+i3+i3=i1+i1=i2 => i3=0 && i1=i2/2=N/3, 最优时坏球存在可能性为2*N/3!!!!!!
c方法:A(i1)+C(i2):B(i1)+B(i2);
A(i1)+C(i2) = B(i1)+B(i2); 坏球在A(i2)中或者坏球在A(i3),B(i3)中;
坏球存在可能性为i2+i3+i3;
A(i1)+C(i2) > B(i1)+B(i2); 坏球在A(i1),B(i1),B(i2)中;
坏球存在可能性为i2+i1+i1;
A(i1)+C(i2) < B(i1)+B(i2); 不可能;
坏球存在可能性为0;
根据原则B: i2+i3+i3=i2+i1+i1 => i2=0 && i1=i3, 最优时坏球存在可能性为N
d方法:A(i1)+B(i2):B(i1)+C(i2);
A(i1)+B(i2) = B(i1)+C(i2); 坏球在A(i2)中或者坏球在A(i3),B(i3)中;
坏球存在可能性为i2+i3+i3;
A(i1)+B(i2) > B(i1)+C(i2); 坏球在A(i1),B(i1)中;
坏球存在可能性为i1+i1;
A(i1)+B(i2) < B(i1)+C(i2); 坏球在B(i2)中;
坏球存在可能性为i2;
根据原则B: i2+i3+i3=i1+i1=i2 => i3=0 && i1=i2/2=N/3, 最优时坏球存在可能性为2*N/3!!!!!!
e方法:A(i1)+C(i2):C(i1)+B(i2);
A(i1)+C(i2) = C(i1)+B(i2); 坏球在A(i2),B(i1)中或者坏球在A(i3),B(i3)中;
坏球存在可能性为i1+i2+i3+i3;
A(i1)+C(i2) > C(i1)+B(i2); 坏球在A(i1),B(i2)中;
坏球存在可能性为i1+i2;
A(i1)+C(i2) < C(i1)+B(i2); 不可能;
坏球存在可能性为0;
根据原则B: i1+i2+i3+i3=i1+i2 => i3=0 && (i1+i2)=N, 最优时坏球存在可能性为N
f方法:A(i1)+B(i2):C(i1)+C(i2);
A(i1)+B(i2) = C(i1)+C(i2);坏球在A(i2),B(i1)中或者坏球在A(i3),B(i3)中;
坏球存在可能性为i1+i2+i3+i3;
A(i1)+B(i2) > C(i1)+C(i2);坏球在A(i1)中;
坏球存在可能性为i1;
A(i1)+B(i2) < C(i1)+C(i2);坏球在B(i2)中;
坏球存在可能性为i2;
根据原则B: i1+i2+i3+i3=i1=i2 不可能!! => 最优化考虑,i3=0, i1+i2=N, i1=i2 坏球存在可能性分别为N,N/2,N/2取最大值为N
再接下来考虑3元复合称法
3元"复合"称法共有以下4种: (分析过程具体略,坏球存在可能性按=,>,<排列)
(i4=N-i1-i2-i3)
a: A(i1) + A(i2) + C(i3) : B(i1) + C(i2) + B(i3)
A(i1) + A(i2) + C(i3) = B(i1) + C(i2) + B(i3)
A(i3),A(i4),B(i2),B(i4): i3+i4+i2+i4
A(i1) + A(i2) + C(i3) > B(i1) + C(i2) + B(i3)
A(i1),A(i2),B(i1),B(i3): i1+i2+i1+i3
A(i1) + A(i2) + C(i3) < B(i1) + C(i2) + B(i3)
不可能:0
i3+i4+i2+i4=i1+i2+i1+i3 => i1=i4
分析具体过程略,坏球存在可能性分别为N,N,0 取最大值为N
b: A(i1) + A(i2) + B(i3) : B(i1) + C(i2) + C(i3)
A(i1) + A(i2) + B(i3) = B(i1) + C(i2) + C(i3)
A(i3),A(i4),B(i2),B(i4): i3+i4+i2+i4
A(i1) + A(i2) + B(i3) > B(i1) + C(i2) + C(i3)
A(i1),A(i2),B(i1): i1+i2+i1
A(i1) + A(i2) + B(i3) < B(i1) + C(i2) + C(i3)
B(i3): i3
i3+i4+i2+i4=i1+i2+i1 =i3 => i2=i4=0 && i1=i3/2=N/3
其实和2元里的d方法一样!!!!
c: A(i1) + C(i2) + C(i3) : B(i1) + A(i2) + B(i3)
A(i1) + C(i2) + C(i3) = B(i1) + A(i2) + B(i3)
A(i3),A(i4),B(i2),B(i4): i3+i4+i2+i4
A(i1) + C(i2) + C(i3) > B(i1) + A(i2) + B(i3)
A(i1),B(i1),B(i3): i1+i1+i3
A(i1) + C(i2) + C(i3) < B(i1) + A(i2) + B(i3)
A(i2): i3+i2
i3+i4+i2+i4=i1+i3+i1 =i2 => i3=i4=0 && i1=i2/2=N/3
其实和2元里的b方法一样!!!!
d: A(i1) + C(i2) + B(i3) : B(i1) + A(i2) + C(i3)
A(i1) + C(i2) + B(i3) = B(i1) + A(i2) + C(i3)
A(i3),A(i4),B(i2),B(i4): i3+i4+i2+i4
A(i1) + C(i2) + B(i3) > B(i1) + A(i2) + C(i3)
A(i1),B(i1): i1+i1
A(i1) + C(i2) + B(i3) < B(i1) + A(i2) + C(i3)
B(i3),A(i2): i3+i2
i3+i4+i2+i4=i1+i1 =i2+i3 => i4=0 && i1=N/3, i2+i3=2*N/3
分析具体过程略,坏球存在可能性分别为2*N/3,2*N/3,2*N/3 取最大值为2*N/3
此时所有情况分析完毕!!!!!
根据最优原则,应该选择2元的b或d方法! 三元的b,c分别等于二元的d,b,三元的d分析起来比较复杂,不与考虑!
下面分析2元的b方法(d方法类似!):
b方法:A(i1)+C(i2):B(i1)+A(i2)
A(i1)+C(i2) = B(i1)+A(i2); 坏球在B(i2)中或者坏球在A(i3),B(i3)中;
坏球存在可能性为i2+i3+i3;
A(i1)+C(i2) > B(i1)+A(i2); 坏球在A(i1),B(i1)中;
坏球存在可能性为i1+i1;
A(i1)+C(i2) < B(i1)+A(i2); 坏球在A(i2)中;
坏球存在可能性为i2;
根据原则B: i2+i3+i3=i1+i1=i2 => i3=0 && i1=i2/2=N/3, 最优时坏球存在可能性为2*N/3!!!!!!
=>称量方案:A(i1)+C(i2):B(i1)+A(i2)
可能结果:
(1)A(i1)+C(i2) = B(i1)+A(i2); 坏球在B(i2)中; i2=2*N/3 (小数进1)
(2)A(i1)+C(i2) > B(i1)+A(i2); 坏球在A(i1),B(i1)中;i1=N/3 (小数取整)
(3)A(i1)+C(i2) < B(i1)+A(i2); 坏球在A(i2)中; 2=2*N/3 (小数进1)
4:在3的结果上:
(1)(3)取N=2*N/3递归调用本处理过程!
(2) 递归调用 3的情况(2)处理!
---------------------------------------------
大致写完处理流程,有人有兴趣可以改写成程序代码!
但是,其实这个不是最优的!!!!
有人有兴趣的话,可以+我QQ17848541和我讨论!
根据该算法: 18个中有1个坏球挑出过程也只需要3次称量,各位可以试试啊!~!!!
原文
http://topic.csdn.net/t/20050427/14/3970657.html