一,问题描述:
从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,http://blog.csdn.net/chen825919148/article/details/8053980
//只参考其第6场比赛中排除法的思想(若已确定有5匹马比它快,则排除该马)