一道笔试题求答案

[Yokin]

昨天的一道面试题,想了好久都没有答案，听说 V2EX 大佬多
大佬勿喷，初级开发,能力有限，没想到合适答案。
8 个外表一样的小球,其中 7 个球重量相同,1 个球为[异常球],可能重量更轻也可能更重,利用天平称重至少多少次可以确保找出这个[异常球],并且知道到底是轻了还是重了。
(1)请先说明思路。
(2)使用 js 实现此思路。
(3)如何从性能的角度优化第(2)步的 js 代码？

[stukiller]

第一秤：拿出 4 个球 2:2 秤，得出正常组 AAAA 异常组 BBBB
第二秤：分四组 AAA BBB A1 B1
情况 1 AAA=BBB 第三秤：正常 A1 和异常 B1
情况 2 AAA > BBB 或 AAA < BBB BBB 异常组，且得知异常球轻还是重。 第三秤：再 BBB 拿 2 个称下就好

[toan]

还要弄清楚异常的那个是重了还是轻了，所以楼上各位回答的好像都不准确。

[huang119412]

@Biwood 大致框架是这，但是每题都有变动，分 4 组，最好一次就能确定异常组，再一次就能确定重量，最坏 4+1，分 2 组，最好 2 次确定异常组，一次就能确定重量，最坏 3+1

[Lumuy]

4, 4 -> 4 一次二分
2, 2 -> 2 二次二分
1, 1 -> 1 三次二分
1, 1 替换一球，确定轻重

[Lumuy]

上面写错了，天平状态
2, 2 判断四分组
1, 1 判断二分组，平保持，不平换分组
1, 1 替换一球判断轻重

最少三次，最多四次

[Alixlucky]

16 楼正解，2 次就能找出来。

[mxT52CRuqR6o5]

@lance6716
称一次结果有三种，理想情况下每次操作可以砍到 1/3
我这边已经想到稳定称 3 次得出轻重的方案了

[mxT52CRuqR6o5]

@lance6716
当我没说，想的方案有点问题
如果按照上面的思路能得出有可能存在最差称 3 次的方案，就是不知道存不存在

[doushiyinweini]

分治法, 2 次

[mxT52CRuqR6o5]

@lance6716
第一次 124 356
第二次 123 457
第三次 158 234
算的我头大，大家帮我验算看看这个固定方案能不能解决这个问题

[lance6716]

@mxT52CRuqR6o5 30 楼这个不能识别 2 轻 5 重吧

另外天平能减少的信息量确实不是一半，是多少有空我再想想

[CareiOS]

line 面试的时候 CTO 出了这道题。

[superrichman]

找出异常球只要 2 次，找出异常球轻了还是重了要 3 次

[superrichman]

@superrichman 知道异常球更轻或更重只要 2 次，不知道要 3 次

[yaphets666]

我想知道 有没有人是 从来没看过类似这种题的方法 然后自己想出答案的?

[CareiOS]

如果要找出那个球是轻还是中就需要三次。
如果只是找出差异球就需要两次。

[leaveeel]

1 2 3 4 5 6 7 8

取 123456 六个球三三对比(123, 456)
情况 1:
①123 == 456, 7||8 异常
②17 == 23 ? 8 : 7, 异常球中取一个和三个正常球两两对比，找出异常球
③7<8||7>8, 异常球和正常球对比，得出轻重
3 次

情况 2:
①123 != 456, 1||2||3||4||5||6 异常，78 正常
②12 == 45 ? 3||6 : 1||2||4||5, 1245 相等 3||6 异常，否则 1||2||4||5 异常

③(3||6) 13 == 45 ? 6 : 3;
④(3||6) 3<6||3>6;
4 次，同情况 1

③(1||2||4||5) 12>45 ? (14>25 ? 1||5 : 2||4) : (14<25 ? 1||5 : 2||4), 两两对比(12, 45)然后交换一个球(24)，结果相同则是没交换的球异常，否则交换的球异常，这里假设 1||5 异常
④(1||2||4||5) 16 == 78 ？ 5 : 1;
⑤(1||2||4||5) 1<5||1>5, 同情况 1
5 次

[mxT52CRuqR6o5]

@lance6716
找到一种方案可以 7/8 找到异常球确定轻重，1/8 找到异常球但确定不了情重
三次找出异常并确定轻重的方法可能不存在

[mxT52CRuqR6o5]

我信息论水平有限，没法用科学的方法，足够完善的证出来 3 次找出异常并确定轻重的方案存不存在

[yzbythesea]

这是道脑筋急转弯（很早之前面 Intel 考的，当时给我说是 brain teaser ）。。。面试问这道写代码，我觉得只能写 `print 2`