25匹马5个跑道,选出最快的5匹马?

news/2024/11/7 22:33:01/

回顾之前问题:25匹马5个跑道,怎样选出最快的3匹
答:先分成5组比赛并组内排序(从1到5速度减慢),再让每组第一名比赛,按照每组第一名的比赛结果从快到慢对每组排序(从A到E速度减慢),此时共计比赛6轮,有:
A1 A2 A3 A4 A5 -> A组
B1 B2 B3 B4 B5 -> B组
C1 C2 C3 C4 C5 -> C组
D1 D2 D3 D4 D5 -> D组
E1 E2 E3 E4 E5 -> E组
这时已经得到,25匹马里,最快的是A1,要选出最快的3匹,那么只需找出第2、3名。
而2、3名只可能出现在:A2 A3,B1 B2,C1 里,让这5匹马再比赛一场,前2名就是要找出的25匹马里最快的2、3名。

现在要找出的是25匹马里,最快的前5名:
显然,找出最快的前5名,最多只需要比赛10场:
前5场赛让每个组组内完成排序,后5场每一场挑选当前组内的第1名参加,然后赛出当前场上剩余马匹里最快的那匹马。要找出前5名,那么自然最多只需要比赛5场。
有没有更快的方法?
依旧通过和之前一样比赛5场,完成组内排序,再比赛1场,首先找出最快的A1:
A1 A2 A3 A4 A5 -> A组
B1 B2 B3 B4 B5 -> B组
C1 C2 C3 C4 C5 -> C组
D1 D2 D3 D4 D5 -> D组
E1 E2 E3 E4 E5 -> E组

A1作为25匹马里最快的,放到结果集里,场上剩余马情况如下:
A2 A3 A4 A5 -> A组
B1 B2 B3 B4 B5 -> B组
C1 C2 C3 C4 C5 -> C组
D1 D2 D3 D4 D5 -> D组
E1 E2 E3 E4 E5 -> E组

此时要找出场上剩余马匹里最快的4匹马,那么这4匹马只可能出现在这些马里:
A2 A3 A4 A5 -> A组
B1 B2 B3 B4 -> B组
C1 C2 C3 -> C组
D1 D2 -> D组
E1 -> E组
为了更快找出场上剩余马匹里最快的4匹,不能像刚开始提到的方式那样,让A2,B1,C1,D1,E1比赛找出最快的,而是应该让:
A2 A3 A4 A5,B1 比赛。
因为A2 A3 A4 A5 里,可能最慢的A5也比B1要快,如果是这种情况,那么只需比赛这一场,就能直接确定场上剩余马匹里最快的4匹是A2 A3 A4 A5,总计比赛7次就能得出题目全部解。
即使不是这种情况,例如假若B1比A2慢,但比A3快,那么也能在这一次比赛里,迅速得出,剩余马匹里最快的是A2,其次是B1,这样一下子就能确定2个解,因为题目是找出前5名,而之前已经找出了第一名A1,那么接下来只需要找出场上剩余马匹里最快的前2名即可。
当然,A2 A3 A4 A5,B1比赛的结果不止以上2种,但无论比赛结果B1排第几名,最后处理流程都是B1前面的马(假设有x匹)作为最终结果里排名的第2名到第x+1名,B1则是最终结果里的第x+2名。剩余要找出的就是在剩余马里最快的5-(x+2)匹马了。
要找出最快的5-(x+2)匹马,只需要在剩余组里,重复第6、第7场比赛的方式,即先让每组最快的马比赛,让组和组之间排好序,找到场上剩余马里最快的马并放到结果集里,然后再让最快马所在的组,和第二快的组里的马比赛。重复这一过程。
易证:这种方式最慢比赛10次,最快比赛7次


http://www.ppmy.cn/news/601461.html

相关文章

100匹马驮100块石头

现在共有100 匹马和100石头,马分三种,大马,中马,小马.其中,每匹大马每次可以驮三块石头,中马可以驮两块石头,而小马两匹才能驮一块,问需要多少匹大马,中马和小马? // 用java来帮你计算// 先写一个main方法public static void main(String[] args) {//大马每次三块石头int a …

64匹马,8个赛道,找出跑得最快的4匹马

64匹马,8个赛道,找出跑得最快的4匹马,至少比赛几场? 第一步 全部马分为8组,每组8匹,每组各跑一次,然后淘汰掉每组的后四名,如下图(需要比赛8场) 第二步 …

MATLAB:单轴晶体的相位匹配角计算

MATLAB:单轴晶体的相位匹配角计算 对于相位匹配来说,计算相位匹配角是一个繁琐的过程。 以下是通过matlab来辅助计算单轴晶体的相位匹配角。 可以简单计算单轴晶体的一类相位匹配以及二类相位匹配。 懒得检查代码了,各位大神欢迎指出错误。 …

25匹马问题

题目:如果要25匹马中选出跑得最快的3匹,每次只有5匹马同时跑,最少要比赛几次,才能确保得出结果? 25匹马看成25个点,每次比赛在参赛的5匹马之间引入4条有向边,1->2->3->4->5&#xf…

测试题:64 匹马,8 个赛道,最少多少次比赛找出最快的 4 匹马?

文章目录 问题一:64 匹马,8 个赛道,最少几场比赛找出最快的4匹马?问题二:64 匹马,8 个赛道,最少多少次比赛对所有马进行排序? 问题一:64 匹马,8 个赛道&#…

现有2头猪、3头牛和4只羊,它们各自的总价都不满1000元。如果将2头猪与1头牛放在一起,或者将3头牛与一只羊放在一起,或者将4只羊与1匹马放在一起,那么它们各自的总价都正好是1000元。问猪、牛、羊

问题:现有2头猪、3头牛和4只羊,它们各自的总价都不满1000元。如果将2头猪与1头牛放在一起,或者将3头牛与一只羊放在一起,或者将4只羊与1匹马放在一起,那么它们各自的总价都正好是1000元。问猪、牛、羊各是多少钱&#…

64匹马,8个赛道,最少多少次比赛找出最快的 4 匹马,以及对所有马进行排序

问题:64匹马,8个赛道,最少几场比赛找出最快的 4 匹马,最少几场对所有马进行排序 问题一:64 匹马,8 个赛道,最少几场比赛找出最快的 4 匹马 问题中隐含的意思:   1、就是每次比赛…

25匹马赛跑

25匹马通过赛跑来决出前三名,每轮最多5匹马参赛,求最少需要几轮? 条件: 1、最多5匹马一组,可以决出本组比赛的次序。 2、没有计时工具,假设马每轮的速度相同。 每次都排除不能争夺前三名的马是关键 7轮就可…