今天面试栽在这个小题上了

ethans

按大小排序，从大到小放。这是算法里面的思想啊～

fhbkyo

其实很简单，有10个球，标1－10

A:拿其中一个，如1，放天平左，一个一个比下去

1：2
1：3
...
1:10

然后，比1重的放一边，比1轻的放一边

轻的那边再GOTO A:

用不了几下就出来了

然后重的分开放两边，轻的一个一个放，哪边轻了放哪边

[ 本帖最后由 fhbkyo 于 2008-3-12 12:01 编辑 ]

fhbkyo

其实这题的目的就是把每个球的重量按顺序排好就解决了

microjuz

原帖由 fhbkyo 于 2008-3-12 12:00 发表
其实很简单，有10个球，标1－10

A:拿其中一个，如1，放天平左，一个一个比下去

1：2
1：3
...
1:10

然后，比1重的放一边，比1轻的放一边

轻的那边再GOTO A:

用不了几下就出来了

然后重的分 ...

这个应该不对，如果正好A是最重或者最轻呢？

axing520

质量差最小！！最小！！！

jronald

从大到小交差放，不能保证是质量差最小，如
3 3 2 2 2
最小的是3 3     2 2 2

zerg_

凑个热闹。

先排序，再交叉分两组，然后根据两边轻重情况，两两成对互换，逐一调试，根据天平相差情况确定最优方案，如果有一个球过重1：9都能把天平砸扁，就算了。

jronald

删自己的

[ 本帖最后由 jronald 于 2008-3-12 17:55 编辑 ]

jronald

.............

[ 本帖最后由 jronald 于 2008-3-12 17:54 编辑 ]

jronald

C(10,1)+C(10,2)+ ... +C(10,5)种组合，根据排序结果可以直接去掉一部分不合理的，余下的比较一遍。前提是球的质量粒度要保证可以通过肉眼可以在天平上观察到