A*o
2 楼
以后院士要实行退休和退出制度了。
m*u
3 楼
10次？这么牛逼？
把你的答案先说说好么？
这个跟N个机器，找中点应该算一道题
【在 j***i 的大作中提到】
: 每次可以赛7匹，
: 我觉得是10次，有没有人知道标准答案
把你的答案先说说好么？
这个跟N个机器，找中点应该算一道题
【在 j***i 的大作中提到】
: 每次可以赛7匹，
: 我觉得是10次，有没有人知道标准答案
s*g
4 楼
熬到80才退呢。
P*l
5 楼
http://www.sureinterview.com/shwqst/1062001
http://www.sureinterview.com/schlsc?q=horse#
有人说最少用17次。
【在 j***i 的大作中提到】
: 每次可以赛7匹，
: 我觉得是10次，有没有人知道标准答案
http://www.sureinterview.com/schlsc?q=horse#
有人说最少用17次。
【在 j***i 的大作中提到】
: 每次可以赛7匹，
: 我觉得是10次，有没有人知道标准答案
w*h
6 楼
有啥意义？有啥好的？
【在 A**o 的大作中提到】
: 以后院士要实行退休和退出制度了。
【在 A**o 的大作中提到】
: 以后院士要实行退休和退出制度了。
j*i
7 楼
那我下面这个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
然后
请指正
分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
8 楼
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
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
9 楼
大家会把这个问题归为什么问题啊？
a*i
10 楼
http://en.wikipedia.org/wiki/Selection_algorithm
【在 E*******0 的大作中提到】
: 大家会把这个问题归为什么问题啊？
【在 E*******0 的大作中提到】
: 大家会把这个问题归为什么问题啊？
p*a
11 楼
每组第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
然后把比第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
12 楼
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轮比赛
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
13 楼
7 times if a timer allowed. If a timer is not allowed, how can a horse run
at the same speed in different races?
at the same speed in different races?
p*a
14 楼
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.
【在 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
15 楼
这个问题好象不是很简单的样子。抛砖引玉 -->
简化问题到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次找出来好象不可能。
简化问题到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
16 楼
niu.
列比较好。
【在 g**********y 的大作中提到】
: 这个问题好象不是很简单的样子。抛砖引玉 -->
: 简化问题到9匹马，每次可以赛3匹，多少次找出中点(第五快的马)?
: 直觉是前3次都一样：
: a1 > a2 > a3
: b1 > b2 > b3
: c1 > c2 > c3
: 第四次可能都会竖着比，比第一列和第三列，可传递的关系不多，感觉比中间的第二列比较好。
: 不失普遍性，可以假设结果为 a2 > b2 > c2
: 现在的结果可以推出：
: (1) a1, a2 比第5 快
列比较好。
【在 g**********y 的大作中提到】
: 这个问题好象不是很简单的样子。抛砖引玉 -->
: 简化问题到9匹马，每次可以赛3匹，多少次找出中点(第五快的马)?
: 直觉是前3次都一样：
: a1 > a2 > a3
: b1 > b2 > b3
: c1 > c2 > c3
: 第四次可能都会竖着比，比第一列和第三列，可传递的关系不多，感觉比中间的第二列比较好。
: 不失普遍性，可以假设结果为 a2 > b2 > c2
: 现在的结果可以推出：
: (1) a1, a2 比第5 快
m*l
17 楼
这不是Randomized Merge Sort吗？
只有Average Case
赛7次
然后把中间的拿出来再赛
然后排除太快和太慢
然后再赛剩下的
【在 j***i 的大作中提到】
: 每次可以赛7匹，
: 我觉得是10次，有没有人知道标准答案
f*4
18 楼
简化一下，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，上面哪个算法能找对？
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
19 楼
mark
z*k
20 楼
最有人性的回复。
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?
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?
相关阅读
endosome phagosome lysosome what is the differenceNature的那个关注的文章624个回复了@@不如，我们来做个Nature文章造假大集锦？nature wiki (转载)我们需要做个专门的网站记录这次事件Re: lai jiang的专业评论被删了？ (转载)有本事以后永远别投别引nature旗下的期刊找骂贴：如果几年后新技术检测出叶诗文尿样有问题怎么办？方舟子：实际上目前的检测方法不可靠请问如何查询荧光蛋白的cDNA？peoplem & neverthink 请进！Nature的回信 （肯定是群发，连个Title都没有）Editorial service为生物口的同胞鼓掌有人提议做个nature事件的wiki page,youtube上真实记录这一事件的视频英国自行车选手故意摔倒获得重赛机会paper helpNature这个鸟杂志的确很搞笑 (转载)To: 觉得"nature的文章我们也许反应过度了"的作者