算法题-25匹马,找出最快的3匹,最少需要多少次比赛

笔试题:25匹马,找出最快的3匹,但是只有5个赛道,每次比赛只能得到5匹马的速度排序,那么最少需要多少次比赛?

答案:7

分析:

1-5 场:

将25匹马分为5组,每组5匹,得到下面的排序,假设每组最快的马在左侧,即X1、X6、X11、X16、X21分别是每组中最快的。

组1:X1    X2    X3    X4    X5
组2:X6    X7    X8    X9    X10
组3:X11  X12  X13  X14  X15
组4:X16  X17  X18  X19  X20
组5:X21  X22  X23  X24  X25

但是,现在还不能说最快的3匹马在X1、X6、X11、X16、X21中,因为有可能最快的3匹马全部分在第一组中,即有可能出现X2比X6快。

但是我们肯定可以知道每组的最后2名肯定不会是最快的3匹马(假如某组的前三名是最快的,就没后两名什么事了~)

那么排除X4、X5;X9、X10;X14、X15;X19、X20;X24、X25

第6场:此时共这些参赛的马,挑选每组中的第一名参赛

X1    X2    X3
X6    X7    X8
X11  X12  X13
X16  X17  X18
X21  X22  X23

参赛的为每组的第1名:X1、X6、X11、X16、X21,假设速度排序为X1、X6、X11、X16、X21。

那么我们可以知道,前三名有可能是最快的三名,所以后两名基本走远了(x16、 x21),X16、X21及其后面的X17、X18;X22、X23均不可能是最快的3匹马。

第7场:因为x1是上轮所有比赛中最快的,假如6是跑的第二快的,那8后面的8基本也走远了,因为1、6都比11快,所以11那一组只能是11为第三名,11后面的12、13也走远了。去掉1,淘汰掉8、12、13,此时剩2、3、6、7、11来参加比赛

X1  X2   X3
X6  X7   X8
X11 X12 X13

目前,我们可以知道,X1是25匹马中最快的,但是X2、X6、X3、X7、X11之间的速度还不确定,需要再一次比赛,而X8、X12、X13不可能是最快的前3名。

参赛的为:X2、X6、X3、X7、X11,速度最快的2匹加上X1构成最快的3匹马。

因此一共需要7次比赛。


原文链接:https://blog.csdn.net/shayne000/article/details/97635105

原文地址:https://www.cnblogs.com/yaya-003/p/12665681.html