作者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