聽說這是Google 的口試題目 :

有25隻馬, 每次競賽只可以跑最多5隻馬, 沒有馬表下, 最少要幾次才可以找出最快的5隻馬?

原文 : There are 25 horses. At a time only 5 horse can run in the single race. How many minimum races are required to find the top 5 fastest horses? Please explain your answer. (There is no timer.)

網路上有很多解法, 7次是最多的說法, 但我套入真實數字時都無法過關, 我自己的解法是 9次.

將25隻馬分成 5 個 group, 在 5 次競賽後找出各組第1,假設得到 a1, b1, c1, d1, e1

所以第 6次是找出  a1, b1, c1, d1, e1 的前兩名 假設成績是 : 

a1> b1>c1>d1> e1, 則a1, b1 為 top 2, 將top2 擺一旁然後取最快的 a1的下兩階及次快 b1 的次排名來進行次輪競賽, e1 為 bottom 1, e1不再參加競賽

第 7次找出 a2, a3, b2, c1, d1 中前兩名為全部的第3, 4名,  假設成績是 :

c1>d1>b2>a2>a3, 則c1, d1為 top 2, 即第3, 4名, 將top2 擺一旁然後取最快的 c1的下兩階及次快 d1 的次排名來進行次輪競賽,a3 為 bottom 1, 不再參加競賽

第8次找出 a2, b2, c2, c3, d2 誰是第5, 6名, 假設成績是 :

b2>c2>a2>d2>c3, 則b2, c2為 top 2, 即第5, 6名,接下只要找出第 6 名就可以解出前5名 

第9次找出'去掉第1名的 a1', 在  b1, b2, c1, c2, d1中有一個是第6名, 假設成績是 :

b1>c1>d1>b2>c2 得 c2 為第 6 名. 故得最快的5隻馬為a1,b1,b2,c1,d1.

後記 : 覺得沒找到最好的解法, 等下週考完試再來想, 不然想到半夜居然睡不著..