两道有趣的题

同事一起去吃饭的路上,喜欢分享一些有趣的题目,最近讨论的两个神题,非常有趣,也非常 难想。

1. 十二个球中找出不一样的那个

12个球,其中只有一个球不一样,该球只是重量跟其他球不一样,但外观是一样的,现在有一 个无砝码的天平,问最少称几次可以找出那个不一样的球?

分析:随便想想,4次称重是很容易找到目标球的,估计没这么简单,估计答案应该是3。答案也确实 是3次,再仔细分析一下,第一次称重必然是分三组,每组4个球,因为只有这样才能最大限度 地剔除一部分球。而且第三次称重,即最后一次称重,必须是对3个球进行,且此时要能够知道 目标球是比其他球重,还是轻。所以关键的第二次称重非常重要,通过这次称重,不仅要剔除到 只剩下3个球,而且还要知道目标球比其他球重还是轻。

答案:第一次称重分三组,球的代号如下,先称左边两组,最坏情况就是1234和5678不等,这样目标 球就在此8个球中。此时不失一般性地假定重量关系为1234 < 5678。

1 2 3 4      5 6 7 8      a b c d

第二次称重,非常巧妙,按如下进行,接下来,我们分析各种可能的结果。

5 2 3 4      1 a b c

如果5234 < 1abc,目标球在234中,而且目标球比其他球轻;如果5234 > 1abc,那么目标球 在5和1中,但不知道目标球和其他球的轻重关系,不过,此时范围已经缩小到2个球的了;如 果5234 = 1abc,那么目标球在678中,而且目标球一定比其他球重。

第三次称重,就很easy了。

2. 情报员如何最快地交换情报

有N个情报员,各自掌握一条情报,任意两个情报员接触一下,那么他们就互相知道了对方所掌 握的情报,此时此两个人掌握的情报条数一样,而且是接触前两个情报的总和。问最少多少次 接触可以使这N个人了解所有的情报,注意一次接触只是两个人之间进行。

分析:估计很快就能想到2N-3次接触是可以搞定的。假如第一个人依次和余下的N-1个人接触,那么此 人就掌握了全部的情报,而且最后接触的那个人也掌握了全部情报。接下来他只需要再跟中间 的N-2个人接触一遍,那么所有人就了解了所有的情报了,所以一共是N-1 + N-2 = 2N-3次。但 答案肯定不是这个,不然就太简单了。

答案:答案是2N-4。问题的突破口在于4个人的时候情况比较特殊,如果按2N-3来算,需要5次,而实 际上只需要4次,想想就能明白。而其他任何人数似乎都没有这个特性。于是乎一种巧妙的解法 诞生了,在N个人中拉4个人出来,让其中一个人与这4个人之外的人都接触一遍,即N-4次,然 后这四个人内部进行4次接触,这样这4个人就了解了所有的情报,然后4个人中的随便一个人再 次与4人之外的所有人接触,又花费了N-4次。总的算起来,就是(N-4) +4 + (N-4) = 2N-4,神 奇吧!

发表于 2013年07月17日 23:54   评论:0   阅读:457  



回到顶部

首页 | 关于我 | 关于本站 | 站内留言 | rss
python logo   django logo   tornado logo