一道简单微软面试题，不google答案 自己做出来的年薪50万

德国足球加油

12个球外观一样，一个没有砝码的天平只能用来比较两边的重量，现知道只有一个和其它的重量不同（但不知道是轻还是重 ！！！或轻或重都可能 而且不知道轻多少或者重多少），问怎样通过天平称才能称三次就找到那一个球（每次称重只能称一次，放上去之后不可以增减），并且要说出这个球到底是轻了还是重了（前提当然是，不能用手感觉轻重，只能通过天平） 。


作出来听说年薪50万

德国足球加油

算法减少一步，都是如此的巧妙，这就是algo的魅力

nanguazaixian

这种题目，不重结果，重在思路

先给球编号，然后去排列组合3次后 称重分析吧。

这种题目还测试是不是有足够的打擦边球和盘外招的能力，比如编号这个动作就是数学上需要，实际中不一定允许的盘外招

chinapope

小学奥赛题。

几维鸟

OK，原来不知轻重。。。

adrenalin

知道轻重可以，不知道得四次好象

wfjwfj

3个球为一组，现分为4组，这样称三次就能找出来

德国足球加油

答出来。。年薪50万。。。

wfjwfj

我只是没具体说步骤  我是说了第一步！我的方法没有错啊。先称两次，找出重量不同的那个一组（3个球），然后最后一次就能找到目标。对吧？

schopenkitto

这个的确是有算法题成分在里面的，考分隔解决问题，但是有技巧不纯粹相等分割。先分出5个球和5个球比较。。。。省去若干字。这是好多年前的微软笔试题了吧，当年做了两遍，现在还在用吗？

wfjwfj

wfjwfj 发表于 2012-8-28 14:04
我只是没具体说步骤  我是说了第一步！我的方法没有错啊。先称两次，找出重量不同的那个一组（3个球），然后 ...

对于小时候没做过类似题目的人可能有些难，要是接触过这类题就不难！

费沙的白狐

年薪50w，还是苦逼啊，

xierwee

xierwee

xierwee 发表于 2012-8-28 14:32

没看清楚，所以把贴删了

并非如此

这题好像做过，要4个一组， 挺复杂的
第一次， 可知，在剩下4个中，还是天平上的8个中 如果在4个中，很简单。。。。
第二次，   在8个中，分别记录轻重，比如重的一组为A组， 轻的为b组，省下的为c组
然后，取出部分，在交换天平盘中的位置，进行一次3 v3 的比较， 通过这次交换一定要将怀疑球限定在两个以内

由于解这题比较浪费时间，仅给大家一个思路

德国足球加油

解这题不如出这题的人牛 估计年薪50万

贞爱

德国足球加油 发表于 2012-8-28 16:16
解这题不如出这题的人牛 估计年薪50万

出的人合计过百万

贞爱

贞爱 发表于 2012-8-28 16:22
出的人合计过百万

哈哈。其实解这题很简单。一个妈妈努力生十二个孩子，叫十二个孩子一起去，每人选个球，必定有一个中。五十万横竖她家的，跑不了

德国足球加油

考夫曼

I.1234 = 5678
II.1(11)>9(10) e.g. --> a. 9《-》/(10) 《-》/(11) 《+》
1(11) = 9(10) --> b. (12) 《?》
III. a.
9 < (10) --> 9《-》
9 = (10) --> (11) 《+》
9> (10) --> (10) 《-》
b.
(12) >< 1 e.g. -->《!》

I. 1234 > 5678 e.g.
II. 167 > 59(10) --> 1>5 《?》
167 = 59(10) --> 4>8 《?》
167 < 59(10) --> 6><7 《-》
III. 1/4/6 >< e.g.(10) --> 1《+》/4《+》/6《-》
1/4/6 = e.g.(10) --> 5《-》/8《-》/7《-》

jjviolet

以下方法错误，没看清楚特殊球不知轻重！请大家不要重复！  （第一次: 4个球一组, 分3组, 这次能决定哪组里有轻的球。两种情况： 如果两组一样重的在称上，那剩下的没称的那组就含有轻球；如果正好选了一组正常，一组轻的， 那一下就能得出。假设这组含轻球的叫A4。第二次：把A组的4个球分成2组称，这次能决定哪组（2个球）里有轻的那个，假设这组叫B2。第3次：称B2的2个球，既可得出哪个是轻的球）

jjviolet

jjviolet 发表于 2012-8-28 19:44
简单, 第一次: 4个球一组, 分3组, 这次能决定哪组里有轻的球。两种情况： 如果两组一样重的在称上，那剩下的 ...

我觉得我说的是对的。刚才第一步没说具体。

并非如此

jjviolet 发表于 2012-8-28 19:49
我觉得我说的是对的。刚才第一步没说具体。

第二次，必须是3v3的称，这题一点不简单，很老的题了， 你想法在于默认球是轻的， 这个前提是不存在的，如果你真的能简单解出来， 很感兴趣，请赐教。

jjviolet

并非如此 发表于 2012-8-28 19:53
第二次，必须是3v3的称，这题一点不简单，很老的题了， 你想法在于默认球是轻的， 这个前提是不存在的， ...

不对， 第2次一共4个球，3个正常重，1个轻。分成2组的话，就一种可能：1组2个正常重，1组一个正常重一个轻。

并非如此

jjviolet 发表于 2012-8-28 19:58
不对， 第2次一共4个球，3个正常重，1个轻。分成2组的话，就一种可能：1组2个正常重，1组一个正常重一个轻 ...

说了半天了，特殊的那个球，是不知轻重的，也就是说，第一次在秤上的8个球，如果不平衡，你根本不知道没，那边是含有特殊的球。

贞爱

chinapope 发表于 2012-8-28 13:45
小学奥赛题。

书14块
小王没钱，小李有13

jjviolet

并非如此 发表于 2012-8-28 20:00
说了半天了，特殊的那个球，是不知轻重的，也就是说，第一次在秤上的8个球，如果不平衡，你根本不知道没， ...

哦，我以为知道是有个轻球或者是重球呢。如果不知道特殊球的轻重的话你说的对， 第一次分3组后就会有3种可能。只有两边平衡的那种可能拿直接推出哪组含特殊球。然后要把另两组中的3个正常球和特殊组中的任3个球城。如果平衡，剩下没称的就是特殊球。如果不平衡，就是称上选出来的那3个球中有特殊球（因为另一组是正常球），或比正常组重或轻。如果重的话，3个球选两个称，平衡就是剩下的那个；不平衡就是称上重的那个；如果是轻的话，同理

另外两组情况就比较麻烦，要下班了，先撤

sparsity

没看过回复，2分钟想出来的。

1。两边各6个
2。轻的那边再各3个
3。轻的那边随机取两个一边各一个，如果不一样重，有结果，如果一样重，第三个。

德国足球加油

sparsity 发表于 2012-8-28 19:27
没看过回复，2分钟想出来的。

1。两边各6个

你怎么就判定是轻的呢？或轻或重都可能啊

sparsity

德国足球加油 发表于 2012-8-28 20:30
你怎么就判定是轻的呢？或轻或重都可能啊

你是说哪一步？