A*o
2 楼
以后院士要实行退休和退出制度了。
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次,有没有人知道标准答案
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 楼
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?
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次找出来好象不可能。
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
相关阅读
老调重谈,读mba是改变命运的充分条件吗?港大,港科技大,新加坡国立分列1-3, 北大清华未进前十 (转载)生物学术冷笑话 (转载)找伙伴:请问这里有人参加2010 ACA meeting的吗?新手求教:怎样把小于30bp的DNA fragment 连接到vector上投稿杂志求大家建议,肿瘤抑制分子方面paper help(Curr Opin Infect Dis)求一篇文献What is the chinese translation of PI?原来这位大教授是意大利人 (转载)问下现在美国的造血干细胞移植很热吗?版上有UCSD博后么,请教DS表格的申请表格的相关问题版上单身gg可以去应征这个广告,笑死我了 (转载)【求助】果蝇实验的自身健康保护[包子求]J1反签时给签证官的老板支持信摸板 (转载)【求助】不匹配的限制性末端如何相连接,兼问当代T4连接酶的效率。UNC Dept. of Microbiology and Immunology 的请进请教为什么抗体会突然不好用我们学校晋升正教授的标准下个月在日本的拟楠芥会议有人同去吗?