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

zhy282289

楼上的已经被否定了~~
   因为如果有一个石头质量过大这个办法这不行了~~
冒似只能用语言写了~~~

LOSO

原帖由 zhy282289 于 2008-3-17 22:01 发表
楼上的已经被否定了~~
   因为如果有一个石头质量过大这个办法这不行了~~
冒似只能用语言写了~~~

10000  20  18  15  13  13  10  8  5  1

那么过程就是   10000     20
                               18
                               15
                               13
                               13
                     10
                     8
                     5
                     1
       total:  10024      79

有问题吗？着就是最小差呀

LOSO

你能举个反例出来说服我吗？

zongyaotang

请试：100 99 42 42 42 42 42 5 5 1

tyz

原帖由 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号球轻的，都重复前面的过 ...

排序方法不错
分而治之

sanbiangongzi

132楼 发表于 2008-3-18 12:07   


QUOTE:
原帖由 zhy282289 于 2008-3-17 22:01 发表
楼上的已经被否定了~~
   因为如果有一个石头质量过大这个办法这不行了~~
冒似只能用语言写了~~~
10000  20  18  15  13  13  10  8  5  1

那么过程就是   10000     20
                               18
                               15
                               13
                               13
                     10
                     8
                     5
                     1
       total:  10024      79

有问题吗？着就是最小差呀
-------------------------------------------------------------------------
我晕，按照你在130楼的算法，这样的数据不是这样做的啊

再说了，你在130楼的算法是错误的

sanbiangongzi

原帖由 LOSO 于 2008-3-18 12:09 发表
你能举个反例出来说服我吗？

      

对30,25,15,12,9这几个数，
按照你在130楼的做法应该是：
30     25
         15
12      
         9            
-------------
42     49

差距是7               

而下面的做法               
30     25  
15           //显然这一步并没有把15放在小的一边
         12
          9
-----------
45     46
差距是1