字體:小 中 大 | |
|
|||||||||||||||||||||||||
2013/05/02 18:13:59瀏覽411|回應0|推薦3 | |||||||||||||||||||||||||
聽說這是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. 後記 : 覺得沒找到最好的解法, 等下週考完試再來想, 不然想到半夜居然睡不著.. |
|||||||||||||||||||||||||
( 知識學習|考試升學 ) |