赛马问题

64匹马,8个赛道,找出前4名最少比赛多少场

常规解法:8匹马,淘汰后四位

64匹马均分8组,每组淘汰末4位。

每组晋级的4匹马再与其他4匹马组合成8匹马,4组,每组淘汰末4位。

直到决出最后4位,共需8+4+2+1=15场

最优解

1.第一场

均分成8组,淘汰每组最后4位

2.第二场

每组第一比赛,选出全场第一,标记为a1

灰色均淘汰(因为a1>b1,b1>b2>b3,所以b4淘汰)

此时,要从除A1外的9匹马中选出全场第二三四名。

3.第三场

因为只有8条跑道,所以要刨除一匹马。选择刨除d1(因为b1>c1>d1,d1最好的情况为全场第四名,d1的情况取决于c1)

情况1:c1是第3(即c1为全场第四。此时d1不是全场第四),c1是3-7名,d1均不可能是全场第四,全场前四已经产生,无需再比

情况2:c1是第2(d1有可能是全场第四,要再比一场

d1和除b1 c1的其他6匹马,决出全场第四

总结

情况1:8+1+1=10

情况2:8+1+1+1=11

PS:刨除一匹马时也可以选择A4

全部评论
从第一名为根结点构建树 层数在四或以内的都是可能对象 也就可以得出最多10次
点赞 回复 分享
发布于 2025-04-11 17:33 广东

相关推荐

03-27 16:40
已编辑
门头沟学院 C++
26学院本太难了,很多公司机筛就给我刷了。机会都难拿到如果是简历存在问题也欢迎拷打————————————————————分割线——————————————————————2026.3.4更新:发完贴之后,时不时投递又收到了不少的笔试/面试邀请。主要是之前投递简历出去之后基本上都是沉默状态,年后好转了不少timeline:2026.01.21 文远知行笔试,半年多没刷算法题 ->挂 (后续HR说春招可以重新安排笔试)2026.2.4     小鹏汇天 技术一面,第二周收到结果 ->挂2026.2.12   大众Cariad代招 技术二面 ->Offer2026.2.28   多益网络技术面试,由于风评太差,一直在犹豫要不要接面试 ->推迟-----------分割线-----------2026.3 月前的某一天,临时去电网报名了二批计算机岗位的笔试2026.3.6 从上家公司实习离职,氛围最好的一家公司,leader 说可以帮忙转正,但是流程太长,而且我们部门据说只有一个 hc,更想要研究生,我很有可能是会被签外包公司在这里干活,就离职了。2026.3.9 入职新公司,大众Cariad 以外部公司的身份进组,项目组签了三年,后续三年应该都可以在这里呆,不知道有没有希望原地跳槽。2026.3.10 电网考试居然说我通过资格审查了,短信约我去参加资格审查,请假一天,买了 12 号晚上的机票回成都2026.3.15 参加国家电网计算机类笔试2026.3.17 电网出成绩了,感觉很低。觉得已经🈚️了2026.3.18 收到电网面试通知,通知 3.22-3.25 这个时间去面试,我的岗位只招 1 个人。据说面试只有 2-3 人,不知道能不能成功----------分割线-----------2026.3.21 电网面试结束,感觉回答的还勉勉强强,大概是2个岗位分别招1个人,一共11人面试,实际来了9人2026.3.27 出面试成绩,满分100分,早上10:20左右发现面试成绩46,我震惊了,没截图,后面过了十分钟重新看发现面试成绩给我改成58了。但同样震惊。朋友问我是不是把面试官打了,哈哈
点赞 评论 收藏
分享
评论
1
17
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务