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