酷应用

腾讯面试题：64 匹马，8 赛道，找出最快的 4 匹最少要几次?

百家 作者：程序员的那些事 2022-05-09 19:48:58


01
故事起源
有64匹马，8条赛道，要找出最快的4匹马，最少要几次呢？
补充：
1、不能计时哈，不然就没有意义了，题目就是要考察逻辑推理
2、默认马的速度不变哈，这是理想的数学模型，所以不能考虑其他的因素



02
初步思考
很多同学可能第一反应就是，这个问题肯定不简单，应该有一些技巧，但技巧是啥呢，又一时想不出来。
其实呢，先别想得太复杂了，比如我现在就问你一个问题，有没有可能存在有一匹不用跑？
答案当然是不行。



03
分析
那也就是每一匹都得先跑一次，64匹，8个赛道，那就先分8组跑8次。
每一组都会得到8匹的相对速度，也就是在同一组内的名次。
为了方便描述，我们用编号来表示。如A组里面的名次分别用来表示。
因为我们只需要找出最快的4匹，那么肯定不属于最快的4匹，同理把每一组的后4名先排除。
现在每一组内都有相对名次，但不同的组间是不知道的。如果把A组和B组放一起，下面的情况都可能存在。
因为是要找最快的，所以选择每组的第一名再出来跑一次，这样落后的第一名所在的整组都可以排除。为了描述方便，把最快到最慢的第一名所在的组依次重新命名为A，B...H组。
组间的第一名有了名次关系，可以发现一定不属于前4名，因为都在他们前面。同理可排除。同时是最快的，一定属于前4。那接下来只需在剩下的9匹中找出前3。
除去，其余8匹跑一次。如果在第3名或者更后，那说明已经选出了前3名，也不用再跑了，否则再取前3和一起跑一次，即可得结果。
最多11次一定可以选出最快的4匹。


04
总结

这种思维题，其实是很难直接就想清楚整个过程。可以先想得简单一点，往下推一步再看，逐步推进就可以引导出正确的结果了。


- EOF -

推荐阅读  点击标题可跳转

1、如果美国把根域名服务器封了，中国会从网络上消失吗？

2、看完微软大神写的求平均值代码，我意识到自己还是 too young了

3、响应乌克兰“制裁”呼吁：Oracle 和 SAP 暂停俄罗斯业务，GitHub 限制俄罗斯获取相应技术


关注「程序员的那些事」加星标，不错过圈内事

点赞和在看就是最大的支持❤️

关注公众号：拾黑（shiheibook）了解更多

[广告]赞助链接：

四季很好，只要有你，文娱排行榜：https://www.yaopaiming.com/
让资讯触达的更精准有趣：https://www.0xu.cn/

*文章为作者独立观点，不代表 爱尖刀 立场
本文由 程序员的那些事发表，转载此文章须经作者同意，并请附上出处( 爱尖刀 )及本页链接。
原文链接 https://www.ijiandao.com/2b/baijia/430139.html
腾讯
图库
程序员的那些事 程序员的那些事
公众号 关注网络尖刀微信公众号
随时掌握互联网精彩
赞助链接
百度热搜榜
排名 热点 搜索指数
iTrust
AiDeep Ued
关于我们 联系我们 升级日志 法律声明 广告服务 侵删通道
Copyright © 2021 K2CMS All rights reserved.
京ICP备14006288号