d**u
发帖数: 412 | 1 25匹马, 任何两匹的速度都不相同, 同一匹马跑两次的速度相同.
想找跑得最快的5匹马.
要求:
每次只能赛5匹马, 记录它们之间的先后次序, 不能记录它们的用时.
问:
最少需要赛几次? |
D****g
发帖数: 2860 | 2 嗯，就是Coreman的书里面的算法
【在 d**u 的大作中提到】
: 25匹马, 任何两匹的速度都不相同, 同一匹马跑两次的速度相同.
: 想找跑得最快的5匹马.
: 要求:
: 每次只能赛5匹马, 记录它们之间的先后次序, 不能记录它们的用时.
: 问:
: 最少需要赛几次?
|
x***1
发帖数: 197 | |
d**u
发帖数: 412 | 4 加油...
【在 x***1 的大作中提到】
: rrdw 能小于10次么。。。。？
|
h*****0
发帖数: 4889 | 5 是最少需要赛几次以保证能找出来，还是运气好的话最少要赛几次。又或者是平均次数。
【在 d**u 的大作中提到】
: 25匹马, 任何两匹的速度都不相同, 同一匹马跑两次的速度相同.
: 想找跑得最快的5匹马.
: 要求:
: 每次只能赛5匹马, 记录它们之间的先后次序, 不能记录它们的用时.
: 问:
: 最少需要赛几次?
|
d**u
发帖数: 412 | 6 最少几次肯定能找到.
数。
【在 h*****0 的大作中提到】
: 是最少需要赛几次以保证能找出来，还是运气好的话最少要赛几次。又或者是平均次数。
|
b******n
发帖数: 33 | 7 排序？偏序，全序？图论？
不会。
【在 d**u 的大作中提到】
: 25匹马, 任何两匹的速度都不相同, 同一匹马跑两次的速度相同.
: 想找跑得最快的5匹马.
: 要求:
: 每次只能赛5匹马, 记录它们之间的先后次序, 不能记录它们的用时.
: 问:
: 最少需要赛几次?
|
u****s
发帖数: 161 | 8 这题已经有人出过了. 你们都不记得了吗?
【在 d**u 的大作中提到】
: 25匹马, 任何两匹的速度都不相同, 同一匹马跑两次的速度相同.
: 想找跑得最快的5匹马.
: 要求:
: 每次只能赛5匹马, 记录它们之间的先后次序, 不能记录它们的用时.
: 问:
: 最少需要赛几次?
|
D****g
发帖数: 2860 | 9 selection algorithm, not sorting
【在 b******n 的大作中提到】
: 排序？偏序，全序？图论？
: 不会。
|
h*****0
发帖数: 4889 | 10 至少也要四百多次吧。。。
【在 x***1 的大作中提到】
: rrdw 能小于10次么。。。。？
|
|
|
N*****N
发帖数: 1605 | 11 要那么多？
【在 h*****0 的大作中提到】
: 至少也要四百多次吧。。。
|
N*****N
发帖数: 1605 | 12 不记得了
【在 u****s 的大作中提到】
: 这题已经有人出过了. 你们都不记得了吗?
|
h*****0
发帖数: 4889 | 13 obviously not...
i just made a silly mistake.
【在 N*****N 的大作中提到】
: 要那么多？
|
c******s
发帖数: 270 | |
b******n
发帖数: 33 | 15 How?
【在 c******s 的大作中提到】
: 7ci
|
D****g
发帖数: 2860 | 16 应该是8次。证明似乎比较复杂，需要考虑的情况很多。我再想想有没有简单的证明
【在 d**u 的大作中提到】
: 25匹马, 任何两匹的速度都不相同, 同一匹马跑两次的速度相同.
: 想找跑得最快的5匹马.
: 要求:
: 每次只能赛5匹马, 记录它们之间的先后次序, 不能记录它们的用时.
: 问:
: 最少需要赛几次?
|
s****n
发帖数: 1237 | 17 那个是25选3的，这个是选5，我猜是8次。
【在 c******s 的大作中提到】
: 7ci
|
d**u
发帖数: 412 | 18 说明:
本题原来是想出找最快3匹马的, 结果记错题目了.
不过找5匹也是个很好的讨论题.
标准答案就没有了.. sorry.
【在 d**u 的大作中提到】
: 25匹马, 任何两匹的速度都不相同, 同一匹马跑两次的速度相同.
: 想找跑得最快的5匹马.
: 要求:
: 每次只能赛5匹马, 记录它们之间的先后次序, 不能记录它们的用时.
: 问:
: 最少需要赛几次?
|
c***a
发帖数: 655 | 19 还是25匹里找3匹？
【在 d**u 的大作中提到】
: 说明:
: 本题原来是想出找最快3匹马的, 结果记错题目了.
: 不过找5匹也是个很好的讨论题.
: 标准答案就没有了.. sorry.
|
d**u
发帖数: 412 | 20 本来应该是这样的.
【在 c***a 的大作中提到】
: 还是25匹里找3匹？
|
|
|
c***a
发帖数: 655 | 21 sorry,没问清楚。原题是每次赛马只有3匹了，还是还能赛5匹，找最快的三匹？
【在 d**u 的大作中提到】
: 本来应该是这样的.
|
d**u
发帖数: 412 | 22 每次赛5匹马, 找最快的3匹.
【在 c***a 的大作中提到】
: sorry,没问清楚。原题是每次赛马只有3匹了，还是还能赛5匹，找最快的三匹？
|
c***a
发帖数: 655 | 23 这个应该就简单了。
随机编号 1-25
#1: 1-5
#2: 6-10
#3: 11-15
#4: 16-20
#5: 21-25
不失一般性，假设每次赛马都是编号小的速度快
这时候 4,5, 9,10, 14,15, 19,20, 24, 25都可以排出了。
#6: 1,6,11,16,21
同上，假设赛马结果的顺序也是编号小的速度快
这个时候可以把12-25排出了，因为至少1,6,11比他们快
8，9,10也可以排出，因为1,6,7比他们快
12，13也可以排出，因为1,6,11更快
最后还剩下5个比一下
#7: 2,3,6,7,11
这次胜出的前两名应该是2，3名
一共7次
【在 d**u 的大作中提到】
: 每次赛5匹马, 找最快的3匹.
|
f*****e
发帖数: 148 | 24 你的意思你改题目了？
找3匹？
【在 d**u 的大作中提到】
: 每次赛5匹马, 找最快的3匹.
|
h*****0
发帖数: 4889 | 25 找三八次很简单。找五应该不止八次吧?
【在 d**u 的大作中提到】
: 说明:
: 本题原来是想出找最快3匹马的, 结果记错题目了.
: 不过找5匹也是个很好的讨论题.
: 标准答案就没有了.. sorry.
|
D****g
发帖数: 2860 | 26 找5八次可以
【在 h*****0 的大作中提到】
: 找三八次很简单。找五应该不止八次吧?
|
h*****k
发帖数: 5022 | 27 how?
【在 D****g 的大作中提到】
: 找5八次可以
|
D****g
发帖数: 2860 | 28 比较麻烦，我先说说前面6次吧，开始5次自然是分5组赛。第六次把这5组的第二名拉出
来赛，结果假设如下：
1 2 3 4 5
H H H H H
H H H H H
H H H H H
H H H H H
H H H H H
每组从上到下依次成绩差，不失一般性假设每组第二名比赛排名是 group1>group2>
group3...
这样的话可以淘汰到剩下11匹马：
H H H H H
H H X X X
H H X X X
H X X X X
H X X X X
其中X表示被淘汰了的。
然后咱们给剩下的马编号:
1 6 9 10 11
2 7
3 8
4
5
已知顺序：1>2>3>4>5, 2>7, 6>7>8
第七场比赛： 3,7,9,10,11。第7场的结果决定了哪些马会被淘汰掉以及第8场怎么比。
但是第7场的结果可能性很多。举一个例子，如果结果是 3>7>9>10>11，那么8,9,10,11
都被淘汰，1,2,3就直接入选，剩下4匹赛一场即可
【在 h*****k 的大作中提到】
: how?
|
h*****0
发帖数: 4889 | 29 really? I'm eager to hear that? must be a very nice solution.
【在 D****g 的大作中提到】
: 找5八次可以
|
h*****0
发帖数: 4889 | 30 狂赞!
把第二名拉出来赛太巧妙了。我一直在考虑把第一名拉出来赛过之后的情况，怎么都搞
不定。
【在 D****g 的大作中提到】
: 比较麻烦，我先说说前面6次吧，开始5次自然是分5组赛。第六次把这5组的第二名拉出
: 来赛，结果假设如下：
: 1 2 3 4 5
: H H H H H
: H H H H H
: H H H H H
: H H H H H
: H H H H H
: 每组从上到下依次成绩差，不失一般性假设每组第二名比赛排名是 group1>group2>
: group3...
|
|
|
h*****k
发帖数: 5022 | 31 没懂
你group2 后面XXX3个怎么被淘汰的？
淘汰a的原则是不是因为有5个比a快了？
group2 后面3个XXX，只知道前面2个H比他快吧？
【在 D****g 的大作中提到】
: 比较麻烦，我先说说前面6次吧，开始5次自然是分5组赛。第六次把这5组的第二名拉出
: 来赛，结果假设如下：
: 1 2 3 4 5
: H H H H H
: H H H H H
: H H H H H
: H H H H H
: H H H H H
: 每组从上到下依次成绩差，不失一般性假设每组第二名比赛排名是 group1>group2>
: group3...
|
d**u
发帖数: 412 | 32 cool.
【在 D****g 的大作中提到】
: 比较麻烦，我先说说前面6次吧，开始5次自然是分5组赛。第六次把这5组的第二名拉出
: 来赛，结果假设如下：
: 1 2 3 4 5
: H H H H H
: H H H H H
: H H H H H
: H H H H H
: H H H H H
: 每组从上到下依次成绩差，不失一般性假设每组第二名比赛排名是 group1>group2>
: group3...
|
D****g
发帖数: 2860 | 33 竖的一列是一组。淘汰的原则是只要确定有5匹马更快
【在 h*****k 的大作中提到】
: 没懂
: 你group2 后面XXX3个怎么被淘汰的？
: 淘汰a的原则是不是因为有5个比a快了？
: group2 后面3个XXX，只知道前面2个H比他快吧？
|
h*****k
发帖数: 5022 | 34 哦
那第2组第4名哪5个比他快？
【在 D****g 的大作中提到】
: 竖的一列是一组。淘汰的原则是只要确定有5匹马更快
|
D****g
发帖数: 2860 | 35 第二组的前三和第一组的前二
【在 h*****k 的大作中提到】
: 哦
: 那第2组第4名哪5个比他快？
|
h*****k
发帖数: 5022 | 36 哦，懂了，谢谢 :)
【在 D****g 的大作中提到】
: 第二组的前三和第一组的前二
|
D****g
发帖数: 2860 | 37 答案是8次，证明很ugly。大家看看有没有简洁的证明（我怀疑有）:
Divide the horses into 5 groups, 5 in each group. Let's have 5 races. Then,
let's pick the 2nd from each group and have a 6th race. Let assume this is
the ranking of the first 6 races:
Group 1 2 3 4 5 |
