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

NalaGinrut

分两步：
1、排序
2、奇偶交替放置
我认为关键考查的是排序算法的效率
不过奇偶交替有很大漏洞，等着标准答案出来
如果真是微软的试题，那我觉得考官未必想知道正确答案，他只是想考你的应变能力，无论对错你总得有个思路，
然后看你思路的清晰性和创造性。这才像是微软的风格。

[ 本帖最后由 NalaGinrut 于 2008-3-4 16:59 编辑 ]

NalaGinrut

原帖由 benjiam 于 2008-3-3 17:56 发表
应该是1：1 比较 分成 轻重2堆。
然后2堆分别排序， 然后合成一个列。
合成不是简单的加在一起， 不断拿最那堆和 重堆里面最轻的比较，类似冒泡的算法

在一个队列以后
那就是
先左10  右边9
不断向轻那 ...
在此同时如果有一边已经变有5个了 就把剩下的加到另外一边

这个算法将有很大漏洞，比如
左边刚好12345，右边为10，那剩下的都加到右边？

醉卧水云间

真有确定的解法吗, 我想不出

NalaGinrut

原帖由 醉卧水云间 于 2008-3-4 17:05 发表
真有确定的解法吗, 我想不出

天平又没有刻度，精确排序是不可能的，这个题或许是没有确定解法的，只是考应变的

benjiam

原帖由 NalaGinrut 于 2008-3-4 16:54 发表


这个算法将有很大漏洞，比如
左边刚好12345，右边为10，那剩下的都加到右边？

你对我的算法理解有问题。  如果一边的重量超过了另一边 就要转向的。

  1 2 3 4 5 已经比10 重了

所以 应该是
10                5

10                5 +4

10                5+4 +3
10+2            5+4+3
10+2+1        5+4+3

.....

benjiam

当然是有算法的。 利用天平的特性就可以了。 上面例子 剩下的小球 只有0.9 0.8 0.7   这样的小球了。

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

cugb_cat

原帖由 醉卧水云间 于 2008-3-4 17:05 发表
真有确定的解法吗, 我想不出

利用天平的重量不同的两侧会倾斜，可以对这10个球排序。

醉卧水云间

问题不在排序, 在于怎么分组和比较不同分组重量差的不同.

heefly

就是背包问题吧

cugb_cat

原帖由 醉卧水云间 于 2008-3-4 17:50 发表
问题不在排序, 在于怎么分组和比较不同分组重量差的不同.

背包问题了。