一道简单微软面试题，不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个球比较。。。。省去若干字。这是好多年前的微软笔试题了吧，当年做了两遍，现在还在用吗？