黑马程序员技术交流社区

标题: 面试题3 找坏球 [打印本页]

作者: orgcheng    时间: 2015-9-30 11:07
标题: 面试题3 找坏球
问题详情
有12个球,1个没有砝码的天秤。其中有11个球的重量是一样的,另外1个是坏球,和其他球的重量不一样,但无法确定是轻了还是重了。请问如何用天秤称3次,就找到坏球并确定是轻了还是重了。(没有砝码的天秤只能比较出两边谁重谁轻或是重量相等,无法求得具体的重量差)
解答
将球进行编号: 1 2 3 4 5 6 7 8 9 10 11 12,分为三组:(1,2,3,4) (5,6,7,8) (9,10,11,12)
第一称:称前两组。
   相等:可以知道8个球都是好的。
       第二次:称(1,2,3)和(9,10,11)。
            相等:12是坏球,用1和12称第三次就知道是重还是轻。
            不等:9,10,11 有坏球,并且已经知道是轻还是重。第三次称9和10就可以得到结果。

   不等:假设(1,2,3,4) < (5,6,7,8) (反过来的情况同理),并且知道了9,10,11,12是好球。
        第二次:称(1,2,5)和(3,4,6)。
            相等:7和8有一个重,称第三次即可。
            不等:假设(1,2,5)<(3,4,6)(反过来类似)。说明1,2轻了,或者6重了,第三次称1,2即可。

面试官角度:
一般问这个问题的公司就是想找平时喜欢研究智力题的人,或者他们公司的招聘名额很少。这是一个十分经典的智力问题。一般来说很难要求面试者在几分钟之内考虑周全。所以碰到这样的问题,知道就是知道,不知道就是不知道。不过即便不知道,比较聪明的面试者还是能够大致说出一些思路。比如一开始分成3堆,这个思路答上就会加分。如果分成2堆6个和6个,你会发现基本是解不出来的。所以这个题目纯粹是考验你是否是一个聪明的面试者或者你是不是准备面试题的时候做过了(那也说明你态度很端正)。

作者: SuperApollo    时间: 2015-9-30 12:04
学习了{:2_32:}。。。
作者: orgcheng    时间: 2015-9-30 14:46
自己给自己顶。。。。。。
作者: 斯文阿昊    时间: 2015-9-30 19:02
学习了,思想最重要
作者: pan1564335    时间: 2015-9-30 19:51
有点难啊
作者: 月影千华    时间: 2015-9-30 20:17
学习了 挺难的
作者: zenghua    时间: 2015-9-30 20:39
00000000000
作者: IT黑马_梧桐    时间: 2015-9-30 21:11
受教了,关键是不知道坏球是重是轻,所以分三组是最佳方法
作者: yxtyxj    时间: 2015-9-30 22:10
这题见过 确实很难
作者: shike951128    时间: 2015-9-30 22:15
表示没有ACM竞赛题难
作者: 召唤吧Bymax    时间: 2015-9-30 22:21
学习了   解题思考的意识还需要多多加强




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2