黑马程序员技术交流社区

标题: [黑马云青年]两道面试逻辑题 [打印本页]

作者: shiweiCao 时间: 2013-6-11 23:02
标题: [黑马云青年]两道面试逻辑题
本帖最后由 shiweiCao 于 2013-6-14 02:06 编辑

一. 有12个一摸一样的小钢球，其中有一个的质量与其他的11个的质量不一样，现在有一架天平（无砝码）。请用这架天平从这12个小钢球中找出与其他质量不一样的那一个小钢球，并判别出这个小钢球是偏重还是偏轻。请证明最少要用几次？

二. 现在小明一家过一座桥，过桥时候是黑夜，所以必须有灯。现在小明过桥要１秒，小明的弟弟要３秒，小明的爸爸要６秒，小明的妈妈要８秒，小明的爷爷要１２秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后３０秒就会熄灭。问小明一家如何过桥?

第二个已经做出来了, 先一秒三秒一起过, 然后return一秒再让耗时最多的两个一起过去,然后return3秒
这样就可以了. 耗时29秒过河. 第一个就不会了.

作者: Changer_s 时间: 2013-6-12 10:42
本帖最后由 Changer_s 于 2013-6-12 10:56 编辑

第一题：5次吧
画个图你看看吧！

QQ截图20130612105434.gif (18.14 KB, 下载次数: 0)

作者: 袁梦希 时间: 2013-6-12 12:16
有点深度

作者: 神之梦 时间: 2013-6-12 12:44
高手的解法，只用3次
转载:
为方便叙述，对十二个小球依次按 1-12 编号，以 X←(...) 记目标球怀疑集合。最初：X←(1～12)，

I、取 L(1,2,3,4)，R(5,6,7,8)，第 I 次称量：
   A、平，则 X←(9～12)；
   B、否，则 X←(1～8)；

II(A)、取 L(1,2,3)，R(9,10,11)，第 II 次称量：
   a、平，则 X←(12)；
   b、否，则 X←(9,10,11)；

II(B)、取 L(1,2,7)，R(3,4,5)，第 II 次称量：
   a、平，则 X←(6,8)；
   b+、倾向与 I(A) 同，则 X←(1,2,5)；
   b-、倾向与 I(A) 异，则 X←(3,4,7)；

III(Aa)、取 L(1)，R(12)，第 III 次称量：
   判断出 X=12 为偏轻还是偏重。
III(Ab)、取 L(9)，R(10)，第 III 次称量：
   ①、平，则 X=11，查 II(Ab) 之记录判断其轻重。
   ②+、倾向与 II(Ab) 同，则 X=10，同时判断其轻重。
   ②-、倾向与 II(Ab) 异，则 X=9，同时判断其轻重。

III(Ba)、取 L(1)，R(8)，第 III 次称量：
   ①、平，则 X=6，查 I(B) 之记录判断其轻重。
   ②、否，则 X=8，同时判断其轻重。

III(Bb+)、取 L(1)，R(2)，第 III 次称量：
   ①、平，则 X=5，查 II(Bb+) 之记录判断其轻重。
   ②+、倾向与 II(Bb+) 同，则 X=1，同时判断其轻重。
   ②-、倾向与 II(Bb+) 异，则 X=2，同时判断其轻重。
III(Bb-)、取 L(3)，R(4)，第 III 次称量：
   ①、平，则 X=7，查 II(Bb-) 之记录判断其轻重。
   ②+、倾向与 II(Bb-) 同，则 X=4，同时判断其轻重。
   ②-、倾向与 II(Bb-) 异，则 X=3，同时判断其轻重。

作者: 郭天龚 时间: 2013-6-12 16:34
因为不知道特殊的哪一个钢球是轻是中所以第一次分成2份每一份六个是不行的，因为你不知道特殊究竟在那一半里。我来谈谈我的分法。
1.把12个钢球分成4份，每一份3个球。记做 ① ② ③ ④。这样拿①和另外随意2份比较，只要3次就可以知道不同的钢球在那一份里。且知道轻重。
      1.这里有两种情况第一种拿①与②比较，如果①这边低，那就拿①与③比较，如果持平，说明不同的钢球在②中且不同的钢球比较轻。如果还是①这边低，就说明不同的钢球在①且比较重. ②平③起和一样的。这种情况比较2次，就可知道不同钢球轻重，可以去掉9个球。
      2.第二种就是拿①和②③都持平那么不同的钢球在④中，拿④和其中一份比，④高则不同的钢球偏轻，④低则不同的钢球偏重。这种情况比较3次就知道不同钢球的轻重。可以去掉9个球。
2.经过上一次比较。这一次，已知的条件是剩余3个球，且知道轻重。如果轻，在剩余的三个秋种随便拿出2个比较，持平，没有比较的为不同的钢球，一高一低，高的为不同钢球
                                                                                       如果重，在剩余的三个秋种随便拿出2个比较，持平，没有比较的为不同的钢球，一高一低，低的为不同钢球
这样最少比较3次就可以知道不同钢球与轻重。
最多4次以知道不同钢球与轻重。

作者: 蚂蚁搬家 时间: 2013-6-12 18:00
第一题，最少的情况是3次
第二题，小明跟弟弟一起过3秒，小明的爸妈一起过8秒，小明的爷爷自己过12秒，合计23秒啊

作者: 陶吉才 时间: 2013-6-12 19:11
以上答案不评价。
第一题，将小球分ABCD4份，每份3个，第1次比A和B的这重量，如果天平不平衡，就说明A或者B有问题，第2次将A和C比重量，如果平衡就说明B有问题，如果不平衡就说明A有问题。第3次，取A中的任意两个比重，就可以得知有问题的那个，至于轻重就看前两次有问题的这一组是高了还是低了，低了就是轻，高了就是重。如果第1次A和B平衡，第2次拿A和C或者D比，可以找出有问题的那一份，然后第3次同上。口述就只能这样了，如过实际操作的话可以有更多的方法，但是三次绝对搞定

第二题：最省时间的方法是12秒的和8秒的先过，8秒后6秒的上桥，4秒后3秒的上，两秒后1秒的上，总共15秒搞定。
就这题，面试的时候能杀掉一大片

作者: funneies 时间: 2013-6-13 15:22
3次可以称出小球并可以判断，偏轻还是偏重。
（转）首先把小球分成三堆，每堆四个。
A: (1,2,3,4)  B: (5,6,7,8)  C: (9,10,11,12)
情况一：
1 第一次称重
随便拿出两堆来称，这里不妨假设拿出A和B
A(1,2,3,4)------------------------ B(5,6,7,8)
结果有两种可能性，第一种A和B相等，第二种A和B不相等。
对于第一种AB相等的情况。
那么C中肯定有一个次品了。接下来做第二次称重。
从AB中随便拿三个，从C中也随便拿三个
   D(1,2,3)---------------  E(9,10,11)
第二次称重也有两种可能。
2．1 如果还是相等的话
      那么剩下12就是次品。
      第三次称重
      随便拿一个球和最后剩下的12球相称就知道结果了。
2．2 如果第二次称重不相等的话。这里我们假设D<E, 那么E中肯定有一个是次品，而且我们可以知道次品相对于真品来说是偏重的。
   从E中任意拿两个出来做第三次称重。
   F (10)------- G(11)
   如果F＝＝G 那么  9 是次品，而且次品是偏重的。
   如果 F > G 那么 10 是次品，而且次品是偏重的。
   如果 F < G 那么 11 是次品，而且次品是偏重的。
好了，到这里为止，对于一次称重出现相等的情况，我们已经给出了解答。
那么对于第一次称重就出现不相等的情况，我们做一下分析：
情况二：
1 第一称重 A B 不相等。我们不妨假设 A < B, 那么C中的9，10，11，12小球必然都是真品。注意这
个技巧是解决问题的关键。我们注意到这样一个事实如果只是交互真品，天平的状态是不会改变的。
好，我们做以下的交换
      H (1,9,10,11) -----------------------------I(2,3,4,5)
因为我们知道9，10，11三个小球都是真品。现在做第二次称重。有两种情况：
2．1 天平保持原来的状态，也就是说 H < I, 那么我们可以知道2，3，4，6，7，8，9，10，11，12
都是真品，1，5小球中有一个是次品。好了，现在我们可以做第三次称重，从1，5中随便拿一个小球，
这里我们拿1小球，从2，3，4，6，7，8，9，10，11，12中随便拿一个，这里我们拿9小球。
做第三次称重，就可以知道结果了。
2．2 天平的状态发生了改变，这里还是有两种情况，第一种 H == I,第二种H > I
第一种对于 H == I 来说，我们知道1，2，3，4，5 ，9，10，11，12 都是真品，
那么6,7,8,必定有一个是次品，因为，第一次称重的时候，我们知道 H < I ,那么也就是说次品是偏重的。
从6，7，8 任意拿出两个来称重，不妨拿出6，7做第三次称重，结果就出来了。
第二种对于H > I 来说。我们可以知道2，3，4中必定有一个是次品。而且次品相对于真品来说是偏轻的。
因为原来 H < I ,现在是H > I ,那么必定是移动偏轻的次品才会导致这种情况。好，我们从2，3，4中
任意拿出两个，不妨拿出2，3 做第三次称重，就可以知道结果了。
可以访问下面的地址进行测试一下：
http://ued.taobao.com/quiz/?aWHYxj6csjNlfOK2wqbZRLQHY2o

作者: Changer_s 时间: 2013-6-14 00:54

funneies 发表于 2013-6-13 15:22
3次可以称出小球并可以判断，偏轻还是偏重。
（转）首先把小球分成三堆，每堆四个。
A: (1,2,3,4) B: (5,6 ...

牛逼，果然牛逼！

作者: Changer_s 时间: 2013-6-14 00:59

陶吉才发表于 2013-6-12 19:11
以上答案不评价。
第一题，将小球分ABCD4份，每份3个，第1次比A和B的这重量，如果天平不平衡，就说明A或者B ...

回答得很棒！

作者: shiweiCao 时间: 2013-6-14 01:58

蚂蚁搬家发表于 2013-6-12 18:00
第一题，最少的情况是3次
第二题，小明跟弟弟一起过3秒，小明的爸妈一起过8秒，小明的爷爷自己过12秒，合计 ...

过桥必须有灯, 得有人返回来送灯,这里就是一个问题.还有其它的,看下题目

作者: shiweiCao 时间: 2013-6-14 02:04

陶吉才发表于 2013-6-12 19:11
以上答案不评价。
第一题，将小球分ABCD4份，每份3个，第1次比A和B的这重量，如果天平不平衡，就说明A或者B ...

过桥时候是黑夜，所以必须有灯; 最多可过两人,而过桥的速度依过桥最慢者而定
还是十五秒吗?

作者: 贺靖轩 时间: 2013-6-14 15:33
1.12个球对半开，随便分
2.取天平中高的那部分，共计6个（因其中必有此球，偏轻）
3.将这6个球对半开，随便分
4.取天平中高的那部分，共计3个（因其中必有此球，偏轻）
5.从这3个球取2个，随便拿
6.1若平衡，则不在天平上的那球便是
6.2若不平衡，则取高的盘子中的那球

综上，3次；特点：全程操作傻瓜式，劳动量逐步降低（拿球越来越少）

作者: 袁梦希 时间: 2013-6-14 17:53

陶吉才发表于 2013-6-12 19:11
以上答案不评价。
第一题，将小球分ABCD4份，每份3个，第1次比A和B的这重量，如果天平不平衡，就说明A或者B ...

牛B

作者: 袁梦希 时间: 2013-6-14 17:54

funneies 发表于 2013-6-13 15:22
3次可以称出小球并可以判断，偏轻还是偏重。
（转）首先把小球分成三堆，每堆四个。
A: (1,2,3,4) B: (5,6 ...

牛B 继续努力

作者: 郭天龚 时间: 2013-6-14 18:10

贺靖轩发表于 2013-6-14 15:33
1.12个球对半开，随便分
2.取天平中高的那部分，共计6个（因其中必有此球，偏轻）
3.将这6个球对半开，随便 ...

前提是不同的钢球不知道是轻始重，对半分，去高的那一份，此球是偏轻，但是也有可能在低的那一份里啊。因为有可能此球偏重。

作者: a283398689 时间: 2013-9-30 17:04
。。。这是什么逻辑啊听不懂，我的想法是爸爸和小明弟弟一起过，小明弟弟过去呢爸爸还在桥上，小明在一秒的速度再过这样只用6秒过3个人记下来你懂的

作者: 十万一千 时间: 2014-10-3 21:56
第一题，应该三次就可以了。证明：如果你运气足够好，二分查找的时候，第二次就可以确认异常小球是偏重还是偏轻了，那么在第三次操作的时候，只需要分别在天平两端放入一个小球，就能够完全判断出那个异常小球了。

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

黑马程序员IT技术论坛 X3.2