由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Military版 - 有25匹马,任意两匹马的速度都不同
相关主题
尼玛 先富党 北京2名警察小跑20余公里找回美国人丢失马匹国内的报纸太坏了-英国特工离奇裸死 警方疑被封口
北京2名警察小跑20余公里找回美国人丢失马匹 (转载)速滑比赛干嘛不单独搞赛道单独计时?
美国人北京租房遇黑中介 工商为其追回中介费谁胜出了?计时赛还是数帖子
Re: 狗家面试题目李将军的日本放水说什么原理?
有一天 txd有25匹马腾讯新闻 中国身家百亿富婆驾赛车冲出赛道 致13人受伤
将25匹马分为甲至戊五组分别比然后各排出一至五名中国女排的波兰球迷
所南门就知道跑马没人看我的诗吗世界杯应取消种子队和分组,全程采用淘汰赛制
所南门就知道跑马没人看我的诗吗我跑步最远记录,一千米3分20秒
相关话题的讨论汇总
话题: 2b话题: 1a话题: 1b话题: 1d话题: 2a
进入Military版参与讨论
1 (共1页)
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
3
前五名也要排序呢?
c****3
发帖数: 10787
4
最极端情况是第一轮,速度最快5匹马,都在一个组里。
能处理这个情况,就是需要的最小次数。
所以第一轮之后,肯定是从下往上赛的,才能处理
c*z
发帖数: 1074
5
你符号是不是颠倒了
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 的大作中提到】
: 前五名也要排序呢?
相关主题
将25匹马分为甲至戊五组分别比然后各排出一至五名国内的报纸太坏了-英国特工离奇裸死 警方疑被封口
所南门就知道跑马没人看我的诗吗速滑比赛干嘛不单独搞赛道单独计时?
所南门就知道跑马没人看我的诗吗谁胜出了?计时赛还是数帖子
进入Military版参与讨论
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
14
用下秒表,五次就行了。
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
20
选举制度也是类似的。
这个就不发散了。
相关主题
李将军的日本放水说什么原理?世界杯应取消种子队和分组,全程采用淘汰赛制
腾讯新闻 中国身家百亿富婆驾赛车冲出赛道 致13人受伤我跑步最远记录,一千米3分20秒
中国女排的波兰球迷国象棋后赛居文君加赛胜挑战者 连续三次夺冠
进入Military版参与讨论
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

1 (共1页)
进入Military版参与讨论
相关主题
我跑步最远记录,一千米3分20秒有一天 txd有25匹马
国象棋后赛居文君加赛胜挑战者 连续三次夺冠将25匹马分为甲至戊五组分别比然后各排出一至五名
【转】菲律宾人质事件最新发帖指南所南门就知道跑马没人看我的诗吗
菌斑这么多人才,光灌水可惜了了所南门就知道跑马没人看我的诗吗
尼玛 先富党 北京2名警察小跑20余公里找回美国人丢失马匹国内的报纸太坏了-英国特工离奇裸死 警方疑被封口
北京2名警察小跑20余公里找回美国人丢失马匹 (转载)速滑比赛干嘛不单独搞赛道单独计时?
美国人北京租房遇黑中介 工商为其追回中介费谁胜出了?计时赛还是数帖子
Re: 狗家面试题目李将军的日本放水说什么原理?
相关话题的讨论汇总
话题: 2b话题: 1a话题: 1b话题: 1d话题: 2a