现在的位置: 首页 > 综合 > 正文

称球问题的测试解法

2014年04月12日 ⁄ 综合 ⁄ 共 2532字 ⁄ 字号 评论关闭
 

称球问题十几年前就在深圳的一网情深BBS上成为热门问题,此后的十余年间不断有人提起此问题,前段时间还在网上看到有人重新提起此问题,已经成为了新网民的入门级必知必会问题之一。
称球问题一般会有以下3种情况:
1、M个球,其中有一个坏球,知道是轻还是重,用天平称出坏球来。
2、M个球,其中有一个坏球,不知是轻还是重,用天平称出坏球来。
3、M个球,其中有一个坏球,不知是轻还是重,用天平称出坏球来,并告知坏球是轻还是重。
现在要问对于上面3种情况,称k次,最多可以在几个球中找出坏球来?也就是要求出称k次的M的最大值来。
1种情况,比较简单,1次可以称3个球,2次可称9个球,k次可以称3^k3k次方)个球。
2种情况就比第1种情况复杂多了,对第3种情况,和第2种情况类似,知道了第2种的解法后,第3种自然也就解出来了。
任意个数球的称法
假设有足够正常重量球的情况下称k次可以从最多F(k)个球里找出不知轻重的坏球(称多次的情况下,称完第一次就会有若干正常重量的球了),现在来计算称k+1次的F(k+1)最大可以到多少,在有足够正常重量球的情况下,0次可以称出1个球,1次可以称出2个球。因此F(0)=1,F(1)=2。
按照测试用例设计的元素分析法,先找出其中的元素:天平,若干球
先分析一下这些元素的属性,天平有两端托盘可以放东西,可以根据天平平衡情况判断天平两端放的东西重量是否相等。球的属性主要是重量,正常球重量都相等,坏球重量和正常球不相等。
再用测试用例设计的分类推理法来进行分类,按球的属性是无法分类的,因为每个球的重量都不知道,因此按天平属性来进行分类,可以将球分为三类,放在天平左端托盘中的,放在天平右端托盘中的,没有放入天平托盘的。
任何一个球最终都可以归结到上面分成的三类中,不论将球分成多少堆,最终都可以将其看成只有三堆,一堆要放入天平左端托盘中,一堆要放入天平右端托盘中,一堆不放入天平托盘中。所以分成了XYZ三堆(某堆可以为空)可以看成是唯一的分法。
将F(k+1)个球分成X,Y,Z三堆,先将X,Y放入天平的两端称一下,由于对成性,只需要考虑两种情况:
1XY一样重
此时只要在Z堆中找出坏球就可以了,Z=F(k)
2XY
在称完第1次后,此时可以再次使用元素分析法,找出四个元素:天平,XYZ
和前面一样可以采用分类推理法根据天平元素的属性将X分成X1X2X3Y分成 Y1Y2Y3Z分成Z1Z2Z3。由于对称性,可以按以下进行放置:
天平左端放置 X1Y1Z1
天平右端放置 X2Y2Z2
G(k) = X+Y
X1+Y1+Z1 X2+Y2+Z2重时,无法判断是Y2中有坏球还是X1中有坏球,由于对称性,可以假定Y20(球个数为0),那么就可以判断出X1中有坏球,且坏球比正常球重,此时X1+Y2=3^(k-1) 。如果X1Y2都不为0时,可以得到X1+Y2=G(k-1)
X1+Y1+Z1 X2+Z2重量相等时,表明坏球在X3+Y3+Z3中,由于此时无法判断坏球是在X3还是Y3中,如果令其中一个为0,那么另一个则为已知重量情况下称k1次的最大个数,因此X3+Y3最大值为3^(k-1),如果不为0,则X3+Y3=G(k-1)
X1+Y1+Z1 X2+Z2轻时,由于此时无法判断坏球是在Y1还是X2中,并且X2Y1重,这和XY重的情况是一样的,那么可以得出X2+Y1G(k-1)或者3^(k-1)
这时有G(k) X+Y = 3^k
或者G(k) X+Y = 3×G(k-1)
对后面那个等式,可以求出G(k) 3^(k-1)×G(1) ,由于G(1)的最大值不可能超过3
综合上面两种情况,G(k)取最大值3^k
由于Z堆中球的最大个数是在XY一样重的情况下来求解的,因此这里Z1Z2Z3中的球的个数并不重要,前面已经讲过 Z = F(k)
这样可以得到F(k1) = X+Y+Z = X1+X2+X3+Y1+Y2+Y3+Z
= F(k) +G(k)
=F(k) + 3^k
解出F(k) = (3^k 1) / 2 F(1) - (3 - 1)/2 = (3^k 1) / 2 1
这样求出了有足够标准球情况下称k次可以称出的最大值,在没有标准球的情况下,由于称2次只能称4个球,比有标准球时少一个,因此可以得出称k次可以称出的最大值为maxk(3^k 1) / 2
这样3次可以称出13个球,4次可以称出40个球….
 
根据以上的推理过程,可以得出以下的称法:
2次称5个球的称法(有标准球参照,F(2) = F(1)+3 = 2+3 = 5
有标准球时2次称5个球的称法
将球编号为12345,标准球记为S
12放入天平的一端,3S放入天平的另一端
如果12 3S,表明坏球在123中,此时将12放入天平两端称一下,如果重量相等则3为坏球,如果不相等则重的那个是坏球。
同理如果123S轻时,将12放入天平两端称一下,相等则3为坏球,不相等则轻的那个为坏球。
如果123S一样重,表明坏球在45里面,取4S一起称一下,相等则5为坏球,不相等则4为坏球。
 
3次称13个球的称法(无标准球做参考)
将球分为(1234),(5678),(910111213)三组
将(1234)和(5678)放入天平两端称一下
如果重量相等则转换为有标准球做参考在(9101112135个球里找坏球的问题,上面已经给出了。
如果重量不等,由对称性不妨设1234为重的一端
将(1567 891011)一起称一下
如果(1567)重,则表明坏球在18里面,只要拿一个标准球和18称一下就可以找出坏球
如果两边一样重,那么坏球在234里,且坏球为重球,称一次就可以称出
如果(1567)轻,那么坏球在567里面,且坏球为轻球,称一次就可以找出。
  

 

抱歉!评论已关闭.