算法--跑马场

转自https://www.cnblogs.com/bhlsheji/p/5373336.html

题目一：对于25匹马，有一个赛场，赛场有5个跑道，不使用计时器（也就是每次比赛仅仅得到本次的比赛的顺序）。试问最少比多少场才干选出最快的三匹马？

 

思路：

 

0)前5场：这个题相对照较简单，25匹马至少要所有參加比赛，所以把25匹马分成5组进行比赛。这样我们就能够得到比赛结果例如以下：

1)选总体第1名：如今我们要选总体第一名，可能成为总体第1名的马匹为：｛A1、B2、B3、B4、B5｝，那么第6场比赛为［A1。B1。C1，D1。E1］

 

比赛结果：第6场得到总体第1名

 

 

2)选总体第2、3名：依据矩阵关系。可知可能成为总体第2名的马匹为：｛A2、B1｝，可能成为总体第3名的马匹为｛A2、A3、B1、B2、C1｝，所以第7场比赛为［A2，B1，A3。B2、C1］

 

比赛结果：第7场得到总体第2、3名

 

 

可能你对上面红色字体不是特别理解，换种思路来说：

 

总体前1名可能出现范围：A1

总体前2名可能出现范围：A2、B1

总体前4名可能出现范围：A1、A2、B1

总体前7名可能出现范围：A1、A2、A3、B1、B2、C1

... ...

 

自己画一下就能够知道里面的规律

 

 

题目二：对于25匹马，有一个赛场，赛场有5个跑道。不使用计时器（也就是每次比赛仅仅得到本次的比赛的顺序），试问最少比多少场才干选出最快的五匹马？（第一题是选前三名）

 

 

思路一：（简单的，竞标赛排序）

 

所谓简单。一般都有些蛮力的味道。全部优化，一般都会借助上一次的结果优化下一次的操作。

 

简单的思路关键词是：替换思想（用已选出的赛马替换掉选出的马）

 

0)和题目一思路一样，我们须要5场比赛来得到25匹马的基本顺序。

 

1)開始选马

 

第6场：选总体第1名-->參赛马为［A1，B1，C1，D1，E1］-->如果选出的总体第1名为A1

第7场：第选总体第2名-->參加在为［A2，B1，C1。D1。E1］-->如果选出的总体第1名为B1

第8场：选总体第3名-->參加在为［A2。B2，C1，D1。E1］-->如果选出的总体第1名为A2

第9场：选总体第4名-->參加在为［A3，B2。C1。D1，E1］-->如果选出的总体第1名为C1

第10场：选总体第5名-->參加在为［A3。B2，C2，D1，E1］-->如果选出的总体第1名为C2

.....

第25场：选总体第20、21、22、23、24、25

 

所以使用竞标赛排序思想（替换策略）。选出前5名须要10场比赛

 

 

思路二：

 

再反复一句：所谓简单，一般都有些蛮力的味道。

全部优化，一般都会借助上一次的结果优化下一次的操作。

 

那么优化后的选马方案为：

 

0)前5场仍然是比赛得到5组马匹的基本序列

 

1)第6场：參赛马为［A1。B1，C1，D1，E1］（比赛后如果A1>B1>C1>D1>E1）

 

比赛结果：第6场得到总体第1名A1

 

 

2)第7场：我们继续分析可能为总体第2名的马为{A2、B1}。可能为总体第3名的马为{A2、A3、B1、B2、C1}。

此时我们能够知道事实上仅仅须要比較［A2。A3，B1，B2，C1］就能够得到第2、3名了（回忆一下刚才使用简单替换思想，第6场比赛［A2，B1。C1，D1，E1］。当中D1、E1根本不可能是总体第2名的）

 

比赛结果：第7场得到总体第2、3名

 

 

3)问题来了。第7场得到2、3名。可是不能确定是哪两匹马。

所以我门要列举一下第2、3名可能的情况（一共5种）：

A2，A3

A2。B1

B1。A2

B1，B2

B1，B3

 

3.1) 对于第一种情况：A2，A3

那么总体第4名可能为：｛A4、B1｝

假设第4名为A4，总体第5名可能为｛A5、B1｝

假设第4名为B1。总体第5名可能为｛B2、C1｝

 

非常明显，我们仅仅须要一场比赛（第8场）就能够确定总体第3，4名，參赛马为：［A4，B1，A5，B2，C1］

 

 

3.2)对于另外一种情况：A2、B1

那么总体第4名可能为A3、B2、C1

假设总体第4名为A3。总体第5名可能为｛A4、B2、C1｝

假设总体第4名为B2。总体第5名可能为｛A3、B3、C1｝

假设总体第4名为C1，总体第5名可能为｛A3、B2、C2、D1｝

 

那么我们要向得到总体第4、5名的马匹，就须要比較［A3。A4，B2，B3，C1。C2。D1］，非常明显须要2场比赛（第8、9场）才干分出胜负

 

剩下的3种情况类似，选出前5匹马，至少8场，最多9场