Re: [新聞] 大企業面試題目古怪 考倒求職者！

[Favonia (小西風最乖了*^^*)]

發現到沒有人給賽馬解答，所以來分享一下～








































※ 引述《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)
推 joeyeh:e1=d1=c1>b1>a1,e2=d2=c2>b2>a2,...last round?
→ squirrel1085:樓上是要問什麼@@?
推 joeyeh:必然有一種結果無法選出前三? 什麼樣的結果?
→ Favonia:必然有一「組」（中間有比較過）至少有兩批馬。如果這組馬
→ Favonia:第一名是全部的第一名，那就無法區辨這組馬的第二名（們）
→ Favonia:是不是在前三名之列。不好意思我寫得太簡潔了 orz
推 joeyeh:但25匹能抽中5批全是第一 把這群列為前三不失有大過錯(亂講
推 joeyeh:把圓跑道切成兩半一次10匹異向對衝(賽馬品質落差不大)