h**********g
发帖数: 3962 | 1 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
问：最少需要几次比赛参能选出最快的五匹马？
下面是一个最多使用8次比赛的方法。
第一步：
把25匹马分成5组，每一组有5匹马。每一组赛一次。
不失一般性，假设结果如下。
1A < 1B < 1C < 1D < 1E
2A < 2B < 2C < 2D < 2E
3A < 3B < 3C < 3D < 3E
4A < 4B < 4C < 4D < 4E
5A < 5B < 5C < 5D < 5E
第二步：各组的第二名在一起比赛。不失一般性，假设结果如下
1B < 2B < 3B < 4B < 5B
现在我们可以知道
(1) 1A一定入选
(2) 2D, 2E; 3B, 3C, 3D, 3E; 4B, 4C, 4D, 4E; 5B, 5C, 5D, 5E被淘汰
第三步：1D, 2B, 3A, 4A, 5A比赛。
我们分几种情况考虑。
(a) 1D < 2B < {...}
答案是1A, 1B, 1C, 1D加上min{1E, 2A}
(b) 1D < iA < {...}, i=3, 4, 5
答案是1A, 1B, 1C, 1D加上min{1E, 2A, iA}
(c) 2B < 1D < {...}
答案是1A, 1B, 2A, 2B加上min{1C, 2C}
(d) 2B < iA < {...}, i=3, 4, 5
答案是1A, 1B, 2A, 2B加上min{1C, iA}
(e) iA < jA < kA < {...}, 3 <= i, j, k <= 5
答案是1A, iA 加上 {1B, 1C, 2A, jA, kA}里的前三。
也许有笔误。但是道理应该是对的。 |
k**********4
发帖数: 16092 | 2 25匹马任意两匹马的速度都不同这个假设太强了
【在 h**********g 的大作中提到】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
|
B*Q
发帖数: 25729 | |
c****3
发帖数: 10787 | 4 最极端情况是第一轮，速度最快5匹马，都在一个组里。
能处理这个情况，就是需要的最小次数。
所以第一轮之后，肯定是从下往上赛的，才能处理 |
c*z
发帖数: 1074 | |
s****r
发帖数: 68 | 6
小于啥意思，用的时间，小就是快？
第二步比第二名，看不出哪个第一名能在top 5吧。
【在 h**********g 的大作中提到】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
|
h**********g
发帖数: 3962 | 7 不好意思。做排序做惯了。A < B 的意思是A排在B前面。
【在 c*z 的大作中提到】
: 你符号是不是颠倒了
|
h**********g
发帖数: 3962 | 8 这个假设是我加上的。为了严格起见。
允许同样快应该没有问题吧。但是我没有考虑。
【在 k**********4 的大作中提到】
: 25匹马任意两匹马的速度都不同这个假设太强了
|
s*****V
发帖数: 21731 | 9 用第三名比也可以，一次性可以排除一半的点，关键是第三步的讨论，要十分仔细，不
能遗漏任何情形。
【在 h**********g 的大作中提到】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
|
h**********g
发帖数: 3962 | 10 呵呵。没有太多的空余时间继续做。
这都是免费的啊。呵呵。
【在 B*Q 的大作中提到】
: 前五名也要排序呢？
|
|
|
h**********g
发帖数: 3962 | 11 排序通常符号。越小越好。
假设第六次比赛，1B最快。
1A一定在前五了。
因为1A比5个组的第二名都快。最差也是第5名。
【在 s****r 的大作中提到】
:
: 小于啥意思，用的时间，小就是快？
: 第二步比第二名，看不出哪个第一名能在top 5吧。
|
s****r
发帖数: 68 | 12 嗯，这个思路是get top5但不排序。
【在 h**********g 的大作中提到】
: 排序通常符号。越小越好。
: 假设第六次比赛，1B最快。
: 1A一定在前五了。
: 因为1A比5个组的第二名都快。最差也是第5名。
|
k**********4
发帖数: 16092 | 13 但是看不出八次是不是最少的
【在 s****r 的大作中提到】
: 嗯，这个思路是get top5但不排序。
|
d****a
发帖数: 3087 | |
m*********9
发帖数: 56 | 15 赛6次就可以找到最快的五匹马
赛八次太多了
【在 h**********g 的大作中提到】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
|
h**********g
发帖数: 3962 | 16 是的。非常容易证明至少需要7次。
但是要证明至少需要8次好像不是很容易。
【在 k**********4 的大作中提到】
: 但是看不出八次是不是最少的
|
c****3
发帖数: 10787 | 17 其实就是处理最坏情况，最快5匹马第一次就分在一个组里面。
第一轮比完。就从最后5名开始比
最后5名比出第一，这个第一和非本组的第四名的4匹马一起比，本组第四名因为已经比
过，不用重复。
就这么倒着来，能处理最快5匹马分在一个组的极端情况，最后需要的次数就是答案 |
k**u
发帖数: 10502 | 18 计时就可以了吧。
每匹马跑一次就够了，既然一次只能跑五匹，那一共是五次。
如果同一匹马一会跑得快一会跑慢了，那永远都没结果哈。 |
k**u
发帖数: 10502 | 19 类似运动会短跑，八条跑道，几十个人报名，怎么半。
这是个赛制安排的问题。
假设人人速度恒定，计时赛就可以。
实际上使用的是淘汰赛制。但是小组赛是第一名还是头两名还是前四名出线，或者是末
位淘汰，是有赛制决定的，有一定的主观因素。
结果是第一名应该是错不了的，但是越往后约不确定，比如说决赛第八名，极大可能不
是那
几十个选手中第八快的。 |
k**u
发帖数: 10502 | |
|
|
k**u
发帖数: 10502 | 21 回到原题。
最少需要六次比赛，即可以确定跑得最快的五匹马。
办法如下：
任意挑一匹马，这匹马伴跑所有比赛，实际上起到一个参照系的作用，然而不能像时钟
一样定量。
剩下24匹，四匹一组，共六组，每次一组加上伴跑马，跑六次。
最理想的情况下，累计有四匹马或者五匹跑得快于伴跑马，此时即可以确定跑得最快的
五匹马。 |
l******r
发帖数: 316 | 22 没啥难证的，大不了穷举法。
【在 h**********g 的大作中提到】
: 是的。非常容易证明至少需要7次。
: 但是要证明至少需要8次好像不是很容易。
|
K******r
发帖数: 4052 | 23 也是6次
【在 B*Q 的大作中提到】
: 前五名也要排序呢？
|
t******2
发帖数: 2265 | 24 就看到第二步，就看不下去了。
2D你是怎么排除的？
1A>1B>2B>2C>2D >3B/1C ...这个序列是怎么排除的？
【在 h**********g 的大作中提到】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
|
h**********g
发帖数: 3962 | 25 1A < 1B < 2B < 2C < 2D
2A < 2B < 2C < 2D
所以有五匹马（1A, 1B, 2A, 2B, 2C）比2D快。
【在 t******2 的大作中提到】
: 就看到第二步，就看不下去了。
: 2D你是怎么排除的？
: 1A>1B>2B>2C>2D >3B/1C ...这个序列是怎么排除的？
|
d********8
发帖数: 691 | 26 细节有漏的，但lz似乎是对的，这里第一个我能看懂的8次
lz思路很清晰，都帮我理清思路了
【在 t******2 的大作中提到】
: 就看到第二步，就看不下去了。
: 2D你是怎么排除的？
: 1A>1B>2B>2C>2D >3B/1C ...这个序列是怎么排除的？
|
g********n
发帖数: 1613 | 27 好像是错的。3B不能排除。所以第七次以后还有6个要比。应该是九次。
【在 h**********g 的大作中提到】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
|
