一,问题描述:
从25匹马中选出跑的最快的5匹,每次比较5匹(5个赛道),假设每匹马的状态是稳定的
二,思路:
1,正向:增至5匹
2,逆向:减至/剩至5匹
3,正向+逆向:
三,我的解答:
设有矩阵/二维数组如下,且依据每次比赛结果进行排序,永远保证M[i][j] > M[i+n][j+n] (n > 0),即永远保证组内有序(从上到下递减)、组间有序(从左至右递减)
A1 |
B1 |
C1 |
D1 |
E1 |
A2 |
B2 |
C2 |
D2 |
E2 |
A3 |
B3 |
C3 |
D3 |
E3 |
A4 |
B4 |
C4 |
D4 |
E4 |
A5 |
B5 |
C5 |
D5 |
E5 |
1,最坏/最多情况:10次
前5步:分5组,比5次(纵向比较/组内有序)
第六步:取每组第一名进行比较(横向比较),抛出第一名
第七步~第十步:取每组当前第一名(除去抛出的元素,类似5个弹夹,各组成员依次上顶)进行比较(横向比较),依次抛出第二名~第五名
2,最好/最少情况:7次
前5步:分5组,比5次(纵向比较/组内有序)
第六步:取每组第一名进行比较(横向比较)并依据比较结果进行排序(组间有序),此时有A1>B1>C1>D1>E1,抛出第一名/A1
第七步:选第二匹。因为组内有序和组间有序,所以每个子矩阵左上角的第一个元素为该子矩阵中最大的元素(最快马)。每次只要比较子矩阵中最大元素和该子矩阵之外的元素即可,即比较B1(红色子矩阵中最大元素)、A2、A3、A4和A5。若A2>A3>A4>A5>B1,则最快的5匹马为A1、A2、A3、A4、A5,且A1>A2>A3>A4>A5
四,校验:
1,假设最快的5匹马都分在同一组
2,假设最快的5匹马分别为各组的第一名
五,我的总结:
最少比赛次数N一定满足:6 < N <= 10
六,参考:
1,CSDN网友SaiRose:
//该网友讨论的是25选3(每次比较5匹)的问题,与本题略有不同
7场是最少的了
首先是先全部都比一次:
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
这5次是必须的
然后分别找出第一,第二,第三
先A1 B1 C1 D1 E1,这样可以得到第一,不妨设这组结果为A1 B1 C1 D1 E1,A1第一
有了上面6组结果可以肯定第二在A2 B1中
如果第二是A2,那么第三肯定在B1 A3中
如果第二是B1,那么第三肯定在A2 B2 C1中
所以现在我们只要知道了A2 A3 B1 B2 C1的大小顺序就可以判断第二第三分别是谁
所以总共需要7次比赛就可以了
上面讨论基于这个结论:
若Pi是第i,则第i+1必然是所有已经完了的比赛中排在Pi后面那匹马中的一个
2,从25匹马中选5匹最快马
//只参考其第6场比赛中排除法的思想(若已确定有5匹马比它快,则排除该马)
今天的文章从25匹马中选5匹最快马多少秒_世界上最快的马是什么马「建议收藏」分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/88584.html