笔试题: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