c*******a
发帖数: 1879 | 1 There are 25 horses. At a time only 5 horses can run in the single race. How
many minimum races are required in all cases to find the top 5 fastest
horses? (No timer
) |
U***r
发帖数: 565 | 2 25匹马
5匹一赛
5次呗
每次取第一名
How
timer
【在 c*******a 的大作中提到】
: There are 25 horses. At a time only 5 horses can run in the single race. How
: many minimum races are required in all cases to find the top 5 fastest
: horses? (No timer
: )
|
m********k
发帖数: 1 | |
z*****g
发帖数: 75 | |
c*******a
发帖数: 1879 | 5 你智商基本为0
【在 U***r 的大作中提到】
: 25匹马
: 5匹一赛
: 5次呗
: 每次取第一名
:
: How
: timer
|
c*******a
发帖数: 1879 | 6 你智商也不行
【在 z*****g 的大作中提到】
: 6
|
U***r
发帖数: 565 | 7 傻逼
你智商基本为零
题目说了最少次数
【在 c*******a 的大作中提到】
: 你智商基本为0
|
L******i
发帖数: 3027 | 8 可以计时吗？如果可以计时的话 这道题难道不是trivial吗？
How
timer
【在 c*******a 的大作中提到】
: There are 25 horses. At a time only 5 horses can run in the single race. How
: many minimum races are required in all cases to find the top 5 fastest
: horses? (No timer
: )
|
B*Q
发帖数: 25729 | 9 嗯
您是大牛！
【在 m********k 的大作中提到】
: 多路merge sort?
: Topk?
|
c*******a
发帖数: 1879 | 10 题目说了， NO TIMER
【在 L******i 的大作中提到】
: 可以计时吗？如果可以计时的话 这道题难道不是trivial吗？
:
: How
: timer
|
|
|
B*Q
发帖数: 25729 | 11 可以数脉搏么？
【在 c*******a 的大作中提到】
: 题目说了， NO TIMER
|
L******i
发帖数: 3027 | |
B*Q
发帖数: 25729 | |
T****t
发帖数: 11162 | |
T****t
发帖数: 11162 | 15 马每次发挥稳定吗。。。
多跑几次千里马也受不了。 |
c*******a
发帖数: 1879 | 16 对， 虽然没有秒表， 但是每次可以记下5个马的快慢排序， 为后来的多次跑马做铺垫。
【在 T****t 的大作中提到】
: 也就是排序，原来是2个比，现在是5个比
|
L******i
发帖数: 3027 | 17 int H[5][5]
for(int i = 0; i < 5; ++i)
sort(H[i]); // race
for(int i = 0; i < 5; ++i)
A = {H[0][0], H[1][0], H[2][0], H[3][0], H[4][0]}
sort(A); // race
output A[0];
Assume A[0] corresponds to H[j][0]
left shift the elements in H[j] |
s****u
发帖数: 1433 | 18 最少次数是6。 5马一组比完以后，然后第一组最后一名和
其他组第一名再赛一场并胜出。所以第一组就是最快的那5匹。
关键是题目不严谨，可以钻空子。 |
L******i
发帖数: 3027 | 19 你这是文字游戏
照你这么说一次即可
【在 s****u 的大作中提到】
: 最少次数是6。 5马一组比完以后，然后第一组最后一名和
: 其他组第一名再赛一场并胜出。所以第一组就是最快的那5匹。
: 关键是题目不严谨，可以钻空子。
|
L******i
发帖数: 3027 | 20 注意读题
“ in all cases ”
【在 s****u 的大作中提到】
: 最少次数是6。 5马一组比完以后，然后第一组最后一名和
: 其他组第一名再赛一场并胜出。所以第一组就是最快的那5匹。
: 关键是题目不严谨，可以钻空子。
|
|
|
c*******a
发帖数: 1879 | 21 他是耍小聪明， 狗会被虐死他，
题目改了
【在 L******i 的大作中提到】
: 你这是文字游戏
: 照你这么说一次即可
|
s****u
发帖数: 1433 | 22 只比一次无法证明；至少比6次
: 你这是文字游戏
: 照你这么说一次即可
【在 L******i 的大作中提到】
: 注意读题
: “ in all cases ”
|
B*Q
发帖数: 25729 | |
r******u
发帖数: 9 | |
s****u
发帖数: 1433 | 25 擦，被揪出漏洞就改题目？
狗太不要脸了
: 他是耍小聪明， 狗会被虐死他，
: 题目改了
【在 c*******a 的大作中提到】
: 他是耍小聪明， 狗会被虐死他，
: 题目改了
|
b******r
发帖数: 1619 | 26 尼玛你们真的都是博士猴吗，这是典型的SAT数学题啊 |
s******2
发帖数: 1 | 27 类似heap，总保持目前最厉害的五个比赛，塞满五个为止
[在 centralla (central LA) 的大作中提到：]
:There are 25 horses. At a time only 5 horses can run in the single race.
How many minimum races are required in all cases to find the top 5 fastest
:horses? (No timer
:) |
c*******a
发帖数: 1879 | 28 看来你的智商不够去狗家。
可能是混进去的。
【在 s******2 的大作中提到】
: 类似heap，总保持目前最厉害的五个比赛，塞满五个为止
: [在 centralla (central LA) 的大作中提到：]
: :There are 25 horses. At a time only 5 horses can run in the single race.
: How many minimum races are required in all cases to find the top 5 fastest
: :horses? (No timer
: :)
|
L******i
发帖数: 3027 | 29 我觉得他说的有道理啊
你说几次？
【在 c*******a 的大作中提到】
: 看来你的智商不够去狗家。
: 可能是混进去的。
|
s******2
发帖数: 1 | 30 淡，如何证明第一组四匹比别的二十匹马快
[在 sususu (史上最) 的大作中提到：]
:最少次数是6。 5马一组比完以后，然后第一组最后一名和
:其他组第一名再赛一场并胜出。所以第一组就是最快的那5匹。
:关键是题目不严谨，可以钻空子。 |
|
|
s****u
发帖数: 1433 | 31 算了。我帮你们一下，一共7匹马，比几次啊？
算明白了，就知道25匹怎么算了 |
s****u
发帖数: 1433 | 32 嗯，因为第一组是最后一名参赛。
: 淡，如何证明第一组四匹比别的二十匹马快
: [在 sususu (史上最) 的大作中提到：]
: :最少次数是6。 5马一组比完以后，然后第一组最后一名和
: :其他组第一名再赛一场并胜出。所以第一组就是最快的那5匹。
: :关键是题目不严谨，可以钻空子。
【在 s******2 的大作中提到】
: 淡，如何证明第一组四匹比别的二十匹马快
: [在 sususu (史上最) 的大作中提到：]
: :最少次数是6。 5马一组比完以后，然后第一组最后一名和
: :其他组第一名再赛一场并胜出。所以第一组就是最快的那5匹。
: :关键是题目不严谨，可以钻空子。
|
s*****V
发帖数: 21731 | 33 10次把，第一个分５组跑一次，然后取每组最快跑一次，最快的竟级，然后把该组下一
名加进来赛。以此类推。这是基本解，但是似乎不是最优。
【在 s****u 的大作中提到】
: 算了。我帮你们一下，一共7匹马，比几次啊？
: 算明白了，就知道25匹怎么算了
|
L******i
发帖数: 3027 | |
T****t
发帖数: 11162 | 35 总共需要10场。
相先分5组， 先比赛。 然后第一名比赛， 如果胜就出线。
剩下的4只和出线那组的下一名比赛。
连续5场， 也就出了这5只了。
: 如果前5名都在第一组呢？
【在 L******i 的大作中提到】
: 如果前5名都在第一组呢？
|
L******i
发帖数: 3027 | 36 我早就前面说了10次了
code都写完了
现在讨论的是 有没有更优解
目前看没有
【在 T****t 的大作中提到】
: 总共需要10场。
: 相先分5组， 先比赛。 然后第一名比赛， 如果胜就出线。
: 剩下的4只和出线那组的下一名比赛。
: 连续5场， 也就出了这5只了。
:
:
: 如果前5名都在第一组呢？
:
|
d**s
发帖数: 4741 | 37 这个是对的 网上的答案都不对
【在 T****t 的大作中提到】
: 总共需要10场。
: 相先分5组， 先比赛。 然后第一名比赛， 如果胜就出线。
: 剩下的4只和出线那组的下一名比赛。
: 连续5场， 也就出了这5只了。
:
:
: 如果前5名都在第一组呢？
:
|
s****u
发帖数: 1433 | 38 你摸到门了。如果要求全适应，需要20次才可以保证确定。
: 如果前5名都在第一组呢？
【在 L******i 的大作中提到】
: 我早就前面说了10次了
: code都写完了
: 现在讨论的是 有没有更优解
: 目前看没有
|
L******i
发帖数: 3027 | 39 你丫不是向来牛b哄哄的吗？
删帖干嘛？
发信人: LiYaoshi (药师——泥腿子五毛一名), 信区: Military
标 题: Re: 狗家面试题目
发信站: BBS 未名空间站 (Tue Apr 24 21:38:31 2018, 美东)
如果前5名都在第一组呢？
【在 d**s 的大作中提到】
: 这个是对的 网上的答案都不对
|
L******i
发帖数: 3027 | 40 别跳大仙了
我前面代码都写好了
你们这群码农效率还不如我这物理千老
【在 s****u 的大作中提到】
: 你摸到门了。如果要求全适应，需要20次才可以保证确定。
:
:
: 如果前5名都在第一组呢？
:
|
|
|
s****u
发帖数: 1433 | 41 10次不够，信不信？
: 我早就前面说了10次了
: code都写完了
: 现在讨论的是 有没有更优解
: 目前看没有
【在 L******i 的大作中提到】
: 别跳大仙了
: 我前面代码都写好了
: 你们这群码农效率还不如我这物理千老
|
a****r
发帖数: 12375 | 42 李药师你是湖南哪的？
别跳大仙了
我前面代码都写好了
你们这群码农效率还不如我这物理千老
【在 L******i 的大作中提到】
: 别跳大仙了
: 我前面代码都写好了
: 你们这群码农效率还不如我这物理千老
|
d**s
发帖数: 4741 | 43 我被网上的答案误导了 结果发现还是最初的想法正确
【在 L******i 的大作中提到】
: 你丫不是向来牛b哄哄的吗？
: 删帖干嘛？
: 发信人: LiYaoshi (药师——泥腿子五毛一名), 信区: Military
: 标 题: Re: 狗家面试题目
: 发信站: BBS 未名空间站 (Tue Apr 24 21:38:31 2018, 美东)
: 如果前5名都在第一组呢？
|
z*****g
发帖数: 75 | |
T****t
发帖数: 11162 | 45 10次有点多，第七次后 关键后面三只在陪跑。
【在 L******i 的大作中提到】
: 我早就前面说了10次了
: code都写完了
: 现在讨论的是 有没有更优解
: 目前看没有
|
s*****V
发帖数: 21731 | 46 有更好的办法，８次就够了，方法如下
第６次，是1.1, 2.1, 3.1, 4.1, 5.1 赛跑，假设1.1胜出
第７次，是1.2, 1.3, 2.1, 2.2, 3.1 赛跑，这样可以保证一次性出来２个
第８次，把剩下最快的集中赛一次，决出前两名。这个似乎要仔细讨论一下，但是应该
可以。
【在 d**s 的大作中提到】
: 我被网上的答案误导了 结果发现还是最初的想法正确
|
L******i
发帖数: 3027 | 47 我是湖南韶山冲的
【在 a****r 的大作中提到】
: 李药师你是湖南哪的？
:
: 别跳大仙了
: 我前面代码都写好了
: 你们这群码农效率还不如我这物理千老
|
T****t
发帖数: 11162 | 48 a1 a2 a3 a4 a5
b1 b2 b3 b4 b5
c1 c2 c3 c4 c5
d1 d2 d3 d4 d5
e1 e2 e3 e4 e5
这个是前5组比赛的， 应该是没问题的。 |
b*********r
发帖数: 44 | 49 Corrigir
8th: same as 7th except changing row indexes.
【在 s*****V 的大作中提到】
: 有更好的办法，８次就够了，方法如下
: 第６次，是1.1, 2.1, 3.1, 4.1, 5.1 赛跑，假设1.1胜出
: 第７次，是1.2, 1.3, 2.1, 2.2, 3.1 赛跑，这样可以保证一次性出来２个
: 第８次，把剩下最快的集中赛一次，决出前两名。这个似乎要仔细讨论一下，但是应该
: 可以。
|
T****t
发帖数: 11162 | 50
第七次 有些无用信息比如1.2 1.3 以及 2.1， 2.2
【在 s*****V 的大作中提到】
: 有更好的办法，８次就够了，方法如下
: 第６次，是1.1, 2.1, 3.1, 4.1, 5.1 赛跑，假设1.1胜出
: 第７次，是1.2, 1.3, 2.1, 2.2, 3.1 赛跑，这样可以保证一次性出来２个
: 第８次，把剩下最快的集中赛一次，决出前两名。这个似乎要仔细讨论一下，但是应该
: 可以。
|
|
|
h*****n
发帖数: 389 | |
T****t
发帖数: 11162 | 52 我觉得第6次可以用上a3,b3,c3,d3和e3
这样b3,b4,b5,c3,c4,c5,d3,d4,d5,e3,e4,e5 就直接被淘汰了。
剩下 a1 a2, a3,a4, a5
b1,b2
c1,C2
d1,d2
e1, e2 |
L******i
发帖数: 3027 | 53 假设第7次选中了2.1，2.2
又假设2.3, 2.4是剩下最快的
怎么办？
【在 s*****V 的大作中提到】
: 有更好的办法，８次就够了，方法如下
: 第６次，是1.1, 2.1, 3.1, 4.1, 5.1 赛跑，假设1.1胜出
: 第７次，是1.2, 1.3, 2.1, 2.2, 3.1 赛跑，这样可以保证一次性出来２个
: 第８次，把剩下最快的集中赛一次，决出前两名。这个似乎要仔细讨论一下，但是应该
: 可以。
|
L******i
发帖数: 3027 | 54 好像有一定道理
【在 b*********r 的大作中提到】
: Corrigir
: 8th: same as 7th except changing row indexes.
|
y****i
发帖数: 2108 | 55 最基本的冒泡排序法吧
任何投机取巧的办法都不行。
【在 T****t 的大作中提到】
: a1 a2 a3 a4 a5
: b1 b2 b3 b4 b5
: c1 c2 c3 c4 c5
: d1 d2 d3 d4 d5
: e1 e2 e3 e4 e5
: 这个是前5组比赛的， 应该是没问题的。
|
y****i
发帖数: 2108 | 56 麻痹我高中学的。后来没有当码农是码农界的损失。
【在 y****i 的大作中提到】
: 最基本的冒泡排序法吧
: 任何投机取巧的办法都不行。
|
s*****V
发帖数: 21731 | 57 淘汰最慢的那个，再加入３匹。2.3, 2.4，肯定加入。
如果最慢的是1.3，则加入4.1, 如果最慢的是3.1, 这４匹跑就可以了
【在 L******i 的大作中提到】
: 假设第7次选中了2.1，2.2
: 又假设2.3, 2.4是剩下最快的
: 怎么办？
|
l****y
发帖数: 4773 | 58 真空中的球形马
【在 B*Q 的大作中提到】
: 妈跑累了
: 速度会不会变？
|
r******i
发帖数: 1445 | 59 冒泡排序法相当于一次只让两只马赛跑。决出前五只需要115次赛跑。
【在 y****i 的大作中提到】
: 最基本的冒泡排序法吧
: 任何投机取巧的办法都不行。
|
m********k
发帖数: 1 | |
|
|
s******2
发帖数: 1 | 61 不用陪跑，每次比较出线马历史上胜过的第二就行了
【在 T****t 的大作中提到】
: 10次有点多，第七次后 关键后面三只在陪跑。
|
L******i
发帖数: 3027 | 62 我来详细论证一下吧
不失一般性 假设第6次赛跑的排名是
1.1， 2.1， 3.1， 4.1， 5.1
下面考虑第2名和第3名花落谁家
可以简单得到 5.2-5.5肯定没戏了
同理，4.1-4.5, 3.2-3.5也没戏了，因为连4.1刚才都没进前3 而3.1刚刚进前3而已
因此只需要比1.2, 1.3, 2.1, 2.2, 3.1来得到第2名和第3名
在比赛第4名和第5名时 可以用同样方法
接下来 只有以下可能性
1.2, 1.3赢，则把1.4，1.5加入第8次跑
1.2, 2.1赢，则把1.3，2.2加入第8次跑
2.1, 3.1赢，则把2.2，3.2加入第8次跑
你还是狠厉害的 想不想读物理博士 我正在招学生呢
【在 s*****V 的大作中提到】
: 有更好的办法，８次就够了，方法如下
: 第６次，是1.1, 2.1, 3.1, 4.1, 5.1 赛跑，假设1.1胜出
: 第７次，是1.2, 1.3, 2.1, 2.2, 3.1 赛跑，这样可以保证一次性出来２个
: 第８次，把剩下最快的集中赛一次，决出前两名。这个似乎要仔细讨论一下，但是应该
: 可以。
|
s******2
发帖数: 1 | 63 1.2和1.3的次序已经决定了，不需要再次比赛，每次比赛应该决定未知的次序
【在 s*****V 的大作中提到】
: 有更好的办法，８次就够了，方法如下
: 第６次，是1.1, 2.1, 3.1, 4.1, 5.1 赛跑，假设1.1胜出
: 第７次，是1.2, 1.3, 2.1, 2.2, 3.1 赛跑，这样可以保证一次性出来２个
: 第８次，把剩下最快的集中赛一次，决出前两名。这个似乎要仔细讨论一下，但是应该
: 可以。
|
m****o
发帖数: 4654 | 64 老将果然个个智商超群
哈哈哈
: 25匹马
: 5匹一赛
: 5次呗
: 每次取第一名
: How
: timer
【在 U***r 的大作中提到】
: 傻逼
: 你智商基本为零
: 题目说了最少次数
|
y****i
发帖数: 2108 | 65 冒泡排序变种。
每次跑5匹，取前4位，淘汰最后一位，需要21次后得到最快的4匹。
剩下的21匹马，每次跑5匹，取第一位，淘汰掉最后4位，需要跑5次。得到第五快的马。
【在 r******i 的大作中提到】
: 冒泡排序法相当于一次只让两只马赛跑。决出前五只需要115次赛跑。
|
L******i
发帖数: 3027 | 66 “1.2, 2.1赢，则把1.3，2.2加入第8次跑”
这个还得再斟酌下
【在 L******i 的大作中提到】
: 我来详细论证一下吧
: 不失一般性 假设第6次赛跑的排名是
: 1.1， 2.1， 3.1， 4.1， 5.1
: 下面考虑第2名和第3名花落谁家
: 可以简单得到 5.2-5.5肯定没戏了
: 同理，4.1-4.5, 3.2-3.5也没戏了，因为连4.1刚才都没进前3 而3.1刚刚进前3而已
: 因此只需要比1.2, 1.3, 2.1, 2.2, 3.1来得到第2名和第3名
: 在比赛第4名和第5名时 可以用同样方法
: 接下来 只有以下可能性
: 1.2, 1.3赢，则把1.4，1.5加入第8次跑
|
a********t
发帖数: 4508 | 67 马跑多了会不会累啊？
How
【在 c*******a 的大作中提到】
: There are 25 horses. At a time only 5 horses can run in the single race. How
: many minimum races are required in all cases to find the top 5 fastest
: horses? (No timer
: )
|
s******2
发帖数: 1 | 68 太多的redundant order了，用最少的比较来求前五
马。
【在 y****i 的大作中提到】
: 冒泡排序变种。
: 每次跑5匹，取前4位，淘汰最后一位，需要21次后得到最快的4匹。
: 剩下的21匹马，每次跑5匹，取第一位，淘汰掉最后4位，需要跑5次。得到第五快的马。
|
n******i
发帖数: 1 | 69 你就别出丑了
[在 yakexi (亚克西) 的大作中提到：]
:冒泡排序变种。
:每次跑5匹，取前4位，淘汰最后一位，需要21次后得到最快的4匹。
:剩下的21匹马，每次跑5匹，取第一位，淘汰掉最后4位，需要跑5次。得到第五快的马
。 |
b*********r
发帖数: 44 | 70 9，你那个算法里能省的也就是排名2和3只要1次race. 决定4和5老老实实一个一个比
【在 L******i 的大作中提到】
: “1.2, 2.1赢，则把1.3，2.2加入第8次跑”
: 这个还得再斟酌下
|
|
|
B*Q
发帖数: 25729 | 71 这个答案可以进微软
【在 s*****V 的大作中提到】
: 10次把，第一个分５组跑一次，然后取每组最快跑一次，最快的竟级，然后把该组下一
: 名加进来赛。以此类推。这是基本解，但是似乎不是最优。
|
m********k
发帖数: 1 | 72 这个答案因该在第10min的时候想出来 再花5-10优化
跟面试官慢慢讨论优化 然后这是第一问
就是进狗的答案lol
: 这个答案可以进微软
【在 B*Q 的大作中提到】
: 这个答案可以进微软
|
B*Q
发帖数: 25729 | 73 确实
一上来就给正确答案的
俺一般毙掉
除非是好看的美美
【在 m********k 的大作中提到】
: 这个答案因该在第10min的时候想出来 再花5-10优化
: 跟面试官慢慢讨论优化 然后这是第一问
: 就是进狗的答案lol
:
:
: 这个答案可以进微软
:
|
m********e
发帖数: 177 | 74 这题看你怎么理解了。如果minimum是修饰all cases，即求required number of races
in all cases的最小值，那么六次显然是对的。
不过这类题的本意肯定是找出minimun required to handle all cases
更神奇的是，这题按照语法，应该是理解成all case所有最小race number的合集 |
L******i
发帖数: 3027 | 75 你丫这么聪明
应该是top2毕业的吧
【在 s*****V 的大作中提到】
: 淘汰最慢的那个，再加入３匹。2.3, 2.4，肯定加入。
: 如果最慢的是1.3，则加入4.1, 如果最慢的是3.1, 这４匹跑就可以了
|
m********k
发帖数: 1 | 76 你去狗家做题第一步就是确认题目
瞎做一通直接毙掉
races
【在 m********e 的大作中提到】
: 这题看你怎么理解了。如果minimum是修饰all cases，即求required number of races
: in all cases的最小值，那么六次显然是对的。
: 不过这类题的本意肯定是找出minimun required to handle all cases
: 更神奇的是，这题按照语法，应该是理解成all case所有最小race number的合集
|
m********e
发帖数: 177 | 77 它这题确实写的乱七八糟，但是你去面试、指出这个有offer拿？还是像板上众将，按
它最希望考验的技能去表现，才是正道。
: 你去狗家做题第一步就是确认题目
: 瞎做一通直接毙掉
: races
【在 m********k 的大作中提到】
: 你去狗家做题第一步就是确认题目
: 瞎做一通直接毙掉
:
: races
|
s**s
发帖数: 260 | 78 1. 25 分成 5 组， H[5][5],先赛出每组排名。
2. 5组 第一名 赛一次，得第一的组定为 A组,第二的组 B,以此类推。
3. E组只留第一名，后四名淘汰， D组只留一，二名，后三名淘汰， C组留前三，B组
留前四， A组全留 （共15马， 淘汰10 马）
4. 每组最后一名 赛一次， 胜者是变成E组第一.其它淘汰 （剩11马）
5. 此时每组最后一名再赛一次， 胜者第一变为D组第一，第二为E组第一。后三名淘汰
（剩8马）
6. 此时每组最后一名再赛一次，胜者第一变为C 组第一，第二为D组第一, 第三为E组
第一， 后两名淘汰 （剩6马）
7. 此时每组最后一名再赛一次，胜者第一变为B 组第一，第二为C组第一, 第三为D组
第一， 第四为E组第一。 （剩5 马）
Done. |
B*Q
发帖数: 25729 | 79 作出九次的可以进狗狗
【在 B*Q 的大作中提到】
: 这个答案可以进微软
|
L******i
发帖数: 3027 | 80 你这水平
连中国好幼儿园都不会收啊
【在 s**s 的大作中提到】
: 1. 25 分成 5 组， H[5][5],先赛出每组排名。
: 2. 5组 第一名 赛一次，得第一的组定为 A组,第二的组 B,以此类推。
: 3. E组只留第一名，后四名淘汰， D组只留一，二名，后三名淘汰， C组留前三，B组
: 留前四， A组全留 （共15马， 淘汰10 马）
: 4. 每组最后一名 赛一次， 胜者是变成E组第一.其它淘汰 （剩11马）
: 5. 此时每组最后一名再赛一次， 胜者第一变为D组第一，第二为E组第一。后三名淘汰
: （剩8马）
: 6. 此时每组最后一名再赛一次，胜者第一变为C 组第一，第二为D组第一, 第三为E组
: 第一， 后两名淘汰 （剩6马）
: 7. 此时每组最后一名再赛一次，胜者第一变为B 组第一，第二为C组第一, 第三为D组
|
|
|
B*Q
发帖数: 25729 | 81 做出八次的
进沈锦斌医院
【在 B*Q 的大作中提到】
: 作出九次的可以进狗狗
|
i*****r
发帖数: 105 | 82 8轮。第7轮，1.2,2.2,3.2,4.2,5.1。第8轮，有的比两匹马，有的比三匹，有的比四匹。
: 做出八次的
: 进沈锦斌医院
【在 B*Q 的大作中提到】
: 做出八次的
: 进沈锦斌医院
|
d***u
发帖数: 943 | 83 >= 7
【在 z*****g 的大作中提到】
: 6
|
s**s
发帖数: 260 | 84 那个是从后排除，也可从前面， 都是赛10次
1. 25 分成 5 组， H[5][5],先赛出每组排名。
5. 每组第一名再赛一次， 胜者得最后第三，排除，胜者组第二升为第一
以此类推，得最后第四第五名 |
L******i
发帖数: 3027 | 85 你忘了5.1 也许5.1就是第5快的呢
【在 s*****V 的大作中提到】
: 淘汰最慢的那个，再加入３匹。2.3, 2.4，肯定加入。
: 如果最慢的是1.3，则加入4.1, 如果最慢的是3.1, 这４匹跑就可以了
|
B*Q
发帖数: 25729 | 86 7轮后， 1.2>2.2>3.2>4.2>5.1
加上 2.1>3.1>4.1>5.1
第8轮咋整？
匹。
【在 i*****r 的大作中提到】
: 8轮。第7轮，1.2,2.2,3.2,4.2,5.1。第8轮，有的比两匹马，有的比三匹，有的比四匹。
:
:
: 做出八次的
:
: 进沈锦斌医院
:
|
s*****V
发帖数: 21731 | 87 第八轮有点棘手，比方说要是2.1，3.1赢了咋办， 4.1，5.1，3.2，3.3， 4.2都是前
两名的candidate，看到网上的题目有的是说TOP 3,这个就是7轮。
【在 L******i 的大作中提到】
: “1.2, 2.1赢，则把1.3，2.2加入第8次跑”
: 这个还得再斟酌下
|
s*****V
发帖数: 21731 | 88 你说的这种情形5.1就被淘汰了，因为有一个组有两个入选。
【在 L******i 的大作中提到】
: 你忘了5.1 也许5.1就是第5快的呢
|
L******i
发帖数: 3027 | 89 我不是指我之前的前提下
我是说某种情况下
你前面的解没有考虑5.1啊
【在 s*****V 的大作中提到】
: 你说的这种情形5.1就被淘汰了，因为有一个组有两个入选。
|
d********8
发帖数: 691 | |
|
|
s******2
发帖数: 1 | 91 第七轮必须有5.1，六轮以后，每次都是有当前第五名，和其他组最有希望进前五的比赛
【在 L******i 的大作中提到】
: 你忘了5.1 也许5.1就是第5快的呢
|
d***u
发帖数: 943 | |
B*Q
发帖数: 25729 | 93 你是盛锦斌
但是是对的
匹。
【在 i*****r 的大作中提到】
: 8轮。第7轮，1.2,2.2,3.2,4.2,5.1。第8轮，有的比两匹马，有的比三匹，有的比四匹。
:
:
: 做出八次的
:
: 进沈锦斌医院
:
|
d***u
发帖数: 943 | 94 <=9
very likely 8 but not confirmed yet ...
【在 d***u 的大作中提到】
: <= 10 and >=7
|
B*Q
发帖数: 25729 | 95 8是对的
等俺擦完屁股
在电脑上写一下
【在 d***u 的大作中提到】
: <=9
: very likely 8 but not confirmed yet ...
|
j*****p
发帖数: 24000 | 96 5次以后，分出1，2，3，4，5个组
每个组第一编成一个组比，就得到最快的马
然后得出最慢的那个组，然后把那个组可以直接去掉，if那个组第一都是垫底的话
我这个思路应该对，不过没时间一个一个排列 |
S****8
发帖数: 1 | |
i*****r
发帖数: 105 | 98 感觉可以。没有彻底验证。不过这棵树有些偏。浪费了一些机会。也许第七轮应该是:1
.3,2.2,3.2,4.2,5.1。
: 7轮后， 1.2
【在 B*Q 的大作中提到】
: 8是对的
: 等俺擦完屁股
: 在电脑上写一下
|
B*Q
发帖数: 25729 | 99 你原来的思路是对的
【在 i*****r 的大作中提到】
: 感觉可以。没有彻底验证。不过这棵树有些偏。浪费了一些机会。也许第七轮应该是:1
: .3,2.2,3.2,4.2,5.1。
:
:
: 7轮后， 1.2
|
B*Q
发帖数: 25729 | 100 见俺专贴详解
【在 B*Q 的大作中提到】
: 你原来的思路是对的
|
|
|
i*****r
发帖数: 105 | 101 这样更容易。最坏的情况是，1.3>2.2。只要在第八轮，1.4,1.5,2.2,3.1。不管怎么样
，unbalance还很大，所以我估计6×6的矩阵，也可能只需要九次。
: 你原来的思路是对的
: :1
【在 B*Q 的大作中提到】
: 见俺专贴详解
|
d***u
发帖数: 943 | 102 confirm <=8.
【在 d***u 的大作中提到】
: <=9
: very likely 8 but not confirmed yet ...
|
B*Q
发帖数: 25729 | 103 嗯
推广一下
搞出个 N X N 的
就牛轰轰了 |
d***u
发帖数: 943 | 104 第七场有点绕，认清是有序列就明白了。难度不算太大。
【在 d***u 的大作中提到】
: confirm <=8.
|
s******2
发帖数: 1 | 105 第八轮4.1和3.2没出局啊，应该比较1.3，2.3，3.2和4.1，每次都是争五
【在 i*****r 的大作中提到】
: 这样更容易。最坏的情况是，1.3>2.2。只要在第八轮，1.4,1.5,2.2,3.1。不管怎么样
: ，unbalance还很大，所以我估计6×6的矩阵，也可能只需要九次。
:
:
: 你原来的思路是对的
:
: :1
:
|
V****n
发帖数: 651 | 106 任选5马一组，五组赛5场
第6场：五组取头名赛一场，名次设定A>B>C>D>E
第7场：取E组第一名E1与其它四组第二A2,B2,C2,D2赛一场，如E1第一名则无需再赛。
最快5马为A1,B1,C1,D1,E1。如E1为第2名亦不用赛，最快5马为A1,B1,C1,D1和第七场第
1名。
第8场：如第7场E1为第3名，多种方式可选，比如取第七场头两名跟B1,C1,D1再赛一场
，前4加A1为最快5马。
如第7场E1为第4名，取第7场2，3名与B1,C1,D1赛一场。
如第7场E1为第5名，这是最复杂的情况。仍取第7场2，3名与B1,C1,D1赛一场。
如前3名仍为B1>C1>D1,则最快5马为A1,B1,C1,D1,和第7场头名。
如前3名为B1>C1>第7场2名，则最快5马为A1>B1>C1>第7场头名>第7场2名
前3名为B1>第7场2名>第7场3名可能性不存在，因为B1>第7场2名>第7场3名>C1>D1,第7
场2,3名不可能为C2,D2因C2
前3名为第7场2，3，4名可能性亦不存在，理由类似上面。
How
【在 c*******a 的大作中提到】
: There are 25 horses. At a time only 5 horses can run in the single race. How
: many minimum races are required in all cases to find the top 5 fastest
: horses? (No timer
: )
|
B*Q
发帖数: 25729 | 107 不对
如果最快的马全在第一组呢？
【在 V****n 的大作中提到】
: 任选5马一组，五组赛5场
: 第6场：五组取头名赛一场，名次设定A>B>C>D>E
: 第7场：取E组第一名E1与其它四组第二A2,B2,C2,D2赛一场，如E1第一名则无需再赛。
: 最快5马为A1,B1,C1,D1,E1。如E1为第2名亦不用赛，最快5马为A1,B1,C1,D1和第七场第
: 1名。
: 第8场：如第7场E1为第3名，多种方式可选，比如取第七场头两名跟B1,C1,D1再赛一场
: ，前4加A1为最快5马。
: 如第7场E1为第4名，取第7场2，3名与B1,C1,D1赛一场。
: 如第7场E1为第5名，这是最复杂的情况。仍取第7场2，3名与B1,C1,D1赛一场。
: 如前3名仍为B1>C1>D1,则最快5马为A1,B1,C1,D1,和第7场头名。
|
d*******3
发帖数: 3 | 108 “第8场：如第7场E1为第3名，多种方式可选，比如取第七场头两名跟B1,C1,D1再赛一场
，前4加A1为最快5马。”
这段就错了，假设第7场头两名是A2,B2, 而第8场没有参赛的A3可能是所有马里第三快
，按你的方法就没选出来。
【在 V****n 的大作中提到】
: 任选5马一组，五组赛5场
: 第6场：五组取头名赛一场，名次设定A>B>C>D>E
: 第7场：取E组第一名E1与其它四组第二A2,B2,C2,D2赛一场，如E1第一名则无需再赛。
: 最快5马为A1,B1,C1,D1,E1。如E1为第2名亦不用赛，最快5马为A1,B1,C1,D1和第七场第
: 1名。
: 第8场：如第7场E1为第3名，多种方式可选，比如取第七场头两名跟B1,C1,D1再赛一场
: ，前4加A1为最快5马。
: 如第7场E1为第4名，取第7场2，3名与B1,C1,D1赛一场。
: 如第7场E1为第5名，这是最复杂的情况。仍取第7场2，3名与B1,C1,D1赛一场。
: 如前3名仍为B1>C1>D1,则最快5马为A1,B1,C1,D1,和第7场头名。
|
e*g
发帖数: 4981 | 109 先比赛ABCDE组
然后5个第一名一组比，5个第二名一组比
如果这两个组的头名之前在同一组
那就把这组第三名和这两个组的前两名一起比
否则就把头名组的前三名和次名组的前两名一起比 |
B*Q
发帖数: 25729 | 110 看不懂
写个a.1 b.2吧
【在 e*g 的大作中提到】
: 先比赛ABCDE组
: 然后5个第一名一组比，5个第二名一组比
: 如果这两个组的头名之前在同一组
: 那就把这组第三名和这两个组的前两名一起比
: 否则就把头名组的前三名和次名组的前两名一起比
|
|
|
e*g
发帖数: 4981 | 111 看错题了！
【在 B*Q 的大作中提到】
: 看不懂
: 写个a.1 b.2吧
|
p******g
发帖数: 8316 | 112 所以说压根不存在唯一解能涵盖all cases的，必须分开单独讨论
你无论怎么算，总有一款不适用的。
凡是在这默默埋头苦干的，都不是CS科班出身。
【在 B*Q 的大作中提到】
: 不对
: 如果最快的马全在第一组呢？
|
l*w
发帖数: 3758 | 113 先分五组比赛。五场比赛。
第六场比赛，五个第一比赛。，第一名晋级
第七场比赛，上场比赛第一的下一个名词递补比赛。第一晋级。
第八场，上场比赛下一名次递补比赛，第一晋级。
第九第十场同上，最多十场比赛决定。 |
i****o
发帖数: 11 | 114 就是，麻痹撒逼题目，就不能一次跑25匹马呀，非5匹一组想把马累死麼？
非要这样跑，就是个概率问题，找到最快的5匹马。
假定最快的5匹马每组恰好一匹，最少跑5次就行。
最复杂的可能性是最快的5匹马在同一组，算一下该跑几次，如果是n的话，答案就是5
到n之间。
: 所以说压根不存在唯一解能涵盖all cases的，必须分开单独讨论
: 你无论怎么算，总有一款不适用的。
: 凡是在这默默埋头苦干的，都不是CS科班出身。
【在 p******g 的大作中提到】
: 所以说压根不存在唯一解能涵盖all cases的，必须分开单独讨论
: 你无论怎么算，总有一款不适用的。
: 凡是在这默默埋头苦干的，都不是CS科班出身。
|
p******g
发帖数: 8316 | 115 哈哈哈
5
【在 i****o 的大作中提到】
: 就是，麻痹撒逼题目，就不能一次跑25匹马呀，非5匹一组想把马累死麼？
: 非要这样跑，就是个概率问题，找到最快的5匹马。
: 假定最快的5匹马每组恰好一匹，最少跑5次就行。
: 最复杂的可能性是最快的5匹马在同一组，算一下该跑几次，如果是n的话，答案就是5
: 到n之间。
:
:
: 所以说压根不存在唯一解能涵盖all cases的，必须分开单独讨论
:
: 你无论怎么算，总有一款不适用的。
:
: 凡是在这默默埋头苦干的，都不是CS科班出身。
:
|
o****e
发帖数: 417 | 116 这是我老当年招人的标准题目之一，除了这个还有强盗分金子、烧绳子、圆筒水测量等
问题。
看来现在小留素质比不上我们当年了。这个赛马问题是minimum spanning tree的最短
路径的变异题，最好的解题方法是画图加简单逻辑判断 |
