作者Favonia (小西风最乖了*^^*)
看板puzzle
标题Re: [新闻] 大企业面试题目古怪 考倒求职者！
时间Sun Jul 3 13:12:49 2011
发现到没有人给赛马解答，所以来分享一下～
※ 引述《puzzlez (帕索)》之铭言：
: 「有五个人，五人的年龄都不同，一起走进一家酒吧内围着一张圆桌子坐下来，他们按年
: 龄大小依次序坐下来的可能性有多大？」
n!/(2n)
: 「二十五匹马，没有计时器，有五条赛道。你如何用最少的比赛场数，去找出跑得最快的
: 三匹马？」（facebook面试题目）
最佳解 7.
总共有 25 匹马，每次比较最多只能多知道 4 个最简大小关系（我自己乱发明的词）。例如
第一场是 a,b,c,d,e 就知道 e > d > c > b > a. 可以画成一个 directed acyclic graph.
至少要知道 24 个最简大小关系（因为连通图至少要 n-1 边）所以至少要 6 场。假如 6 场
可以，最後一场一定是 5 个完全独立的组各派代表出来，必然有一种结果会无法选出前三，
所以至少要 7 场。
: 「你爬楼梯，每次走一级或两级，那道楼梯有n那麽多级，你有甚麽与别不同的方法去爬
: ？」（Google）
fib n = theta (phi^n)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.39
※ 编辑: Favonia 来自: 140.112.30.39 (07/03 13:39)
1F：推 joeyeh:e1=d1=c1>b1>a1,e2=d2=c2>b2>a2,...last round? 07/03 22:37
2F：→ squirrel1085:楼上是要问什麽@@? 07/03 23:45
3F：推 joeyeh:必然有一种结果无法选出前三? 什麽样的结果? 07/04 01:24
4F：→ Favonia:必然有一「组」（中间有比较过）至少有两批马。如果这组马 07/04 02:08
5F：→ Favonia:第一名是全部的第一名，那就无法区辨这组马的第二名（们） 07/04 02:09
6F：→ Favonia:是不是在前三名之列。不好意思我写得太简洁了 orz 07/04 02:10
7F：推 joeyeh:但25匹能抽中5批全是第一 把这群列为前三不失有大过错(乱讲 07/04 06:58
8F：推 joeyeh:把圆跑道切成两半一次10匹异向对冲(赛马品质落差不大) 07/04 07:03