Re: [問題] Google Interview Question (2)
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間11年前 (2013/02/14 21:23)推噓1(1推 0噓 1→)留言2則, 2人參與討論串8/9 (看更多)
※ 引述《pika0923 (宜安)》之銘言：
: 寫了一個 14 races 的作法
: 不知道會不會很難理解
: https://dl.dropbox.com/u/33437124/25th%20car/page1.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
推
02/14 21:43, , 1F
02/14 21:43, 1F
→
02/15 05:41, , 2F
02/15 05:41, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 8 之 9 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
