关于“12个球天平称3次”问题的信息学思考 天平最小称量值

今天下午和3个同事去爬山,下山时1同事说很无聊,于是我“很有聊”地出了一道高中以来我用于测试自己的思维清晰度的保留题目:心算789乘以987的答案。以前都是用789*(1000-13)算,今天首次用(800-11)*(1000-13),结果我很没面子地算成了110000-21257,而正确答案是800000-21257……汗。接着该同事给我出了一道题——据说是微软公司的面试题:

今有12个外观相同的球,其中11个球一样重,剩下那个球重量和其他11个不同。用1个天平称3次,找出那个重量异常的球。

我花了大概路上的20分钟,想出了3个答案,都被出题的同事一一否决,他还试图给我一个提示:第一次选多少球,被我谢绝了(答案当然要完全自己想出来才有成就感嘛~)。回到公司后又想了45分钟左右,终于在晚饭18:00前成功地答出了。

答案是很简单啦,到网上随便一搜都有,虽然可能稍有不同。
下面用“重?”表示“过重或正常的球”,“轻?”表示“过轻或正常的球”,“正常”表示“正常的球”。
(1)选出8个球,一边4个称。
(1_a)一样重:异常球在剩下4个里。从中选出2个,一边一个:如果一样重,那么异常球在剩下两个里;如果不一样重,那么异常球在这两个里。即,范围缩小到两个球。随便选1个和剩下那10个“正常”中的1个比较即可判断异常球。
(1_b)不一样重。此时情况是3组球:{重?,重?,重?,重?}是比较重的那一组,{轻?,轻?,轻?,轻?}是比较轻的那一组,{正常,正常,正常,正常}是没有称过的那一组。
(1_b_2){重?,重?,轻?}和{重?,重?,正常?}称量,剩下的是{轻,轻,轻} 和{正常,正常,正常}。
(1_b_2_a){重?,重?,轻?} 比较轻。这时,可能异常球是那个“轻?”,也可能是{重?,重?,正常?}组中两个“重?”中的1个。即,范围缩小到{重?,重?,轻?} 里。
(1_b_2_a_3)把一个“重?”和一个“轻”放在一组,另一组放两个“正常”。如果前者重,那么该组中“重?”就是异常重的那个;如果前者轻,那么该组中“轻?”就是异常轻的那个;如果一样重,那么剩下没称的那个“重?”就是异常重的那个。
(1_b_2_b){重?,重?,轻?} 比较重。这时异常球是该组中两个“重?”中的1个。即,范围缩小到{重?,重?} 里。
(1_b_2_b_3)随便选一个和“正常”比较,如果一样重,剩下的那个“重?”就是异常重的球;如果“重?”比较重,那么它就是异常重的球。

题目是解出来了,但光这样还不够过瘾。在思考过程中,我习惯性地找出思考方向,而不是像没头苍蝇一样往四处乱想。以下是我的思考结果。

1.本题本质上是一个搜索问题,从一大堆结果中找出一个目标的问题。这类问题的本质就是每次对样本空间测试都会得到某些信息,利用这些信息来设计之后的测试方法,最终获得终极信息——答案。因此,要让测试次数最少,就要让每次测试获得的信息(1)尽量多;(2)被充分利用。
2.关于“获取尽量多的信息”,一个很容易理解的看法是,那些可能有“左重右轻”、“左轻右重”和“一样重”3种可能结果的称量方式,比只有两种或一种可能的结果的称量方式更有助于获得较多的信息。
3.关于“信息被充分利用”,要点是判断出获得了那些信息,再自问自己的测试是否在任何结果中都充分利用了信息。信息包括“异常球在这x个球中”和“异常球较重/轻”。

本题的一个陷阱是,题目并没要求答题者判断异常球和正常球相比是更重还是更轻,这让答题者觉得这是个1/12的搜索问题。然而事实上,为了信息最大化,无论怎么称量都不可能出现“知道异常球所在却不知道该球比正常球重还是轻”。这是由于开始时球数是12是偶数(详情待证)。

从信息和熵的角度来看搜索问题,可以这么理解:答题者每次称量都从结果中获得一定的信息,这些信息累加并去掉重复(多余)信息,如果结果大于或等于问题的熵,那就能得到答案。

为什么3次称量的每一次都要保证可能的结果有3个?
由于异常球的位置是个1/12的问题,需要的信息是-ln(1/12)=ln(12),异常球较重还是较轻是个1/2的问题,需要的信息是-ln(1/2)=ln(2),本问题实际上需要的信息是ln(12)+ln(2)=ln(12*2)=ln(24)。
每次称量,即使没有任何信息损失,对于可能结果有3个的称法,每次称量获得的信息熵是ln(3),3次则是ln(3)+ln(3)+ln(3)-f=ln(27)-f。当然,如果设计不当,会有些多余信息f。如果f足够小,使得ln(27)-f大于问题的熵ln(24),那就能找到答案。
关于“12个球天平称3次”问题的信息学思考 天平最小称量值
如果3次称量中有任何一次只获得ln(2)的信息(即只有两种可能的结果),那3次称量的最大获得信息量是ln(3*3*2)=ln(18),即使信息没有多余,也无法得到答案。

为什么网上的答案的第一步都是一样的:4,4,4分组?
如果第一次称量时采用3,3,6的分组方式,3个3个称,那如果两边相等,剩下6个球就陷入1/6*1/2=1/12的搜索问题中了。而余下的两次称量最多只能提供ln(9)的信息,对于ln(12)的问题无能为力。

当然,上述的分析是很粗糙的,因为称量的方式获得的信息还受到天平两侧放多少球的影响。也没有对多余信息量f的计算以及为什么“知道异常球所在却不知道该球比正常球重还是轻的情况对于总球数12称3次的问题不可能出现”做出说明。这些留待以后我再慢慢思考……貌似很难很难,靠初等数学分析是不够的。

  

爱华网本文地址 » http://www.aihuau.com/a/25101012/105954.html

更多阅读

声明:《关于“12个球天平称3次”问题的信息学思考 天平最小称量值》为网友朱唇点点醉分享!如侵犯到您的合法权益请联系我们删除