賽車拼圖

Question

你能幫我解決這個難題，我無法找到一個很好的答案！

有49輛車以獨特的速度競賽。另外還有一個賽道，最多可以有7輛賽車一起參賽。我們需要找到組中第25快的賽車。我們沒有秒錶來衡量時間（所以我們只能測量每輛賽車與其他6輛賽車的相對速度）。什麼是最少的比賽將需要？

Answer 1

嘗試這些算法

http://en.wikipedia.org/wiki/Quick_select

Answer 2

繼Dialecticus一的靈感。分成7個隨機組，然後比賽每組，然後比賽這些組的中位數。這輛車成爲樞軸，我們已經直接或間接地知道它與其他30輛汽車的關係（這是中位數的一個屬性）。所以把它放在resp。其他18場比賽我們需要參加3場比賽，包括主場比賽。在轉動之後，我們最多需要緩行33輛車。繼續。我結束了29場比賽。即使你認爲需要完整的排序，但不是，在17場比賽中有一個下限（真正的下限會更低），這比29小得多。所以我懷疑這不是正確的答案，但由於這一直缺乏任何解決方案，這裏是一個次優的。如果你看看分揀網絡的研究（這個問題一次只限於兩輛車），尋找最佳網絡是困難的，只有非常小的尺寸才能知道最佳網絡，絕對不超過49個。我不知道任何有關7路比較器網絡的研究。

也許一個例子可以提供幫助。比方說，從最慢到最快的車號，並以7x7矩陣排列（任意，因爲我們不知道速度，直到我們比賽）。

 [,1] [,2] [,3] [,4] [,5] [,6] [,7] 
[1,] 34 25 45 43 26 21 13 
[2,] 11 24 2 40 14 30 32 
[3,] 27 19 29 42 4 17 46 
[4,] 15 10 39 33 1 9 5 
[5,] 28 18 41 8 23 20 6 
[6,] 16 3 38 7 12 22 36 
[7,] 31 44 48 35 49 37 47 

然後讓你追我趕列並進行排序根據比賽的結果：根據結果

 [,1] [,2] [,3] [,4] [,5] [,6] [,7] 
[1,] 11 3 2 7 1 9 5 
[2,] 15 10 29 8 4 17 6 
[3,] 16 18 38 33 12 20 13 
[4,] 27 19 39 35 14 21 32 
[5,] 28 24 41 40 23 22 36 
[6,] 31 25 45 42 26 30 46 
[7,] 34 44 48 43 49 37 47 

現在，讓我們的比賽列＃4（中位數），並重新排列列

 [,1] [,2] [,3] [,4] [,5] [,6] [,7] 
[1,] 1 3 9 11 5 7 2 
[2,] 4 10 17 15 6 8 29 
[3,] 12 18 20 16 13 33 38 
[4,] 14 19 21 27 32 35 39 
[5,] 23 24 22 28 36 40 41 
[6,] 26 25 30 31 46 42 45 
[7,] 49 44 37 34 47 43 48 

現在觀察到，中位數的中值（元素[4,4]）比上述任何車比低於任何汽車和右（這是中位數的中值的一個屬性）更快和左，慢。對於其他車型（左下角和右上角），我們不知道，所以我們需要一次對抗[4,4]和6號賽車（3場比賽）。現在我們觀察到26輛車比[4,4]慢，因此中位數必須是其中的一輛。無需進一步比賽任何其他人。現在用這26輛車重複這個過程。

Answer 3

http://www.sureinterview.com/shwqst/1062001

回合一個

1. （7個種族）除以汽車分爲7組，並獲得每個組內的順序。
2. （1場比賽）參加7中位數並獲得訂單。找到中位數（表示爲o）。在以下示例中，它是34.
3. （3個種族）查找中位數的中位數。從左下角（25〜33）和右上角（13〜21）取6個元素並與o（34）競賽。經過3輪後，我們知道整組中位數的中位數。最好的情況是o是全球中位數（最快的25位）。最糟糕的情況是o是第16或第34最快。

該示例顯示了一種可能的最壞情況。

1 2 3 4 13 14 15 <- group 1 
5 6 7 8 16 17 18 
9 10 11 12 19 20 21  ... 
22 23 24 34 35 36 37 
25 26 27 38 39 40 41 <- group 5 
28 29 30 42 43 44 45 <- group 6 
31 32 33 46 47 48 49 <- group 7 

第二輪

我們要找到其他位數的排名在一個二進制搜索。

1. （3場比賽）挑中位數小於34，即12。與左下角和右上角的賽車比賽。在3場比賽後，我們知道它的排名是12.

現在，這兩個中間值之間的差距最多爲21，如本例所示。

第三輪

重新排列21輛（> 12和< 34）如下。

13 14 15 <- group 1 
16 17 18 
19 20 21  ... 
22 23 24 
25 26 27 <- group 5 
28 29 30 <- group 6 
31 32 33 <- group 7 

每行仍然排序。

1. （1個種族）再次找到中位數的中位數，這是23
2. （1種族）找到它的排名。在這一步之後，我們知道前一步的賽車肯定排名23。
3. （1比賽）與二進制搜索相似，請檢查另一箇中位數的排名，29.
4. （1比賽）將所有賽車排序在23〜29（不含）之間。發現第25快的汽車。

所以最多需要18場比賽才能拿到第25輛最快的賽車。

Answer 4

難道你不能通過確定汽車的確切位置來反覆劃分池嗎？

隨機挑選一輛汽車，轉動 跑過其他48輛賽車，以6輛賽車組成的賽車對陣中軸車 您現在知道了轉向車的確切位置。

現在在你知道包含位置25的部分上運行相同的過程。如果剩餘分區中的元素少於7個，則很容易確定。

這種情況的最壞情況是非常可怕的，但可以通過以某種半智能方式選擇連續的樞軸來緩解。

Answer 5

我有一個解決方案，只需要17場比賽。

首先，讓我解釋一個簡單的解決方案，需要32場比賽。將汽車分成7組，每組7人，每組參加比賽（7場比賽）。重複25次：從每組中選出最快的剩餘賽車，並將其輸入比賽，並將優勝者放在一邊（25場比賽）。 25場比賽中的第一場決定最快的整車（＃1），第二場比賽決定＃2，依此類推。

現在只有17場比賽的解決方案：

我們的策略是首先確定24輛最快的汽車（讓我們稱這些車「迅速」）。然後我們會發現其餘的最快（＃25）。

隨機放置在一個7x7格子的汽車，並比賽每一排（7場比賽）。 然後，從每場比賽（第8場比賽）中選出第3名參加比賽的選手，並按第3名選手的速度排序。

於是，經過8場比賽，我們有這樣的：

每個網格代表的汽車。箭頭指向速度更快的汽車。請注意，箭頭是傳遞的。

我們已經能夠識別8 「迅速」 汽車：

我們怎麼知道他們是迅速？看看藍色的'x'。只有23輛車可能比它快（不在右下角的5x5）。所以，這當然是「快速」。您可以驗證其他x的。

我們已經確定了24輛「快速」轎車中的8輛。從未來的考慮中刪除這8個。我們現在正在尋找其餘車中最快的16輛。我們七組的尺寸分別爲4,4,5,7,7,7和7.（對於圖表，每當我們拆下一輛車時，讓我們將剩餘的汽車向左滑動。）

讓我們比賽每組的第二快的剩餘賽車，並相應地排序（第9場比賽）。和以前一樣，我們可以找出4輛汽車這當然是16個最快（即「快速」）中：

我的電池，其中，除去汽車可能是彩色的，但這並沒有影響呢。
我們已經確定了12輛「快速」轎車。除去「快速」汽車，我們尋找其餘汽車中最快的12輛。我們的團隊規模在2到7之間。 讓我們參加每組的第二快的剩餘賽車，並相應地對行進行排序（第10場比賽）。我們確定了2輛它們中的12個發展最快（即「快速」）：（10「迅速」汽車保持）

我們可以重複前面的步驟兩次（第11和12場比賽） 。每次我們移除2輛車。但是請注意，行/組可能有0或1輛汽車。如果它有1輛車，我們會比賽，而不是「剩下的第二快」。如果這輛車贏了，我們知道它是「快速」，以及下一個最快的第二名車。無論如何，我們確定2輛「快速」轎車。 （仍然有6輛「快速」汽車。）

在12場比賽之後，我們確定並移除了18輛「快速」賽車。我們需要確定剩餘的6輛「快速」轎車。

現在，讓我們簡單地比賽每組中最快的剩餘賽車（第13場比賽），並相應地對行進行排序。獲勝者是「快速」。還剩5個。

最後一場比賽之後，只有2輛車可能是最快的剩餘賽車。藍色O公司：

此外，第二剩餘最快的車或者是一個藍色的「O」或綠色的「O」。讓我們參加這5輛賽車（第14場比賽），前兩名車手肯定是「快速」。還剩3個。

讓我們重複最後兩步/場比賽，以確定最後的3輛快速汽車（15日和16日的比賽）。

因此，我們已經確定24 「快捷」 的汽車。剩下最快的車必須是第25快。我們可以通過簡單地在每排/組（第17場比賽）中競速最快的賽車來找到這款車。

Answer 6

你總是可以在8場比賽中解決這個問題...... 讓我們拿一個樞軸車說Car1，然後在8場比賽中與所有其他賽車比賽，並將其他車的相對速度與Car1進行比較。 可以說下面給出結果：讀汽車＃（相對速度分享幫助）

---

賽事1：Car1-（0），CAR2 - （+ 10），的Car3（5），CAR4（+ （0），Car8 - （+ 10），Car9（+5），Car10（+7），Car5（-3），Car6（-4），Car7（+1）

第2場：Car1- ），Car11（-3），Car12（-4），Car13（+1）

第3場：Car1-（0），Car14-（+11），Car15（+4），Car16（+6） ，Car17（-4），Car18（-10），Car19（+2）

第4場：Car1-（0），Car20（+9），Car21（+3），Car22（+5），Car23 （-5），Car24（-1 1），Car25（+3）

第5場：Car1-（0），Car26-（+8），Car27（+2），Car28（+6），Car29（-6），Car30（-12） ），Car31（+4）

第6場：Car1-（0），Car32-（+7），Car33（+1），Car34（+3），Car35（-7），Car36（-13） ，Car37（+5）

第7場：Car1-（0），Car38-（+ 6），Car39（-1），Car40（+2），Car41（-8），Car42（-14）， Car43（+6）

第8場：Car1-（0），Car44-（+5），Car45（-2），Car46（+1），Car47（-9），Car48（-15），Car49 （7）

仙ce Car1是轉向車，每輛賽車的速度在所有比賽中都是一致的，我們可以將所有的結果集中在一起。

如果排序的相對速度（WRT CAR1），你可以找出25最快的車。