j***i
发帖数: 1278 | 1 每次可以赛7匹，
我觉得是10次，有没有人知道标准答案 |
m****u
发帖数: 3915 | 2 10次？这么牛逼？
把你的答案先说说好么？
这个跟N个机器，找中点应该算一道题
【在 j***i 的大作中提到】
: 每次可以赛7匹，
: 我觉得是10次，有没有人知道标准答案
|
P********l
发帖数: 452 | |
j***i
发帖数: 1278 | 4 那我下面这个10次有什么问题
请指正
分7组 这是7次
然后 每组第4名 一轮 这样 可以排除最快得15个 和最慢15ge
a1 a2 a3 a4 a5 a6 a7
b1 b2 b3 b4 b5 b6 b7
c1 c2 c3 c4 c5 c6 c7
d1 d2 d3 d4 d5 d6 d7
e1 e2 e3 e4 e5 e6 e7
f1 f2 f3 f4 f5 f6 f7
g1 g2 g3 g4 g5 g6 g7
.
剩下19(e1-g3) +d4+(a5-c7)个找正数第10或倒数第10
然后 a6 b6 c6 d4 e2 f2 g2 跑一轮
d4 在中间是worst case 否则，可以正的淘汰更多，或倒着淘汰更多
a5 a6 a7
b5 b6 b7
c5 c6 c7
d4
e1 e2 e3
f1 f2 f3
g1 g2 g3
这样又淘汰了 6+6个
最后还有7个 a7 b7 c7 e 1 f1 g1 d4 最后跑一次
一共7+1+1+1
然后 |
S**I
发帖数: 15689 | 5 counter example:
1 2 3 4 5 31 39
8 9 10 11 22 29 30
6 7 14 18 20 21 23
15 16 17 19 26 27 28
12 13 24 25 33 34 35
32 36 37 38 40 41 42
43 44 45 46 47 48 49
【在 j***i 的大作中提到】
: 那我下面这个10次有什么问题
: 请指正
: 分7组 这是7次
: 然后 每组第4名 一轮 这样 可以排除最快得15个 和最慢15ge
: a1 a2 a3 a4 a5 a6 a7
: b1 b2 b3 b4 b5 b6 b7
: c1 c2 c3 c4 c5 c6 c7
: d1 d2 d3 d4 d5 d6 d7
: e1 e2 e3 e4 e5 e6 e7
: f1 f2 f3 f4 f5 f6 f7
|
E*******0
发帖数: 465 | |
a***i
发帖数: 39 | |
p*****a
发帖数: 147 | 8 每组第4名 比一轮，应该可以求得第28名，
然后把比第28名小的，可能是第27,26,25名的7个元素再比一次，
是不是就可以定出第25名了？
这样总共要9轮比赛
【在 j***i 的大作中提到】
: 那我下面这个10次有什么问题
: 请指正
: 分7组 这是7次
: 然后 每组第4名 一轮 这样 可以排除最快得15个 和最慢15ge
: a1 a2 a3 a4 a5 a6 a7
: b1 b2 b3 b4 b5 b6 b7
: c1 c2 c3 c4 c5 c6 c7
: d1 d2 d3 d4 d5 d6 d7
: e1 e2 e3 e4 e5 e6 e7
: f1 f2 f3 f4 f5 f6 f7
|
b*****n
发帖数: 482 | 9 Thanks again. You can only tell there are 27 horses run faster, and 3
horses run slower than that one. It's rank is in the range of 28 ~ 46.
【在 p*****a 的大作中提到】
: 每组第4名 比一轮，应该可以求得第28名，
: 然后把比第28名小的，可能是第27,26,25名的7个元素再比一次，
: 是不是就可以定出第25名了？
: 这样总共要9轮比赛
|
F******n
发帖数: 346 | 10 7 times if a timer allowed. If a timer is not allowed, how can a horse run
at the same speed in different races? |
|
|
p*****a
发帖数: 147 | 11 Yes, you are right. thanks.
【在 b*****n 的大作中提到】
: Thanks again. You can only tell there are 27 horses run faster, and 3
: horses run slower than that one. It's rank is in the range of 28 ~ 46.
|
g**********y
发帖数: 14569 | 12 这个问题好象不是很简单的样子。抛砖引玉 -->
简化问题到9匹马，每次可以赛3匹，多少次找出中点(第五快的马)?
直觉是前3次都一样：
a1 > a2 > a3
b1 > b2 > b3
c1 > c2 > c3
第四次可能都会竖着比，比第一列和第三列，可传递的关系不多，感觉比中间的第二列比较好。
不失普遍性，可以假设结果为 a2 > b2 > c2
现在的结果可以推出：
(1) a1, a2 比第5 快
(2) c2, c3 比第5 慢
剩下a3, b1 > b2 > b3, c1，互相之间没有确定关系
第5次比a3, b2, c1; 根据比较结果，再比1次可以确定中点。(最初我写的不对，但是修改一下可以证明这个是可行的)
综合起来，最坏情况要比 3 + 1(a2,b2,c2) + 1 + 1 = 6次
==============================================================
9匹马，每次赛3匹都这样。也许哪位能优化一下？到5次？
49匹马，每次7匹，我觉得10次找出来好象不可能。 |
P********l
发帖数: 452 | 13 niu.
列比较好。
【在 g**********y 的大作中提到】
: 这个问题好象不是很简单的样子。抛砖引玉 -->
: 简化问题到9匹马，每次可以赛3匹，多少次找出中点(第五快的马)?
: 直觉是前3次都一样：
: a1 > a2 > a3
: b1 > b2 > b3
: c1 > c2 > c3
: 第四次可能都会竖着比，比第一列和第三列，可传递的关系不多，感觉比中间的第二列比较好。
: 不失普遍性，可以假设结果为 a2 > b2 > c2
: 现在的结果可以推出：
: (1) a1, a2 比第5 快
|
m********l
发帖数: 4394 | 14
这不是Randomized Merge Sort吗？
只有Average Case
赛7次
然后把中间的拿出来再赛
然后排除太快和太慢
然后再赛剩下的
【在 j***i 的大作中提到】
: 每次可以赛7匹，
: 我觉得是10次，有没有人知道标准答案
|
f****4
发帖数: 1359 | 15 简化一下，5×5，每次5马，求第13快
5次，每次取第3名，5个第3名再赛一次
下面的是速度矩阵，越大的越快
93 94 56 98 99
91 92 55 95 96
70 60 50 40 30
67 29 49 39 29
66 18 48 38 28
第13名是56，上面哪个算法能找对？ |
h**********8
发帖数: 267 | |
z**k
发帖数: 629 | 17 最有人性的回复。
run
【在 F******n 的大作中提到】
: 7 times if a timer allowed. If a timer is not allowed, how can a horse run
: at the same speed in different races?
|
