作者kiedveian (极地之星光)
看板Inference
标题Re: [问题] 一题关於赛马的题目
时间Sun Nov 27 09:10:20 2011
※ 引述《ds0319 (扑扑扑)》之铭言：
: 其实是面试的题目
: 只是我好想知道答案...
: 就是说今天有100只马，要找出最快的前三只
: 但是跑道只有三个，也就是说一次最多三只马下去跑分出胜负
: 快的马永远都会跑的比慢的马快
: 请问最少要跑几轮比赛
我的方法同前推文所写
(33+11+4+1+1) + 2 + 2 = 54次
详细一点为
(33+11+4+1+1) +(1+1)+(1+1)
使用方法为
1.先选出第一名
2.从输给第一名中选第二名
3.从输给第二名中选第三名
使用这个方法必须依序选出一二三名
否则不确定第一名，可能输给第一名的会非常的多
定义a与b ，a为输给第1名的，b为输给第2名的
找出第一名共5个阶段
其中第一阶段的余数并入第3阶段比
100
33....1 a b
11....0 a b
4.....0 a b
1.....1 a
b
1.....0 a
共33+11+4+1+1轮
第5阶段操作的正确的话，可省去第4阶段的b
可想成45阶段选出第一名与第四名，第四名除去、二三名为a
---------------------第5阶段说明分隔线-------------------
情况为第4阶段 胜出1+剩余1
因此还有一个名额
假设当时名次为 123 x ，x为剩余的，3应为第4阶段的b
选出1、3、x当做第5阶段的比赛
名次 1 2 3
i. 1 3 x 名次为123x
j. 1 x 3 名次为1x23 或 12x3
k. x 1 3 名次为x123
i状况下，3会变成第5阶段的 a，因此第4阶段的b可忽略
j或k的状况下，3不可能是第3名，第4阶段的b也可忽略
--------------------说明结束分隔线-----------------------
找出第二名，同等於简化後的原题
由刚产生的5个a下去比
第2阶段与第1阶段的余数比
1.....2 b
1.....0 b
共1+1轮
第三名则为前面产生的b(4-1)+2=5个
比较方法同上
1.....2
1.....0
共1+1轮
(33+11+4+1+1) + 2 + 2 = 54次
以上，欢迎讨论
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.117.117.13
※ 编辑: kiedveian 来自: 59.117.117.13 (11/27 10:10)
1F：→ puzzlez:第二名在其他轮中 不是也有可能是第一名？ 11/27 13:09
是的，但在只要没遇到第一名，会前进到四强
2F：推 closetou:请问你的第二阶段为什麽不是11...1而是11...0 11/27 13:22
因为是33下去分队，第一阶段的余数不包含在内
※ 编辑: kiedveian 来自: 59.117.117.13 (11/27 13:27)
3F：→ puzzlez:终於看懂了0.0....这题出在面试还满过分的 11/27 14:52
4F：→ puzzlez:这个有考虑到 第3名不小心与第1名在一起时被淘汰的情形吗? 11/27 14:56
如果123名同组，取第1名时会将第3名分至b组
如果第1、3名同组而第2名不同组
取第1名时会将第3名分至a组
取第2名时会将第3名分至b组
※ 编辑: kiedveian 来自: 59.117.117.13 (11/27 15:12)
5F：推 closetou:我的方法跟原po略有不同 11/27 15:29
6F：→ closetou:恕小弟无能，研究很久还是看不太懂 11/27 15:29
7F：→ closetou:我的方法po在Tech_Job版，有不一样的地方烦请指正 11/27 15:30
8F：推 puzzlez:哦...原来如此...我没问题了 谢谢 :-) 11/27 16:40