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

benjiam

原帖由 NalaGinrut 于 2008-3-4 21:38 发表


比1小？按你的意思1是最轻的，比1小是什么?
你用的应该是类似于merge方法，只不过你把最后的归并和称量判断合在一起了，
在这种情况下，下一个最轻的只能是5了，你说随便放哪边，那放右边是不是我说的那种 ...

在这种情况下，下一个最轻的只能是5了，  这个是错误的。  

我首先排过一次序的， 所以会是10 5 4 3 2 1 这样的顺序。不会出现10 4 3 2 1 5 这样的顺序。


比1小？  你目前最轻的球 是1 个单位了 那么后面的球重量都是比1 小的了。只有0.9 0.8 这样的球了。


先排序，由重到轻。V10，V9，V8......V1

左边放V10，右边放V9，
根据轻的一边来放V8，这样就是3个球如何放得以两边差最小。
再根据轻的一边来放V7，这样就是4个球如何放得意两边的茶最小。
同样 5个，6个...10个球的方法就是这样。

和我的是一个意思。

[ 本帖最后由 benjiam 于 2008-3-4 22:42 编辑 ]

lwbbs

就是利用天平对10个球进行排序。数据量不大，随便什么方法都可以。
如果只是想知道方法的话，应该是3秒钟的抢答题。

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

ssffzz1

1、给小球从1到10编号。
2、2-10号球都和1号球相比较，这样分出来3个大类，1是比1号球轻的。2是和1号球相等的，3是比1号球重的。
3、和1号球相等的不用处理了。
4、比1号球重的和比1号球轻的，都重复前面的过程。
5、前面的过程完成后，就会有一个从轻到重的顺序。
6、既然顺序都有了，那么剩下的就好办了。

zhengwei_zw

这个题不简单.很久前出现在微软的面试题上面.

zhengwei_zw

在很久前的<程序员>杂志出现求解过.记得有3页纸.实际是用算法和程序解答的.

cugb_cat

原帖由 ssffzz1 于 2008-3-5 08:59 发表
1、给小球从1到10编号。
2、2-10号球都和1号球相比较，这样分出来3个大类，1是比1号球轻的。2是和1号球相等的，3是比1号球重的。
3、和1号球相等的不用处理了。
4、比1号球重的和比1号球轻的，都重复前面的过 ...

顺序出来了，后续的呢？后续问题比排序麻烦多了。如果10个球的重量是做为输入的话，那就是背包问题，如果不是做为输入的话，完全不知道，好像没法做了。

hujiaobeibei

对的,大一的时候程序老师就给过这个问题.有算法和公式的!

trp111

天平连刻度都没了，还来丢人现眼

ssffzz1

题目要求是要求重量差最小。

[ 本帖最后由 ssffzz1 于 2008-3-5 12:07 编辑 ]

ssffzz1

题目要求是要求重量差最小。

既然顺序都出来了。那么把1 10 3 8  5放到一边，2 9 4 7 6的放到另一边。自然是重量差最小。