作者FRAXIS (喔喔)
看板Prob_Solve
標題Re: [問題] Google Interview Question (2)
時間Thu Feb 14 21:23:32 2013
※ 引述《pika0923 (宜安)》之銘言：
: 寫了一個 14 races 的作法
: 不知道會不會很難理解
: https://dl.dropbox.com/u/33437124/25th%20car/page1.jpg
: https://dl.dropbox.com/u/33437124/25th%20car/page2.jpg
: 第9和10場是參考原po那篇文的作法
: 然後我不確定14是不是最少的
: 不過我目前能想到的大概就是這樣^^"
我想用Decition Tree來證明這問題的下限。
原本有49台車子，所以總共有49!種可能。
每次比賽只能選7台車，所以每次的結果有7!種可能。
所以這個樹的高度，至少要有log_7! 49!，
如果用ln 49! / ln 7!來算，數字是16.95.....
所以少於17步應該是不可能的..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 24.128.7.79
1F：推 scwg:Output 不是順序, 只是中位數, 49! 個 leaf node 不用全分開 02/14 21:43
2F：→ FRAXIS:也對，所以這Lower Bound不對 02/15 05:41