龙空技术网

智力题分析解答:赛马问题

IT小村 53

前言:

现时你们对“3匹马算法”大体比较着重,朋友们都想要分析一些“3匹马算法”的相关内容。那么小编也在网上汇集了一些对于“3匹马算法””的相关知识,希望朋友们能喜欢,同学们快快来了解一下吧!

题目

你有25匹马,你要找出跑得最快的三匹。每次比赛你只能让五匹马同时跑,而且比赛的结果不能得到确切的时间,只能得到排名。假设所有马的速度都是恒定不变的,你最少需要安排多少场比赛才能找出跑得最快的三匹马?

分析

这个问题的关键在于你不能得到每匹马的确切速度,只能通过它们之间的比赛结果来判断哪一匹马跑得更快。问题的挑战在于找出一种最有效的比赛安排方式,以便在最少的比赛次数中找出最快的三匹马。

并利用好每次可以放5匹马进行比赛的特点,物尽其用。

答案

答案是7次:

第一步,把25匹马分成5组,每组5匹。让他们分别进行一次比赛,这需要5次比赛。第二步,选出每组的第一名(总共5匹马),再进行一次比赛,得出的冠军肯定是所有25匹马中最快的,这需要1次比赛。假设结果是A1>B1>C1>D1>E1。第三步,根据矩阵的特点,将A2、A3、B1、B2、C1这5匹马进行比赛,得出第2、3名。

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

所以,总共需要5 + 1 + 1 = 7次比赛,就能找出最快的3匹马。

扩展

假设要获取最开的5匹马,而不是3匹马,那么需要多少次比赛呢?

标签: #3匹马算法