一道面试题:赛马问题

FROM 酷壳

据说,这是Google的面试题。面试题目如下:

一共有25匹马,有一个赛场,赛场有5个赛道,就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定,不用任何其他工具,只通过马与马之间的比赛,试问,最少得比多少场才能知道跑得最快的5匹马?(不能使用撞大运的算法

很明显这是一个算法题,网上有很多贴子在讨论这个问题,不过都没有给出一个明确的答案。我想了想,想到下面的一个算法:

1)分成5组A,B,C,D,E,比五场。然后根据每场结果分别给这五组内的五匹马排序(从快到慢)。
2)每组的头名再赛一场,取走第一名,然后该组第二名顶上。
3)重复第二步,直到选出前5名。

这个算法是比较笨的算法,总计需要赛10次,这个算法应该是万无一失的。现在的问题的就,如何优化这个算法,想了想,的确是有优化的空间的。也就是说,是可以少于10次的。

想了一想,上面的那个算法自从第6次开始就使用5个排序数组的头名做“冒泡法”,总是挑一个最优秀的出来,其实,在第6次以后除了挑出最优秀的,我们还可以在每次比赛后淘汰一些速度不行的,淘汰的马匹数自然会比选出的更多,所以,一方面在找,另一方面在淘汰,找出前5名的速度应该会更快。

比如:我们假设比赛完第六场后,我们得到下面的排序:(每组排序是——快马从左到右,各组头名的排序是——快马从上到下)

A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 B5
C组 C1 C2 C3 C4 C5
D组 D1 D2 D3 D4 D5
E组 E1 E2 E3 E4 E5

这样,我们不但知道,A1是25匹马里最快的马,而且我们可以淘汰近一半的马,比如E2,E3,E4,E5就可以全部淘汰了,为什么呢,因为比E2快的马有A1,B1,C1,D1,E1这五匹马,所以,E2后面的马是无法进入前五名了;同理,D3和其后面的也进入不了前5;同理,C4,C5,B5都可以淘汰。

于是,在第六轮后我们可以得知,除了A1外的Top 4必然在下面这些马中:

A组  A2 A3 A4 A5
B组 B1 B2 B3 B4 
C组 C1 C2 C3 
D组 D1 D2 
E组 E1

接下来的过程应该不必我多说了。重复前面的方法,尽可能淘汰无法进前N名的马,于是后面的马就越来越少,你所需要的比赛也会越来越少。

那么,对于这个题,聪明的你知道最少要比赛几场了吗?

举一反三,如果有64匹马,8个赛道呢?不失一般性,如果有N匹马,M个赛道呢?N = M*M,那么公式是什么呢?

期待你的答案!

时间: 2024-10-24 10:05:58

一道面试题:赛马问题的相关文章

一道面试题(关于千万量级数据结构排序)

问题描述 一道面试题(关于千万量级数据结构排序) 题目: 已知文件中存有全国英语六级历年来的成绩(千万级别,考生分数都是正整数,最高710分),每一行都是一个人的姓名.考号和成绩,请你对考生的成绩从高到低进行排序,输出到另一个文件中. 格式 如下: 李四,201008823,678: 张三,201007432,356: 王五,201322233,464: 排序后: 李四,201008823,678: 王五,201322233,464: 王五,201322233,464: 要求:使空间复杂度和时间

语言 面试题-一道面试题,不是很清楚这个例子怎么解答,求大神帮助.

问题描述 一道面试题,不是很清楚这个例子怎么解答,求大神帮助. 提问是 这段代码有什么问题, 有什么解决思路.(我其实连问题都没看出来,代码可以编译) // Memory-mapped peripheral#define STATUS_REG_ADDR 0x12345678 // 32-bit status register#define DATA_REG_ADDR 0x1234567C // 32-bit data register // Status register bits#define

初始化顺序-今年阿里巴巴的一道笔试题

问题描述 今年阿里巴巴的一道笔试题 public class Test1 { public static int k = 0; public static Test1 t1 = new Test1("t1"); public static Test1 t2 = new Test1("t2"); public static int i = print("i"); public static int n = 99; public int j = pr

结构体定义-如何定义满足以下的Node与List结构体,今天参加斐讯的一道笔试题。

问题描述 如何定义满足以下的Node与List结构体,今天参加斐讯的一道笔试题. Node包含50个字符.

从一道面试题说去

    有一道面试题: 给定n个整型数,怎样让这n个数的使用空间最小.      ok,我们都知道在32位的机器下,int类型的数占4个字节,因此n个数总的使用空间应该是4n.(64位不做解释)那我们怎么样才能使得n个数字的使用空间最小呢?     一. 我们先来看一个例子           假设现在有3个数,1,2,3.           我们都知道数字最后都是以二进制的方式存储的,我们可以表示出1,2,3的二进制           1: 0000 0000 0000 0000 0000

《Wireshark网络分析就这么简单》—从一道面试题开始说起

从一道面试题开始说起Wireshark网络分析就这么简单从一道面试题开始说起我每次当面试官,都要伪装成无所不知的大牛. 这当然是无奈的选择--现在每封简历都那么耀眼,不装一下简直镇不住场面.比如尚未毕业的本科生,早就拿下CCIE认证:留欧两年的海归,已然精通英.法.德三门外语:最厉害的一位应聘者,研究生阶段就在国际上首次提出了计算机和生物学的跨界理论--可怜我这个老实人在一开场还能装装,到了技术环节就忍不住提问基础知识,一下子把气氛从学术殿堂拉到建筑工地.不过就是这些最基础的问题,却常常把简历精

《大咖讲Wireshark网络分析》—从一道面试题开始说起

从一道面试题开始说起大咖讲Wireshark网络分析我每次当面试官,都要伪装成无所不知的大牛. 这当然是无奈的选择--现在每封简历都那么耀眼,不装一下简直镇不住场面.比如尚未毕业的本科生,早就拿下CCIE认证:留欧两年的海归,已然精通英.法.德三门外语:最厉害的一位应聘者,研究生阶段就在国际上首次提出了计算机和生物学的跨界理论--可怜我这个老实人在一开场还能装装,到了技术环节就忍不住提问基础知识,一下子把气氛从学术殿堂拉到建筑工地.不过就是这些最基础的问题,却常常把简历精英们难住.本文要介绍的便

一道面试题:布尔变量

FROM:酷壳 下面这篇文章是从StackOverflow来的.LZ面试的时候遇到了一道面试题:"如果有三个Bool型变量,请写出一程序得知其中有2个以上变量的值是true",于是LZ做了下面的这样的程序: boolean atLeastTwo(boolean a, boolean b, boolean c) { if ((a && b) || (b && c) || (a && c)) { return true; } else { r

mysql一道面试题

mysql> #一道面试题 mysql> #把一张表num 的值[20-30]之间的数全改为20 mysql> #并且把[30-40]之间的数全改为30 mysql> create table mianshi ( -> num int -> ); Query OK, 0 rows affected (1.94 sec) mysql> show tables; +----------------+ | Tables_in_test | +--------------