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

sanor

菜鸟遍地都是。
我问你们如果有3个这样的球你能不能求出解来？如果能的话那么10个球为什么会让你如此困惑？

zongyaotang

假设已经排序，轻重已经编上号，1号最轻。
从最重的开始依次取。
第一和第二肯定不会在一起的。第一重为A堆，第二重为B堆。
之后的分配是：
把重的先放在轻的一堆上。
如此分发，直到发完。作为算法，这样的分发能趋于平均。

下面进行交换调整。
如果A堆重，看总序最轻的是否在A堆？
如果不在A堆，从B堆去取出，与A堆总序刚好比它大的交换。交换后翻盘，说明已经符合要求。
最后换到最轻的总序的几个都已经在A堆而不翻盘。则结束。
如果B堆重，则取B堆最重的与A堆刚好比它轻的交换。交换后翻盘停止。

我写了个C程序，解决“100张人民币分给7个人”
的问题，基本用的就是这样的算法。
但那里比这里要更复杂些。
惭愧的是，那个问题整整玩了一个星期。
在本站可以用以下标题找到：
“100张人民币分给7个人, 分的钱最平均的通用C实现”

[ 本帖最后由 zongyaotang 于 2008-3-12 05:50 编辑 ]

benjiam

第一和第二肯定不会在一起的。  这个设想是错误的

zongyaotang

应该承认，题目中的小球大概是看不出也掂不分量的。
否则无意义。

JohnBull

我怎么觉得这是个脑筋急转弯啊？！？！

既然没有刻度，如何判断“最小”？？

xgtd

很简单的问题，天平的特点是平衡，就是说，一边重，一边轻，就会是重的一变沉下去，轻的一边升上去。所以这个问题就演变成了，先排序，然后按重到轻依次往天平上放球球的问题了（不一定2边的球球数量相等）。排序问题，可采用2路归并排序（不知道记错了没有），先找个球，然后以这个球做基准，将剩余的9个球分成2组，一组比这个求重，一组比这个球轻，然后对这2组球进行同样的分组，到最后排序结束为止。放的时候先放重的，然后放轻的，哪变轻了就将下个球放到那边的天平上，这样直到所有球球放完为止。不知道，我说的对不对。

gaoas

先找出最轻或最重的那个再穷举，最多需要做136次

gaoas

对了，连个尺子都没有的话没法区分最小质量差的，单凭眼睛看天平的倾斜度不准确吧，有尺子的话可以给天平标刻度，就可以以最轻的小球为基数指定标准，可以称出每个小球的重量，再去计算就好了

dragonfly0427

o(∩_∩)o...哈哈

可以根据手感，
大小搭配两边放。