|
|
很简单阿,学过算法的应该不难啊.
我来给个解答:
用逆推逻辑,首先,如果3个球,知道坏球轻重,1次可以称出来（随便选两个称一下就可以了）. 那么,我们只需要在最坏的情况下,用2次称重,将范围缩小到3个球,并且确定坏球的轻重就可以了.
此时,我们从另一个方向想,第一次称,最多也就只能将坏球的范围缩小到4个球,且不知道坏球的轻重.
那么,我们现在主要是从4个球的分组中,成功将范围缩小到3个球,并且获得坏球轻重的信息.
现在我们按照上边的思路开始求解策略:
设,球编号1-12
分3组, (1,2,3,4) (5,6,7,8) (9,10,11,12)
随便选两组称1次:
假设(1,2,3,4) VS (5,6,7,8)
如果：(1,2,3,4) = (5,6,7,8)
那么：(9,10,11,12) 是坏球所在的组
将(9，10，11，12)分2组(9,10) (11,12).
用（1，2）和（9，10）称1次：（1，2） VS （9,10）
如果：（1，2）=（9，10）
那么：11，12中有一个是坏球
将1和11称1次，如果1 = 11，那么12是坏球；
如果 1 !=(不等于) 11， 那么11是坏球；
如果：（1，2）！=(不等于) （9，10）
那么：9，10中有一个是坏球
将1和9称1次，如果1 = 9，那么10是坏球；
如果 1 !=(不等于) 9， 那么9是坏球；
如果：(1,2,3,4) ！=（不等于） (5,6,7,8)，假设 （1，2，3，4）重一些，(1,2,3,4) >(5,6,7,8)。
那么：(9,10,11,12) 全部是好球，同时还知道
A:或者（1，2，3，4）中有个球偏重
B:或者（5，6，7，8）中有个球偏轻
将9，10，11，12分成 （9，10，11） 和12；目标是将范围缩小到3个球。
将1，2，3，4分成（1，2，3） 和4；
将5，6，7，8分成（5，6，7） 和8；
用好球（9，10，11）（4）和 （1，2，3）（8）称1次：（9，10，11）（4）vs （1，2，3）（8）
如果：（9，10，11）（4）= （1，2，3）（8）
那么：B成立，5，6，7，8中有个球偏轻，而且8是好球，所以，一个偏轻的坏球在（5，6，7）中，此时，可以比较(5) VS (6) 称1次，如果不相等，则轻的是坏球，如果相等，则没称得是坏球。
如果：（9，10，11）（4）> （1，2，3）（8）
那么：或者4偏重，或者8偏轻。此时用9和4或者8称1次就可以了，如果（9=4），则8是偏轻的坏球；如果（9<4）,那么4是偏重的坏球。
如果：（9，10，11）（4）< （1，2，3）（8）
那么：4不可能是偏重的球，8也不可能是偏轻的球，此时，只有一种结论：A成立，且（1，2，3）中有个偏重的坏球。选择1vs2 称1次，若不等，那么重的就是坏球；若相等，那么没称得就是坏球。
 |
|
发表于 2007-12-28 22:55:10
楼主
