首页 > 代码库 > 36辆车和6个赛道,筛选出最快的3辆车

36辆车和6个赛道,筛选出最快的3辆车

问题描述有36辆赛车和6条跑道,没有计时器的前提下,最少用几次比赛可以筛选出最快的3辆赛车?

情况1:不能标记

  • 将36辆车分成6组,每组6辆车,每组分别进行比赛,留下每组的前3名。还有18辆车(6次)
  • 将18辆车分成3组,每组6辆车,每组分别进行比赛,留下每组的前3名。还有9辆车(3次)
  • 从9辆车中选择6辆进行一次比赛,留下前3名。留下的3辆车和没有参加比赛的3辆车,还有6辆车(1次)
  • 最后6辆车比赛选出前3名(1次)

  总共6+3+1+1=11次

情况2:可以标记

  方法1(8次)

  • 将36辆车分成6组,每组6辆车,每组分别进行比赛,留下每组的前3名,标记。得到A1、A2、A3、...、F1、F2、F3共18辆车(6次)
  • 选择上次比赛每组的第1名进行比赛,得到前3名。A1、B1、C1、D1、E1、F1  --->  D1、A1、E1(假设是这三个,不影响结果)(1次)
  • 上次比赛的第1名D1就是最终的第1名,选择D2、D3、A1、A2、E1(第1名所在分组的2、3名;第2名所在分组的1、2名;第3名所在分组的第1名)共5辆车进行一次比赛,得到前2名,这两辆车和D1组成了最终的结果(1次)

  总共6+1+1=8次

  方法2(7-10次)

  • 选择6辆车进行一次比赛,得到前3名标记为S1、S2、S3(1次)
  • 剩余的30辆车分成6组,每组有5辆车。每组的5辆车和S3进行比赛。如果每一组中S3都是最快的,结束(6次)
  • 否则,最坏情况下,从上次6组比赛前3名组成的A1、A2、A3、...、F1、F2、F3共18辆车中选择前3名(2次,同方法1)
  • 上次比赛的前3名和S1、S2、S3进行比赛,得到最终的结果(1次)

  总共1+6=7(最好)、1+6+2+1=10次(最坏)

  方法3(10次)

  • 将36辆车分成6组,每组6辆车,每组分别进行比赛,留下每组的前3名,标记A1、A2、A3、...、F1、F2、F3共18辆车(6次)
  • 每组的第一名进行一次比赛A1、B1、C1、D1、E1、F1留下前3名B1、A1、F1(1次)
  • 第一次比赛每组的第二名进行一次比赛A2、B2、C2、D2、E2、F2留下前2名A2、E2(1次)
  • 第一次比赛每组的第三名进行一次比赛A3、B3、C3、D3、E3、F3留下第1名B3(1次)
  • B1、A1、F1、A2、E2、B3组成的6辆车,进行1次比赛,得到最终的结果(1次)

  总共6+1+1+1+1=10次

  所以最快的方法是7次,最稳定又快速的方法是8次。

变形1:有25匹马,5条跑道,选出最快的5匹马

  有标记

  • 将25匹马分成5组,每组5匹马,每组分别进行比赛,标记A1、A2、A3、A4、A5、...、E1、E2、E3、E4、E5(5次)
  • 每组的第1名进行比赛A1、B1、C1、D1、E1得到的第1名为最终的第一名,假设为B1(1次,选出1匹)
  • 每组当前的第1名进行比赛A1、B2、C1、D1、E1得到的第1名为最终的第二名(1次,选出2匹)
  • 以此类推,每次比赛都可以选出一匹最快的马。

  总共5+1+1+1+1+1=10次

变形2:有38头牛,6条赛道,选出跑的最快的3头牛。

  无标记

  方法1(13次)

  • 将其中的36头牛分成6组,分别进行比赛,留下前3名,共18头牛,与没有参与比赛的牛总共20头(6次)
  • 将20头牛分成4组,每组5头牛,比赛留下前3名,共12头牛(4次)
  • 将12头牛分成2组,每组6头牛,比赛留下前3名,共6头牛(2次)
  • 剩下的6头牛比赛,得到最终的结果(1次)

  总共6+4+2+1=13次

  方法2(11次)

  • 从38头牛中随机挑出2头牛,不参与比赛(0次)
  • 从剩下的36头牛中选择跑的最快的3头牛(11次,同情况1)
  • 挑出的2头牛和选出的3头牛比赛,得到最终的结果(1次)

  总共11+1=12次

  有标记

  • 从38头牛中随机挑出2头牛,不参与比赛(0次)
  • 从剩下的36头牛中选择跑的最快的3头牛(8次,同情况2的方法1)
  • 最终比赛一次,得到结果(1次)

  总共8+1=9次

36辆车和6个赛道,筛选出最快的3辆车