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

wind_ch

簡單地將球依次放上去,然後看天平的傾斜放下一個.這種作法是不行的.
因為試圖去中和天平的平衡,卻不知道是不是過了
(將一組球放上去改變原來的傾斜,有可能使得兩邊的質量差拉大了)
反例:1000,998,997,996,100,10,4,3,2,1
一邊:1000,998,10,4,3
另一邊:997,996,100,2,1
這樣放應該是最小的.

正確的作法是:不僅要給球質量排序,還要知道任意兩個球之間質量差了多少,
(這個用天平也是可以得到近似結果的),最後決定如何放置.
10個球的話考慮起來太複雜了,頭大~
不知道有沒有簡潔的方案?
我的想法是:通過天平的比較操作,能不能給10個球加上某種帶權值的記數,然後直接處理10個數字

sunnyfun

哦，如果要考虑这种极端情况的话，那确实难度陡然增大了，肯定不是能在面试时间里能简单解答的了，不计计算量的话还是穷举最可靠，反正电脑比人脑快

unicom_2

原帖由 wind_ch 于 2008-3-7 11:09 发表
簡單地將球依次放上去,然後看天平的傾斜放下一個.這種作法是不行的.
因為試圖去中和天平的平衡,卻不知道是不是過了
(將一組球放上去改變原來的傾斜,有可能使得兩邊的質量差拉大了)
反例:1000,998,997,996,10 ...

我同意81楼的答案，首先你得注意先决条件，如果面你的是技术型，你就别钻牛角尖，整算法
如果是创造型号的职位，而且面你的人是开朗玩笑型，就告诉他，没办法（10个球。一个重1000其他9个每个重为1  2 3 ....9）你怎么做 ？
一般这种问题，主要是看考官，而不是看题目 ！

rsmunix

17楼的方法是对的。这就是一个递归的排序了。

xiaocongwjb123

原帖由 hll 于 2008-3-2 13:34 发表
有10个小球质量未知，一个天平没有刻度，要求一边放5个使两边质量之差最小，问怎么放。给了我不到5分钟时间没有答出来说回去等通知，真是郁闷

我的做法是：找出最重的和最轻的作为第一组，第二重和第二轻的作为第二组，第三重和第三轻的作为第三组，第四重和第四轻的作为第四组，
剩下的一个重（第五重），一个轻（第五轻）。然后把第一组和第四组放在天平一边，把第二组和第三组放在天平另一边;这个时候那边重的放第五轻，剩下一个（第五重）放在轻的一边。

而找出最重和最轻的方法：在10个球中任意选两个球放在天平两边，重的留下，轻的拿出去，再往剩下的8个球中任选一个放上去，重的留下，轻的拿走。。。。。。这样一来从10个球中通过天平选出最重一个球。接着在剩下的9个球重任选两个放在天平的两边，这回是轻的留下，重的拿走，接着在剩下的7个球重任选一个放在天平上，仍然是轻的留下，重的拿走。。。。。。这样一来就选出了10个球中最轻的一个球，最重的与最轻的组成第一组。

呵呵，接下来就在剩下的8个球中按照前面的方法选出第二重和第二轻的球组成第二组。。。。。。

以此类推，这就是我的思路，如果有不妥的地方请大家多多指教。

[ 本帖最后由 xiaocongwjb123 于 2008-3-7 16:14 编辑 ]

johnsonshu

我同意81楼的答案，首先你得注意先决条件，如果面你的是技术型，你就别钻牛角尖，整算法
如果是创造型号的职位，而且面你的人是开朗玩笑型，就告诉他，没办法（10个球。一个重1000其他9个每个重为1  2 3 ....9）你怎么做 ？
一般这种问题，主要是看考官，而不是看题目 ！
-------------------------------------------------------------
支持。 这种题总是这样，没有标准答案，就想看你解题思路

crashsky

原帖由 cugb_cat 于 2008-3-6 17:23 发表

10个球的重量分别为1,2,3,4,5,6,7,8,9,10时这种方法就不行。

要知道 天平没有刻度，就是说你不知道实际重量是多少
还有时间比较短， 题目要的是方法不是针对这10个1球

10个球得到的结果是下面（相等时先左后右)

左10 7 6 3 2
右9 8  5 4 1

重量差1 已经比较小了


如果是1000个，必须有一种通用的方法得到近似的值，是最优值，而不是一定要相等的值

[ 本帖最后由 crashsky 于 2008-3-7 17:05 编辑 ]

netice

???

[ 本帖最后由 netice 于 2008-3-8 11:06 编辑 ]

mygodispig

化石了...