64匹马8赛道问题

(2010-10-08 00:11:16)

标签：

杂谈

64匹马8赛道与归并排序

2009清华大学自主招生试题：64匹马赛跑，假设马发挥稳定且没有体力问题，如果一场比赛可以让8匹马同时赛跑，那么能否在50场比赛内排出所有名次。

1.把64匹马分成8组，先把每组排个序，共8场比赛。

2.把这8组8匹马两两合并为4组16匹马的有序组，每次合并需要3场比赛。
这里就是本题的关键所在：从其中任意选出两组，合并后的前4名肯定在两组的前4名这8匹马里，这8匹比一场就把两组的前4比出来了；对剩下的12马采取同样的策略，各取前4名，然后通过一场比赛决出整合后序列的5-8名，最后还剩8匹马，再为这8匹赛一次，这就是最后8名了。

3.把4组16匹马再两两合并为2组32匹马，每次合并需要7场比赛。
方法同上，实际上可以证明，两组有序的8k匹马合并成一组16k匹马，需要16k/4-1=4k-1场比赛。（之前每场比赛决出靠前的4名，最后一场比赛一次决出最后的8名）

4.把2组合并成1组，需要15场比赛。

这样的话，一共就是 8+4*3+2*7+1*15=49场比赛。

这就体现了信息学中“归并排序”的思想。归并排序具体工作原理如下（假设序列共有n个元素）：

将序列每相邻两个数字进行归并操作(merge)，形成floor(n / 2)个序列，排序后每个序列包含两个元素；
将上述序列再次归并，形成floor(n / 4)个序列，每个序列包含四个元素；
重复步骤2，直到所有元素排序完毕。

另一牛逼解答：

       37场：先随意将马排成8*8阵型：

               01 02 03 04 05 06 07 08

               09 10 11 12 13 14 15 16

               17 18 19 20 21 22 23 24

               25 26 27 28 29 30 31 32

               33 34 35 36 37 38 39 40

               41 42 43 44 45 46 47 48

               49 50 51 52 53 54 55 56

               57 58 59 60 61 62 63 64

         1、每一行赛一场，共八场。由对称性，不妨设每一行都是从左到右速度依次减慢。即01,09,17,25,33,41,49,57是八场的冠军。

         2、下面说明，之后每4场总可以决出8个名次。

                  （1）各组冠军赛一场，（2）各组垫底赛一场，共两场，决出了第一名、第六十四名。且不妨设第一列各马速度由上至下依次变慢。即01是总冠军。

                  （3）现在，总第二名有两匹马候选，02,09。让02,09,10,17四匹马参与第三场。第三场另四匹呢？它们是有类似情况的最慢的几匹马。例如如果64是最慢的，第八列由快到慢依次是08,16,24,32,40,48,56,64，那么，让56,63,55,48四匹马参与第三场。由第三场的结果，总可以知道总第二、第六十三名。

                  下面说明，不管02,09,10,17赛得的结果如何，总第三、四名的候选马不会超过四匹。

                           若02获胜，那么总第三、四名的候选马只有03,04,09，以及10和17两匹中较快的一匹（这两匹已经赛过）

                           若09获胜，那么第三名实际上已经知道了，是02、10或17中较快的一匹。若是02，则第四名候选马是03，10，17。若是10，则第四名候选马是02，11，17。若是17，则第四名候选马是02，10，18，25。

                     于是，总第三、四名的候选马不会超过四匹。同理，总第六十二、六十一名的候选马也不会超过四匹。

                  （4）将上述总第三、四名的候选马、总第六十二、六十一名的候选马至多不超过八匹，赛一场，于是至此已经决出了前四名后四名共八个名次。

         不断重复上述过程，直至7个4场后决出了56个名次。

         3、最后还剩8个名次，用一场解决。

总计：8+4*7+1=37场。

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：c# webBrowser 模拟填表

后一篇：QQ邮箱 POP3 和 SMTP 服务器地址

新浪BLOG意见反馈留言板　欢迎批评指正