注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

64匹马能否通过50场比赛比出任意两匹马之间的优劣(每场比赛至多8匹马参赛)  

2010-10-31 14:04:29|  分类: 数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

这是2009年清华大学自主招生数学试题(理综)。

思考时间,答案在下面(字体是白色的)。

这道题其实考的是归并排序。

首先将马分为8组,每组排一下序,就比了8场。

然后再将这8组合并为4组,两两合并。

比如A和B组合并:

选A组的前4名和4个B组的前4名,比一场,如果从A中的选出的第4名比B中选出的第4名排名高,那么在A中的选出的第4名前和他自己一定是这些马中靠前的,于是把他们排到新的队中,其余马回到原来的位置;否则,同理分析。所以这样比一场可以确定至少4匹马在新的小组中的的位置。

接下来在剩下的马中继续这样做,直到所有马在新的小组中的位置都确定了。

由于每次都可以至少确定4匹马的位置,而且最后还剩8匹马时只需要比一次就可以确定8匹马的位置,所以两个8匹马的有序的小组合并为一个16匹马的有序小组只需要(16-8)/4+1=3次比赛。

所以8个8匹马的有序的小组合并为4个16匹马的有序小组需要4*3=12次比赛。

所以4个16匹马的有序的小组合并为2个32匹马的有序小组需要2*7=14次比赛。

所以2个32匹马的有序的小组合并为1个64匹马的有序小组需要1*15=15次比赛。

所以一共只需比49场就可以了。

  评论这张
 
阅读(639)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018