试题-有一个小白程序员，写了一个只能对5个数字进行排序的函数。现在有25个不重复的数字，请问小白同学最少调几次该函数，可以找出其中最大的三个数？

题目

有一个小白程序员，写了一个只能对5个数字进行排序的函数。现在有25个不重复的数字，请问小白同学最少调几次该函数，可以找出其中最大的三个数？

A.5

B.6

C.7

D.8

上一题 下一题

解答

正确答案是 C

1、25人分5组调用，分别排序，调用5次

2、取出5组中的最大数，排序，调用1次

3、将第2步排序中最大的三组取出，假设为A,B,C，从第二步已知A[1]>B[1]>C[1]，不需要再比较，选A[2]、A[3]、B[1]、B[2]、C[1]比较。不需要比较B[3]是因为A[1]已经最大了，若剩下两个数在B中，A[1]占了一个数，只剩两个位置，C[1]同理，轮到C[1]的时候，前面A[1]>B[1]已经占了两个位置。调用1次

总共 5+1+1=7次

C 10条回复评论

老瑭

我还是个菜鸟

发表于 2021-09-12 17:55:00

0 0

途安米

一：五组分别调用排序

二：取每组最大值排序，得到数组A；取最大A1；

三：找到A1所在第一次排序数组B取b2,b3,再取第二次排数数组A1，A2，A3进行排序，得到数组C，取C1，C2，C3

发表于 2018-10-13 14:22:14

0 0

雨声敲敲

另一种思路：

7次

先均分为5组，各组排序，共5次

再取出每组的中位数，排1次，假设结果如下：

A[2]< B[2] < C[2] < D[2] < E[2]

再从C[3]、D[2]、D[3]、E[2]、E[3]这5个数中排序，即可取得前3大的数

所以7=5+1+1

发表于 2018-10-13 14:21:58

0 0

遇见

赛马问题的变形：25匹马，只有5个跑道，决出前3名，最少需要赛几场？

发表于 2018-10-13 14:21:40

0 0

冬季恋歌

答案是C，我选的B。

错误原因：

1. 25人分5组调用，分别排序，调用5次

2、取出5组中的最大数，排序，调用1次

5+1=6次。

未考虑到数组的第二个元素可能是最大的三个数之一。

发表于 2018-10-13 14:21:26

0 0

猪猪猪

将25分成5组，比较5次，n = 5

取出5组最大的一个数，比较一次， n = 5+1

最后一步最重要，思考下，题目中要求取出最大的三个数，假设前三大的组分别为，A,B,C

A[1]最大，剔除A[1]，取出A[2],A[3]，A[4]不符合要求剔除，B组取B[1],B[2]，C组因为已经有两个数比最大的数大(A[1],B[1])，因此只取一个C[1]

新的组为：A[2],A[3],B[1],B[2],C[1]将这比较，取出前两个数 n= 5+1+1 = 7

发表于 2018-10-13 14:21:06

0 0

岁月长歌

答案是7次。

6次比较好理解，不再解释。我们来看为什么要第7次。

5组数中最大的三个，有可能都分布在其中一个组中。因此6次排序实际上只有确认最大的一个数，最后两个不可能的数（第6次排序后2位，最少也是第4大和第5大）。

除开平均分布的情况，还有二种情况，一是三个最大的数都在一组，二是有两数在一组。

因此只需要比较最大三组中的前6个数（3，2，1），注意最大的数已经确定，因此只需要比较5个数。即排序一次。

发表于 2018-10-13 14:20:51

0 0

窦先生

先每5个为1组排序，得到5个极大值
再对这5个排序，得到最大的三个数，设为A1>B1>C1
再回去找第一次排序得到的A2、A3、B2，和B1、C1又凑成5个数
A1一定是全局最大值，因此它算最后三个数里的一个，那么还剩下俩位置，这俩位置可能是
A1    B1    C1
A1    A2    A3
A1    A2    B1
A1    B1    B2
因此对A2    A3    B1    B2    C1再做一次排序
一共5+1+1=7

发表于 2018-10-13 14:20:39

0 0

改造家

先分成五组

测试五次得到每组前三

五组里面的第一（假设是 A B C D E） 测一次 得到序列（假设比较好的序列是 A B C D E）

再从得到最大那一组(A组)的里面取出第二大 X 和第三大 Y ，和第二大数那一组(B组) 取出第二大 Z，把最大五个排好序(A B C D E)里面的最大（A）和倒数两个（D E）换掉

现在就是（B Z C X Y） 调用一次

5+1+1=7

发表于 2018-10-13 14:20:18

0 0

花将离

先每5个数一组，分5组比较，得到5个小组最大，在对这5个数比较得到前3大的，分析，最大的那个肯定最大，排在第一位，第二第三的只能出现在一下5个数中（最大组的第2、3位，第二大的组的第1、2位，或者第三大的组的第1位）将这5个数再比较一次得到第2、3。所以共5+1+1=7次

发表于 2018-10-13 14:20:10

0 0