从25匹马中选5匹最快马多少秒_世界上最快的马是什么马「建议收藏」

从25匹马中选5匹最快马多少秒_世界上最快的马是什么马「建议收藏」一,问题描述:从25匹马中选出跑的最快的5匹,每次比较5匹(5个赛道),假设每匹马的状态是稳定的二,思路:1,正向:增至5匹2,逆向:减至/剩至5匹3,正向+逆向:三,我的解答:设有矩阵/二维数组如下

从25匹马中选5匹最快马多少秒_世界上最快的马是什么马「建议收藏」

一,问题描述:

从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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注