※ 引述《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)