一道简单微软面试题，不google答案 自己做出来的年薪50万
本帖最后由 德国足球加油 于 2012-8-28 20:14 编辑12个球外观一样，一个没有砝码的天平只能用来比较两边的重量，现知道只有一个和其它的重量不同（但不知道是轻还是重 ！！！或轻或重都可能 而且不知道轻多少或者重多少），问怎样通过天平称才能称三次就找到那一个球（每次称重只能称一次，放上去之后不可以增减），并且要说出这个球到底是轻了还是重了（前提当然是，不能用手感觉轻重，只能通过天平） 。
作出来听说年薪50万{:5_347:} 算法减少一步，都是如此的巧妙，这就是algo的魅力{:5_343:} 这种题目，不重结果，重在思路
先给球编号，然后去排列组合3次后 称重分析吧。
这种题目还测试是不是有足够的打擦边球和盘外招的能力，比如编号这个动作就是数学上需要，实际中不一定允许的盘外招 小学奥赛题。 本帖最后由 几维鸟 于 2012-8-28 13:59 编辑
OK，原来不知轻重。。。 知道轻重可以，不知道得四次好象 3个球为一组，现分为4组，这样称三次就能找出来 答出来。。年薪50万。。。{:5_333:} 我只是没具体说步骤我是说了第一步！我的方法没有错啊。先称两次，找出重量不同的那个一组（3个球），然后最后一次就能找到目标。对吧？ 这个的确是有算法题成分在里面的，考分隔解决问题，但是有技巧不纯粹相等分割。先分出5个球和5个球比较。。。。省去若干字。这是好多年前的微软笔试题了吧，当年做了两遍，现在还在用吗？ wfjwfj 发表于 2012-8-28 14:04 static/image/common/back.gif
我只是没具体说步骤我是说了第一步！我的方法没有错啊。先称两次，找出重量不同的那个一组（3个球），然后 ...
对于小时候没做过类似题目的人可能有些难，要是接触过这类题就不难！ {:2_235:}年薪50w，还是苦逼啊， 本帖最后由 xierwee 于 2012-8-28 14:37 编辑
{:2_240:} xierwee 发表于 2012-8-28 14:32 static/image/common/back.gif
没看清楚，所以把贴删了{:2_235:} 这题好像做过，要4个一组， 挺复杂的
第一次， 可知，在剩下4个中，还是天平上的8个中 如果在4个中，很简单。。。。
第二次， 在8个中，分别记录轻重，比如重的一组为A组， 轻的为b组，省下的为c组
然后，取出部分，在交换天平盘中的位置，进行一次3 v3 的比较， 通过这次交换一定要将怀疑球限定在两个以内
由于解这题比较浪费时间，仅给大家一个思路 解这题不如出这题的人牛 估计年薪50万 德国足球加油 发表于 2012-8-28 16:16 static/image/common/back.gif
解这题不如出这题的人牛 估计年薪50万
出的人合计过百万 贞爱 发表于 2012-8-28 16:22 static/image/common/back.gif
出的人合计过百万
哈哈。其实解这题很简单。一个妈妈努力生十二个孩子，叫十二个孩子一起去，每人选个球，必定有一个中。五十万横竖她家的，跑不了 {:5_360:} 本帖最后由 考夫曼 于 2012-8-28 19:39 编辑
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 于 2012-8-28 20:22 编辑
以下方法错误，没看清楚特殊球不知轻重！请大家不要重复！:sleepy:（第一次: 4个球一组, 分3组, 这次能决定哪组里有轻的球。两种情况： 如果两组一样重的在称上，那剩下的没称的那组就含有轻球；如果正好选了一组正常，一组轻的， 那一下就能得出。假设这组含轻球的叫A4。第二次：把A组的4个球分成2组称，这次能决定哪组（2个球）里有轻的那个，假设这组叫B2。第3次：称B2的2个球，既可得出哪个是轻的球） jjviolet 发表于 2012-8-28 19:44 static/image/common/back.gif
简单, 第一次: 4个球一组, 分3组, 这次能决定哪组里有轻的球。两种情况： 如果两组一样重的在称上，那剩下的 ...
我觉得我说的是对的。刚才第一步没说具体。 jjviolet 发表于 2012-8-28 19:49 static/image/common/back.gif
我觉得我说的是对的。刚才第一步没说具体。
第二次，必须是3v3的称，这题一点不简单，很老的题了， 你想法在于默认球是轻的， 这个前提是不存在的，如果你真的能简单解出来， 很感兴趣，请赐教。
并非如此 发表于 2012-8-28 19:53 static/image/common/back.gif
第二次，必须是3v3的称，这题一点不简单，很老的题了， 你想法在于默认球是轻的， 这个前提是不存在的， ...
不对， 第2次一共4个球，3个正常重，1个轻。分成2组的话，就一种可能：1组2个正常重，1组一个正常重一个轻。 jjviolet 发表于 2012-8-28 19:58 static/image/common/back.gif
不对， 第2次一共4个球，3个正常重，1个轻。分成2组的话，就一种可能：1组2个正常重，1组一个正常重一个轻 ...
说了半天了，特殊的那个球，是不知轻重的，也就是说，第一次在秤上的8个球，如果不平衡，你根本不知道没，那边是含有特殊的球。
chinapope 发表于 2012-8-28 13:45 static/image/common/back.gif
小学奥赛题。
书14块
小王没钱，小李有13 并非如此 发表于 2012-8-28 20:00 static/image/common/back.gif
说了半天了，特殊的那个球，是不知轻重的，也就是说，第一次在秤上的8个球，如果不平衡，你根本不知道没， ...
哦，我以为知道是有个轻球或者是重球呢。如果不知道特殊球的轻重的话你说的对， 第一次分3组后就会有3种可能。只有两边平衡的那种可能拿直接推出哪组含特殊球。然后要把另两组中的3个正常球和特殊组中的任3个球城。如果平衡，剩下没称的就是特殊球。如果不平衡，就是称上选出来的那3个球中有特殊球（因为另一组是正常球），或比正常组重或轻。如果重的话，3个球选两个称，平衡就是剩下的那个；不平衡就是称上重的那个；如果是轻的话，同理
另外两组情况就比较麻烦，要下班了，先撤 没看过回复，2分钟想出来的。
1。两边各6个
2。轻的那边再各3个
3。轻的那边随机取两个一边各一个，如果不一样重，有结果，如果一样重，第三个。 sparsity 发表于 2012-8-28 19:27
没看过回复，2分钟想出来的。
1。两边各6个
你怎么就判定是轻的呢？或轻或重都可能啊 德国足球加油 发表于 2012-8-28 20:30 static/image/common/back.gif
你怎么就判定是轻的呢？或轻或重都可能啊
你是说哪一步？