25匹赛马,5个跑道,也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的5匹马
前5次大家都一样,排序后如下
A1,A2,A3,A4,A5
B1,B2,B3,B4,B5
C1,C2,C3,C4,C5
D1,D2,D3,D4,D5
E1,E2,E3,E4,E5
第六次,最大值比较,找出最快的马
第7次参加比赛的马匹为
A2 A3 B2 C2 D1
下面就3种第7次可能的比赛结果进行分析:
1、若第7次的比赛可能的一种结果为:
A2 A3 B2 C2 D1
此时必进入前5的是A1、A2、A3
可能进前5的是A4、A5、B1、B2、C1
则第8次为
A4、A5、B1、B2、C1
取前2名,与A1、A2、A3一直即为前5
2、若第7比赛结果为B2、A2、C2、A3、D1
此时必进入前5的是A1、B1、B2
可能进入前5的是A2、B3、B4、C1
第8次只要让这4匹马参赛就可以啦
3、若第7次比赛结果为D1、C2、A2、A3、B1
此时必进入前5的是A1、B1、C1、D1
而剩下的第5匹马只可能出现在C2、D2、E1这3匹马中,自然,让这3匹马参加第8次比赛就可以啦
总之,不管第7次的比赛结果如何,都在第8次比赛中做出适当的安排,即而可以在8次比赛后确定跑得最快的前5匹马。
36匹马,通过赛马寻找出最快的3匹。跑道可容纳6匹马同时赛跑,请问最快需要几次赛马可以找到最快的3匹马?
首先假设每匹马的速度不一样,这样分析可以抓住要害。如果有速度相同的马,则问题会稍微复杂一点,但基本思路是一致的。
先给出一个最简单的方案。36匹马随机分为6组,分别进行赛跑,那么每组的后3名将被淘汰(这些马不可能是最快的),余下18匹马。将剩余的18匹马再次分为3组进行赛跑,余下9匹。在最后9匹中随机选择6匹进行赛跑,将最快的3匹马与剩下3匹马进行赛跑,最后胜出的3匹马即为所求。总共赛马次数为6+3+1+1=11
让我们回顾一下上述的赛马过程。我们发现,最初的6次赛马之后,剩余的18匹马实际上是局部有序 的,每一组赛马的3匹优胜马都是有序的,很显然上面的做法过于简单,存在冗余操作。我们接下来要做的工作实际上类似于归并排序。那么怎么做可以用最少的赛马次数从18匹马中挑选出最快的3匹呢?
答案是这样的:将第一组中3匹优胜马按排名令为A1,A2,A3,其中A1最快;同理第二组令为B1,B2,B3;第三组C1,C2,C3;以此类推,直至F1,F2,F3。取A1,B1,C1,D1,E1,F1进行赛跑,为了方便说名,假设结果为A1>B1>C1>D1>E1>F1。很显然,D1,E1,F1,将被淘汰,于是D、E、F组的其余马也将被淘汰,因为他们比这3匹马还慢。再看C组,在剩余有竞争力的9匹马中(分别是A1,A2,A3,B1,B2,B3,C1,C2,C3),C1最多只能排第三,那么C2,C3不可能成为最快的3匹马之一,将其淘汰。同理观察B组,可知B3也不具备成为前三甲的可能,淘汰之!现在只剩下A1,A2,A3,B1,B2,C1共6匹马,再次进行赛马即得到答案。总共赛马次数为6+1+1=8
结论:最快通过8次赛马可得答案。
前5次大家都一样,排序后如下
A1,A2,A3,A4,A5
B1,B2,B3,B4,B5
C1,C2,C3,C4,C5
D1,D2,D3,D4,D5
E1,E2,E3,E4,E5
第六次,最大值比较,找出最快的马
第7次参加比赛的马匹为
A2 A3 B2 C2 D1
下面就3种第7次可能的比赛结果进行分析:
1、若第7次的比赛可能的一种结果为:
A2 A3 B2 C2 D1
此时必进入前5的是A1、A2、A3
可能进前5的是A4、A5、B1、B2、C1
则第8次为
A4、A5、B1、B2、C1
取前2名,与A1、A2、A3一直即为前5
2、若第7比赛结果为B2、A2、C2、A3、D1
此时必进入前5的是A1、B1、B2
可能进入前5的是A2、B3、B4、C1
第8次只要让这4匹马参赛就可以啦
3、若第7次比赛结果为D1、C2、A2、A3、B1
此时必进入前5的是A1、B1、C1、D1
而剩下的第5匹马只可能出现在C2、D2、E1这3匹马中,自然,让这3匹马参加第8次比赛就可以啦
总之,不管第7次的比赛结果如何,都在第8次比赛中做出适当的安排,即而可以在8次比赛后确定跑得最快的前5匹马。
36匹马,通过赛马寻找出最快的3匹。跑道可容纳6匹马同时赛跑,请问最快需要几次赛马可以找到最快的3匹马?
首先假设每匹马的速度不一样,这样分析可以抓住要害。如果有速度相同的马,则问题会稍微复杂一点,但基本思路是一致的。
先给出一个最简单的方案。36匹马随机分为6组,分别进行赛跑,那么每组的后3名将被淘汰(这些马不可能是最快的),余下18匹马。将剩余的18匹马再次分为3组进行赛跑,余下9匹。在最后9匹中随机选择6匹进行赛跑,将最快的3匹马与剩下3匹马进行赛跑,最后胜出的3匹马即为所求。总共赛马次数为6+3+1+1=11
让我们回顾一下上述的赛马过程。我们发现,最初的6次赛马之后,剩余的18匹马实际上是局部有序 的,每一组赛马的3匹优胜马都是有序的,很显然上面的做法过于简单,存在冗余操作。我们接下来要做的工作实际上类似于归并排序。那么怎么做可以用最少的赛马次数从18匹马中挑选出最快的3匹呢?
答案是这样的:将第一组中3匹优胜马按排名令为A1,A2,A3,其中A1最快;同理第二组令为B1,B2,B3;第三组C1,C2,C3;以此类推,直至F1,F2,F3。取A1,B1,C1,D1,E1,F1进行赛跑,为了方便说名,假设结果为A1>B1>C1>D1>E1>F1。很显然,D1,E1,F1,将被淘汰,于是D、E、F组的其余马也将被淘汰,因为他们比这3匹马还慢。再看C组,在剩余有竞争力的9匹马中(分别是A1,A2,A3,B1,B2,B3,C1,C2,C3),C1最多只能排第三,那么C2,C3不可能成为最快的3匹马之一,将其淘汰。同理观察B组,可知B3也不具备成为前三甲的可能,淘汰之!现在只剩下A1,A2,A3,B1,B2,C1共6匹马,再次进行赛马即得到答案。总共赛马次数为6+1+1=8
结论:最快通过8次赛马可得答案。
发表评论
-
小白鼠试药
2011-11-26 19:59 1053大家应该都听说过这个老题目:有 1000 个一模一样的瓶子,其 ... -
算生日是哪天
2011-11-26 19:57 1小明和小强都是张老师的学生,张老师的生日是M月N日, 2 ... -
自由主义的书单-王怡
2011-11-11 19:17 1174zz:http://www.douban.com/group/ ... -
HTTP协议详解
2011-11-07 21:10 667zz:http://blog.csdn.net/gueter/ ... -
SSL和HTTPS
2011-11-07 20:59 801zz:http://cuiyongxiu.com/201102 ... -
Actor
2011-11-07 17:23 0http://blog.jeoygin.org/archive ... -
软件质量的度量
2011-11-04 20:07 3836如何去度量软件的 ... -
YCSB测试Hbase-MySQL测试
2011-11-04 15:46 0Hbase测试: http://hbase.inf ... -
Java命令参数说明
2011-11-03 14:45 687序言: Java 在运行已编译完成的类时,是通过 java ... -
REST API必须是超文本驱动的
2011-10-24 21:10 1458http://www.infoq.com/cn/news/20 ... -
狼的精神
2011-09-28 23:05 938在人类心目中的狼 凶残 ... -
JDK中的设计模式
2011-09-24 21:16 633http://stackoverflow.com/questi ... -
系统日志分析脚本
2011-09-24 21:32 4011http://bbs.chinaunix.net/thread ... -
成功说服别人的20个技巧
2011-08-21 23:42 662转自:http://www.shanghaisc. ... -
为什么群体规范扼杀创造力
2011-08-21 23:32 856转自:http://article.yeeyan. ... -
Git GitHub入门
2011-08-21 19:01 714参看: GitHub和Git配置 http://artori. ... -
提问的智慧
2011-08-19 17:20 527... -
MySQL-十大工具
2011-09-24 21:14 872转自:http://tech.it168.com/a2011/ ... -
不要成为工具的奴隶
2011-08-07 11:38 762转自:http://daiyuwen.freeshell.or ...
相关推荐
骑士赛马问题,eclipse下JAVA编程实现;采用贪心算法实现,程序中有详细的注释。测试通过。
田忌赛马问题田忌赛马问题田忌赛马问题田忌赛马问题田忌赛马问题
8.3 赛马问题.docx
最有赛马问题(田忌赛马)算法设计.docx
田忌与齐王赛马,双方各有n匹马参赛(n),每场比赛赌注为1两黄金,现已知齐王与田忌的每匹马的速度,并且齐王肯定是按马的速度从快到慢出场,现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金(输用负数...
最新人教版四年级数学上册《田忌赛马问题》课时练习--.pdf
四年级上册沏茶问题、烙饼问题、田忌赛马问题精品教学设计.doc
时优化田忌赛马问题PPT学习教案.pptx
2014四上第八单元赛马问题课件3.ppt
本文实例讲述了Golang算法之田忌赛马问题实现方法。分享给大家供大家参考,具体如下: 【田忌赛马问题】 输入: 输入有多组测试数据。 每组测试数据包括3行: 第一行输入N(1≤N≤1000),表示马的数量。 第二行有N个...
最新人教版四年级上册数学《赛马问题》同步练习--.pdf
新人教版四年级上册数学 第3课时 赛马问题 重点习题练习复习课件.pptx
四年级数学上册8数学广角_优化8.3田忌赛马问题教学反思素材新人教版
输入n[1, 100]组田忌和齐威王的马的速度,使用贪心法求田忌胜出的最多盘数(赢局数—输局数,平局数不算分),设计贪心策略,实现程序。 输入:组数n[1, 100],田忌和齐威王每组马的速度,每一组包含两个正整数,...
古时候,国王 A和国王 B 都十分热爱赛马运动。他们分别有 N匹马,他们知道自己和 对手每只马的速度。两人进行 N 场比赛,每次比赛双方各出一匹马,每匹马限比一次。国 王 A通过某种特殊途径,已预先打探到了国王 B ...
用动态规划的方法实现田忌赛马问题,用C语言实现
田忌赛马问题 利用动态规划解决,很简洁
mathematica软件解决实际问题——田忌赛马3.pdf
【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校训练题,2020年的今天,我们一个集训队全部挂在上面了。最后在HDU看到了9年前的讨论区,才知道这题有如下问题: speed...