问答 （数学趣味类）《5球排序》√已有答案√欢迎拓展和应用√

jingmouren

有5个球，重量各不同
只能两两相互比较重量而不能称量出重量
1、用最少的比较次数找出第三重的球
2、用最少的比较次数将这这5个球按重量排序
可能网上有，但最好不要搜索，自己做出来。并想出比较好的描述方式让大家容易明白你的操作过程

看到一楼的解答，发现我的题目描述不严密
应该为在最坏的情况下用最少的比较次数

yzh_nj_china

如果我人品好，我称5次~~正好是1>2>3>4>5~~~
楼下的继续~~~

blueicenan

5个球，简单了点了，呵呵！
5个称球问题的传统解，其各次称法一般是相关的，即第2次
称哪些球一般要依赖于第1次的称球结果，而第3次所称的球又要
依赖于前2次的称球结果。。。。。

1234561

首先将5个球标号，1、2、3、4、5，逐次进行如下：

第1次：称1、2，设1＜2，则此时球的排序为1＜2

第2次：称2、3，设3＜2

第3次：称1、3，设1＜3，则此时球的排序为1＜3＜2

第4次：称3、4，设3＜4

第5次：称2、4，设4＜2，则此时球的排序为1＜3＜4＜2

第6次：称3、5，设3＜5

第7次：称4、5，设4＜5

第8次：称2、5，完成。

上述结果都可以反推

fferror

楼主的题目的确不很严谨，比较重量的次数，包括最坏情况下，都与初始排列有关。再者，排序算法太多。

1234561

引用第4楼fferror于2007-12-18 13:26发表的 :
楼主的题目的确不很严谨，比较重量的次数，包括最坏情况下，都与初始排列有关。再者，排序算法太多。

依照楼主的题，这样的题目只能假设定一种情况然后依原假设定情况向下继续假设定推导

blueicenan

编号1 2 3 4 5，每次假定为需要更多称量次数的结果
12
13
23(假设2>3)
34
14(假设4>1)
45
35
25(假设2>5)
结果1 4 3 5 2
这算2分法吧，，应该有更好的结果

horky

5个球称8次。取一未称好的球与2球称一次，如2轻，再与1比较，如2 重轻则与3，4比较。要分出1，2，3，4，5最多3 次。G（5）=G（4）+3=8

jingmouren

Hint:
2,排序。 一般地，用比较的方法排序n元素序列，最好也要O(nlogn)比较    nlogn与log(n!)相当
n=5时，log(5!)=log(120).=.7
而且确实可以用7次比较完成这5个球的排序

Ｕ３３

五球排序

百度贴吧_逻辑学吧_改编题目——五球排序(http://post.baidu.com/f?kz=268145632) 35楼：

1v2，3v4-----2次，假设1>2，3>4；
1v3，--------1次，假设1>3,则1>3>4；
把5插入1，3，4中，需要2次，
结果有4种：
5>1>3>4，则把2插入3，4中，需2次
1>5>3>4，则把2插入5，3，4中，需2次
1>3>5>4，同上
1>3>4>5，同上
这样一共2+1+2+2＝7次

killl

好帖，可惜容易搜索到。

http://www.baidu.com/baidu?word= ... 0%F2&tn=myie2dg

建议更换某些相关要素，方便大家展开讨论

任取两个比较、排列，用一次；
加入第三个，用一次到两次；
加入第四个，先与三个中的中间一个比较，再按其结果向较轻或较重的方向，与另一个比较，用两次；
加入第五个，先与四个中较中间的一个比较。。。。。。，用两到3次。
共用6——8次。

jingmouren

引用第11楼shuchuxs于2007-12-19 22:41发表的 :
任取两个比较、排列，用一次；
加入第三个，用一次到两次；
加入第四个，先与三个中的中间一个比较，再按其结果向较轻或较重的方向，与另一个比较，用两次；
加入第五个，先与四个中较中间的一个比较。。。。。。，用两到3次。
共用6——8次。

已经说了，排序最坏情况要7次比较

说出1的次数，请不要搜索，自己想想怎么实现
1。找第三重的球，最坏情况下要6次。

Ｕ３３

这其实是个最小最大问题，即从最坏的可能中找出最好的结果。

四球排序

1、1v2，设 1>2

2、3v4，设 3>4

3、1v3，设 1>3 （若1<3，只需将编号(1,2)与(3,4)对调即可）

此刻我们已经有： 1>2, 1>3>4

4、2v4，若 2<4，则有 1>3>4>2，排序结束；若 2>4，则有 1>2>4, 1>3>4，还需继续比较

5、2v3，若 2<3，则有 1>3>2>4，若 2>3，则有 1>2>3>4

四球排序最多需要5次。

五球中的前三名

6、5v（四球中的第3名），决定5是否进入前三名

最多需要6次。

jingmouren

引用第13楼Ｕ３３于2007-12-20 00:34发表的 :
这其实是个最小最大问题，即从最坏的可能中找出最好的结果。
1、1v2，设 1>2
.......

嗯，确实是minmax问题。但楼上的解答不对。因为要求找出的是第三重的球，而不是前三重的三个球。

四球排序最多需要5次。  OK

五球中的前三名
6、5v（四球中的第3名），决定5是否进入前三名      
最多需要6次。     有问题.
找到了前三名，到底哪个为第三名并不清楚。所以这种方法还需要继续比较确定哪个是第三名，所以超过6次了。

Ｕ３３

不好意思，记错题目了。重做如下：

1、1：2 -> 1>2
2、3：4 -> 3>4
3、2：4，若2>4，则1>2>4，3>4；把4扔掉。若 2<4，则 1>2，3>4>2；把2扔掉。

   于是我们或者有1>2,或者有3>4,若是后者，把3、4的编号改为1、2，另外2球的编号于是就是3、4。

4、3：4 -> 3>4
5、重复步骤3，再扔掉1球，并重新编号，且有1>2，另外1球的编号于是就是3。
6、2：3，取小的。

完毕