首页 > 代码库 > 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辆车
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。