1. 首頁
  2. 問答
  3. 如何決定M軌道的N匹馬的等級？

如何決定M軌道的N匹馬的等級？

2011-09-24 50 views
4

提供N匹馬和M（M < = N）的曲目但沒有計時器，所有你可以從一輪獲得的是M馬的順序。至少有多少回合的問題，如果你想獲得所有馬匹的排名？如何決定M軌道的N匹馬的等級？

例如 N=3, M=3, Round=1; N=3, M=2, Round=3; N=4, M=3, Round=3;

圓是什麼，當N = 1000時，M = 3？

來源

2011-09-24 ghostonleft

+3

這是功課？你有什麼嘗試？ –

+0

有趣...三元邏輯的排序算法。 –

+0

這是我在面試中遇到的一個問題，我無法得到一個精確的結果，但只有一個上限，使用合併排序。 – ghostonleft

回答

4

你可以用信息論得到一個下界。

每場比賽都會給你提供log（m！）比特的信息，而你需要log（n！）比特。所以比賽數量的自然下限爲log（n！）/ log（m！）。

來源

2011-09-24 05:40:09

相關問題

 相關問題