※ 引述《CEO (少點特寫多點空間)》之銘言： : There is one race ground with 5 race tracks. Each race could only : have one horse running on it when there is a horse race.. When there : are 100 horses and the faster horse always run faster than the slower : horse. if we have to find out the fastest 3 horses out of these 100 : horses, how many races we need to have in this race ground? : 大家想看看嚕~ ：D 順著推文去追了一下這題的歷史。原先好像是Tech_Job板一題NVIDIA面試的考題 後來轉到Inference板，時間是去年。題目是100匹馬，一次只3匹同時跑，因為 餘數問題討論起來比這題複雜。但精神應該一樣的，而且可以講比較細，就先解 冷題一下 以下是closetou板友的解答的附注解囉嗦版(?) 結論是＜100匹/3匹/找前三＞需55次 EDIT: 訂正為54次, closetou原答案正確 方法的精神是聚焦在「全局的第一/二/三名可能在哪裡」為了避免搞混我把冠軍馬命 名為A，第二名= B，第三名= C，以和每一次比賽的1,2,3名區分。 *第一梯 ┌ 33場 ┐+1 * 100= 33x3 +1 剩一匹 1 ..... ↓ 2 ↓ 3 ↓ ↓ *第二梯 ↓ ↓ ┌ 11場 ┐+1 * 33 = 11x3, 1 ..... 2 多的一匹混回來，試煉之。 3 *第三梯 * 11+1 = 4x3 ┌ 4 場 ┐ 1 1 1 1 不難驗證，四匹馬要完全排序起碼要比三次。 2 2 2 2 但，若只是要找四匹中的前兩名，只需要兩次。 3 3 3 3 因此 2 場後 可分出 *王者之梯次(=2場比賽) 1----------> 篤定是馬王A，此時要問，B可能在哪裡？B唯一會被打敗就是跟A分在 2 一組，換句話說A升上來的過程中，牠的下一名都有可能是籤運很衰 3/4 剛好被A幹掉的B。 3/4 另外，可能B從未遇到A，此情況下一路升到王者之梯次的第2名就是B。 這就是上面說只需要比兩次確定前兩名的原因。 可能的B有幾匹？ 若A恰好是第一梯多出來那匹，可能的B = 3匹。若A並不是該匹馬， 則由A一路「產生」出可能的B的"馬"選 = 4匹。 考慮最糟情況4匹 。由這4匹 恰好都曾被A打成第2名的馬 再比2場，以確定前兩名 *決定B之梯次 (=2場比賽) 1' ----------> 我是B 2' 3/4' 3/4' 那C可能在哪？ 結論是C可能是A或B一路升上來不小心幹掉的第2名，要是A曾經淘汰掉B (在同一組)，C還可能極頂倒楣，剛好也在同一組，被擠到第3名。 依照A與B相遇的狀況，可能的C數量不同。可能的C 有: >> B在遇到A之前的手下敗將第2名，可能0或1或2匹。 >> A與B相遇該梯次跟他們同組的第3名。 >> 以及上面的2'。2'洽好是A的手下敗將集合，而且在決定B一戰輸給B，故可能是C。 >> 若A跟B直到王者之梯次才遇到，王者戰中名次懸而未決的2匹馬3/4也都可能是C 這樣一共是6匹馬，考慮最差狀況，還需要3場才能決定其中最快的，即C。 總計 33 + 11 + 4 + 2 + 2 + 3 = 55 一梯 二梯 三梯 王戰 B戰 C戰 這答案我還蠻確定的。 EDIT: 藍底字錯了，>>號第二個與第四個重複計算，最差狀況是5匹馬。 從五匹馬中找最快者只需2場，因此總共是54場才對。 - - - - - - - - - - - - - 100匹/5匹因為除得盡，簡單很多 ┌ 20 場 ┐ 1 .... 2 3 4 5 ┌ 4場 ┐ 1 1 1 1 2 2 2 2 3 3 3 3 ... ┌1場┐ 1 ----------> A 2 3 4 可能的B有3匹，再一場 -----> 決定B 可能的C有2或3匹 (依AB相遇時機而定，參考上題) ，再一場 -----> 決定C 20+4+1+1+1一共27場即可 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.213.88 ※ 編輯: jurian0101 來自: 140.112.213.88 (11/13 20:30)