《12个球问题》分析
有十二个乒乓球形状、大小相同,其中只有一个重量与其它十一个不同,现在要求用一部没有砝码的天秤称三次,将那个重量异常的球找出来,并且知道它比其它十一个球较重还是较轻。
这是在园友“小_金_鱼”的《寂寞的程序人生》中看到的一个题目,“11道题智商超200…”这几个字完全吸引了我,迅速在Google中搜出了这篇文章。看了这篇文章发现都似曾相识,在学校的时候一直想知道自己的智商,肯定在120以上,没事的时候总找一些相关的题目做做,但每次都让我失望,没有一次超过120。但不代表我会认为我的智商在120以下,现在还是一样一看到“智商”或是IQ就让我两眼放光。当然那篇博客我也就没有往下看,因为我不寂寞啊。
下班第一件事就是打电话给老婆,说今天有题目做了,受我的影响,她也喜欢做这样的题目,在吃晚饭的时候,我告诉了她题目,一告诉她题目我就马上思考,生怕她提前想到了方法,那我多没有面子,但是每次带着功利心去做事,根本就不能正常的思考,高考考了两次,本想考武大的,结果顺利考上了武职。得知她没有在想这个问题我就开心了,我可以正常的思考了,吃完饭没有想出来,老婆说她要在纸上画画,计算计算,还好我不需要,我就一边洗碗,一边思考,最终我想出来了,高兴之情难以言表,就像我突然明白《火车运煤问题》一样,“有时灵光一闪而过,牛顿也吃苹果”。雷军说得对:成功就是99%的汗水+1%的灵感,后半句都被我们有意忽略。其实1%的灵感重要性远远超过前面99%。当灵感到来的时候你必须放下一切的抓住它,对,就是放下一切,哪怕是手上拿着一把枪对着犯人。当然是开玩笑的。
接下来就是在纸上证明给老婆看,证明的过程中,她的话也对我很有提示,整个过程也就三四分钟。但是感觉紧张又刺激,过了几分钟之后,她说是不是漏了一种情况,真的把我给吓一跳,难道我少考虑了一种情况,马上再次证明给她看,又是紧张刺激,最后得出我的分析是对的,分析这种东西就是你分析完之后,你就知道是否对错了,最后你说这就是标准答案。对,就是这样。
下面是分析,不好意思都写成日记了。
一:天平两边先各6个球
由于两边的重量肯定不等,不用称都知道天平肯定不能平衡,白白浪费一次,难道你自认为牛B到用2次就能得出结论,显然你不会这样认为,排除。
二:天平两边先各5个球
如果天平不平衡,特殊的球可能在左边,也可能在右边,左边和右边个称一次,你得不出答案,但你却用了三次机会,Game Over。
三:天平两边先各3个球
称完一次之后,你知道那个特殊的球在其中的6个当中,你要用两次找出那个特殊的球。
你先在天平两边各放两个,如果平衡,你在想特殊球是在左边呢,还是右边,你只有一次机会了,最后你狠坚定的说,排除天平两边先各3个球的情况。
四:我们程序员一般不考虑天平两个先各放2个球,周星驰可能会考虑两边先各放1个球,最后他说:你猜猜那个特殊的球是哪个,是轻是重?你愤怒的说,把这种情况拖出去斩了。
五:天平两边先各放4个球,答案从这里揭晓,请认真看。
1: 如果天平平衡,特殊球在剩下的4个当中,其他8个都为普通球。从4个和8个当中各取3个放在天平上,
1.1:如果平衡,特殊球就是4个当中剩下的那个,你还有一次机会,并且你已经知道是哪个球了,随便和一个球比,如果它重它就是重的,如果它轻它就是轻的。
1.2:如果不平衡
1.2.1 如果特殊球所在的那边轻,特殊球就是轻的,三个球中,称一次找出那个轻的,你会的
1.2.3 如果特殊球所在的那边重,特殊球就是重的,三个球中,称一次找出那个重的,你会的
2:如果天平不平衡,剩下的4个是普通球。从轻的那边取出1个,从重的那边取出3个,放到天平的一边,为A,重的那边剩下的1个和三个普通的放到另一边B。
2.1 如果A=B,特殊球在轻的那边剩下的3个中,3个球,一次找出轻的那个。
2.2 如果A>B,特殊球是重的,在B中除了普通球之外的三个中,3个球,一次找出重的那个。
2.3 如果A<B,特殊球中A中来自第一次轻的那边的那个球(C),或者是B中来自第一次重的那个球(D),C<D,拿C或者是D与普通球比一下就知道答案了。
这次总该打完收工了吧,不要再告诉我说还有错啊,我有心脏病的。
看完之后,你发现其实很简单,的确是这样,不难,乐趣在在于分析和证明的过程。在于1%的灵感。
这个过程让我兴奋,所以我把这篇博客当做是陈太汉的代表作,我的另一篇代表作《火车运煤问题分析》
本文转自啊汉博客园博客,原文链接:http://www.cnblogs.com/hlxs/archive/2011/08/17/2142820.html