一道笔试题求答案

2021-02-01 21:52:53 +08:00
 Yokin
昨天的一道面试题,想了好久都没有答案，听说 V2EX 大佬多
大佬勿喷，初级开发,能力有限，没想到合适答案。
8 个外表一样的小球,其中 7 个球重量相同,1 个球为[异常球],可能重量更轻也可能更重,利用天平称重至少多少次可以确保找出这个[异常球],并且知道到底是轻了还是重了。
(1)请先说明思路。
(2)使用 js 实现此思路。
(3)如何从性能的角度优化第(2)步的 js 代码？
4823 次点击
所在节点    职场话题
62 条回复
pkookp8
2021-02-02 20:35:10 +08:00
@pkookp8 知道为什么可以 3 次了
第一次，123 对 456，不相等(左重)则
第二次，14 对 25

球有三种状态，3*8 有 24 种状态
天平有轻重相等，3^3 等于 27>24
JeffGe
2021-02-02 20:47:02 +08:00
单从信息论的角度讲，所有不同可能性是“1 重、1 轻、2 重、2 轻、……”共 16 种，天平最多提供“左<右、左=右、左>右”3 种不同信息，确定异常球**且**确定异常球是轻是重至少需要 ceil(log3(16))=3 次，上面说 2 次的不用看绝对是错的。

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/750433

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX