【经验总结】不能实施并行处理的情况	浅谈并行编程中的任务分解模式

论述12小球问题（升级散分）

楼主jihanzhong（逍遥）2005-04-27 14:49:30 在 Java / Web 开发提问

本人一只小菜鸟，刚来csdn几天（不到一星期），不小心升级了，高兴之余散分！！

本人没什么成果拿来和大家分享，昨天在帖子中看到12小球问题，回家思考一夜，颇有心得，决定升级论文就是这个了！请大家多提意见^_^

————————————————————————————————————————
论述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

问题点数：50、回复次数：31Top

1 楼jihanzhong（逍遥）回复于 2005-04-27 14:49:50 得分 0

再接下来考虑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次称量,各位可以试试啊!~!!!

Top

2 楼zhaohaiqing_001（景天）回复于 2005-04-27 14:53:05 得分 2

我是景天,什么意思?Top

3 楼jihanzhong（逍遥）回复于 2005-04-27 15:17:15 得分 0

根据该算法: 18个中有1个坏球挑出过程也只需要3次称量,各位可以试试啊!~!!!

不好意思，经过验证，不行。但是27个球4次是可以的
27 4次和18 3次之间的区别就是算法需要优化的地方

Top

4 楼woodcord（我心飞翔）回复于 2005-04-27 15:19:28 得分 2

呵呵，晕了，帮你顶一下！！Top

5 楼xuf2000（失衡的天秤）回复于 2005-04-27 15:23:30 得分 2

帮你顶一下，顺便恭喜你，再顺便接分，呵呵。Top

6 楼craigavon（廷飞）回复于 2005-04-27 15:23:48 得分 2

路过
顶一下Top

7 楼duanxd（）回复于 2005-04-27 15:26:22 得分 2

gzTop

8 楼smilefei（奇幻咖斐）回复于 2005-04-27 16:26:10 得分 2

楼主太厉害了　　
还敢说是小菜鸟
有空的试试程序！
顶Top

9 楼mind_1220（大灰狼）回复于 2005-04-27 16:28:44 得分 2

这个12球问题
也曾经让我考虑了很久.
后来我觉得它并不是难而是麻烦!Top

10 楼wzy19514（凡事留一线，日后好相见）回复于 2005-04-27 16:59:04 得分 2

谢谢楼主讲课，学习中。Top

11 楼Net8Java（男将╭ァＭ'r杜）回复于 2005-04-27 17:28:41 得分 2

数学不好，看不懂```但是要找出球不是太难！！
恭喜了，接分！！！Top

12 楼EchoEverything（小E）回复于 2005-04-27 17:42:34 得分 2

看得挺过瘾，弄得没明白！Top

13 楼andywhite（咬紧牙关向前冲）回复于 2005-04-27 17:55:02 得分 2

接分Top

14 楼an_andy（）回复于 2005-04-27 18:06:03 得分 2

jiefenTop

15 楼flyfoxx（fox）回复于 2005-04-27 18:13:24 得分 2

接分需要理由吗！Top

16 楼007remember（绿原）回复于 2005-04-27 19:57:55 得分 2

需要吗？不需要吗？
别认真，和您探讨下而已

^_^

路过
学习Top

17 楼princeliuxj（雨扬）回复于 2005-04-27 20:14:57 得分 2

我也想过,想通了就不难.Top

18 楼isni2（看中）回复于 2005-04-27 20:28:42 得分 2

厉害
接分！！！Top

19 楼superslash（开始用功学习）回复于 2005-04-27 20:32:18 得分 2

不懂,但是要顶Top

20 楼xiaozscs（小组生产）回复于 2005-04-27 20:38:49 得分 2

好复杂，顶了再说Top

21 楼mayeyun（mayeyun）回复于 2005-04-27 20:56:45 得分 2

厉害啊，果然是高人！Top

22 楼kotte（小学生）回复于 2005-04-27 20:58:19 得分 2

行家一出手就知有没有。
实在高！！Top

23 楼jihanzhong（逍遥）回复于 2005-04-28 10:03:50 得分 0

整理了以下：
1：无标准球，坏球不知道轻重，1次最多判断1个
2：有标准球，坏球不知道轻重，1次最多判断2个
3：有标准球，坏球已经知道轻重，1次最多判断3个
4：无标准球，坏球已经知道一端轻一端重，1次最多判断每端1个

5：无标准球，坏球不知道轻重，2次最多判断4个
6：有标准球，坏球不知道轻重，2次最多判断5个
7：有标准球，坏球已经知道轻重，2次最多判断9个
8：无标准球，坏球已经知道一端轻一端重，2次最多判断每端4个

验证过：39个可以4次称出Top

24 楼yinleiyoung（星际孤虹）回复于 2005-04-28 12:55:59 得分 2

楼主真是厉害啊！！
膜拜膜拜！！！Top

25 楼onray（39度）回复于 2005-04-28 13:09:11 得分 2

你是不是和我一样学数学的啊
不错Top

26 楼huangxiaodong9（晓晓）回复于 2005-04-28 15:30:55 得分 2

厉害，佩服，帮顶Top

27 楼fengyue2001（）回复于 2005-04-28 15:58:34 得分 2

高手啊Top

28 楼xtaotao（淘淘）回复于 2005-04-28 16:45:05 得分 2

高手,接分Top

29 楼jihanzhong（逍遥）回复于 2005-04-28 17:06:01 得分 0

研究最新成果如下：
重:轻表示一端重一端轻，两边数量一样
重|轻表示已知坏球偏重或偏轻
表中数据是最大可判断球数

规律已经很明显了~~~~

(无条件无标准球)(重:轻,无标)(无条件,有标)(轻:重,有标)(重|轻,无标)(重|轻,有标)
0次: 1 0:0 1 0:0 1 1
1次: 1 0:0 2 1:1 3 3
2次: 4 4:4 5 4:4 9 9
3次: 13 12:12 14 13:13 27 27
4次: 40 40:40 41 40:40 81 81
......

Top

30 楼qjyh（牵机引幻）回复于 2005-05-09 13:11:52 得分 0

厉害！佩服之极！
小弟我想了半天才大概理解。
楼主真是牛X！！！！！！！！！Top

31 楼qxaaa（北落师门）回复于 2005-05-26 17:12:00 得分 0

楼主真N啊Top