一道笔试题求答案

[Yokin]

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

[JerryY]

看过类似的题目，好像是位运算符做的？ 2^3 = 8 ？如果不对，证明我记错了。

[Jooooooooo]

称球的题目本身一搜都是答案

n 个球称几次能找出异常重量的球是有公式的

[LadyChunsKite]

称球的题目我记得好像是三等分来做。
但是你这个重量更轻也可能更重好像把问题复杂化了。

[lance6716]

概率空间{1 轻、1 重、2 轻、2 重…}共 16 种，理想情况下每次操作砍一半，所以最少要操作 4 次

具体咋操作，就慢慢想吧

[yeqizhang]

先各放 3，
如果在这 6 个球里，再各放 2，
如果在这 4 个球里，再各放 1，可以找到剩下的最后的 2 个中有一个异常球，
两球中再拿一球和六正常球中的一个对比就可以知道了。
最坏的情况 4 次，最快是 3 次。

暂时没抽象出公式出来……

[Caballarii]

@yeqizhang 最快不在这 6 个球里，两次

[yeqizhang]

上面漏了最坏的一次，应该是 5 次了。
比二等分还复杂，二等分称好像也是这个结果……是我想复杂了……

[yeqizhang]

@Caballarii 不知道轻重，所以还得称两次。其实理想情况下，一次各放 1 个，运气好是两次能找到轻重的那个。不过题目是确保找出来咯……

[lemon6]

3 次啊，2 分法！！

[lxy42]

有 v 友发过一篇文章解释这个问题: https://www.v2ex.com/t/504875?p=1

[bushenx]

二分，最好 3 最坏 4 吧

[szxczyc]

最快不是两次嘛，332，两两测。最少两次。

[hawhaw]

三次

[kunkunzhang]

三次，2 的 3 次为 8，建议搜索同款题，关键词：8 只小鼠 毒药

[k3Sv1]

只要两次。因为天平结果有三种。3^2=9 。

[IvanLi127]

三个和三个比，如果等重，那么剩下两个比，得出结论；否则轻的那三个中拿两个比。如果等重，剩下的一个轻；否则答案也出来了。

[Biwood]

单纯用二分法也不行，因为不知道异常球的轻重，第一次二分的时候你取哪边？

[Biwood]

二分法还不如枚举法，至少能达到目的，最坏 n 的平方，在此基础上再优化

[JKeita]

3 次
1 。两个与两个比较，相同说明在另外 4 个里，反之这在当前比较的 4 个里。
2 。拿出未比较的两个球，与上一步比较过的一组进行比较，相同说明在另一组（这一步就能看出到底是大还是小）
3 。同上再拿一颗球与上一步中其中一颗球比较，相同则说明另一颗为异。

[DonaldY]

两次

[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`

[mxT52CRuqR6o5]

第一次 123 456
第二次 124 357
第三次 134 267
可以三次称量确定 1-7 轻重或 8 缺陷（再称一次就能确定 8 轻重）

[kifile]

来一份伪代码吧

def find_different_ball(balls: list):
if len(balls) == 1:
return balls[0]
balls_1, balls2, balls_3, balls_other = split(balls) // 将球等个数分为三份，如果不能等分，剩余球放入 ball_other
if sum(balls) == sum(balls):
target_balls = balls_3 + balls_other
if len(target_balls) == 2:
# 至少保留三个球方便比对
(target_balls) += balls_1[0]
return find_different_ball(target_balls )
else:
target_balls = balls_1 + balls_2
if len(target_balls) == 2:
# 至少保留三个球方便比对
(target_balls) += balls_3[0]

return find_different_ball(target_balls )

[mxT52CRuqR6o5]

@lance6716
哦哦，想到 3 次的方案了，要动态策略不能固定策略
第一次 123 456
如果不平衡则
第二次 124 357
第三次 134 267
如果第一次平衡
第二次 1 7
第三次 1 8

[kifile]

来一份伪代码吧

```
def find_different_ball(balls: list):
if len(balls) == 1:
return balls[0]
balls_1, balls2, balls_3, balls_other = split(balls) // 将球等个数分为三份，如果不能等分，剩余球放入 ball_other
if sum(balls) == sum(balls):
target_balls = balls_3 + balls_other
if len(target_balls) == 2:
# 至少保留三个球方便比对
(target_balls) += balls_1[0]
return find_different_ball(target_balls )
else:
target_balls = balls_1 + balls_2
if len(target_balls) == 2:
# 至少保留三个球方便比对
(target_balls) += balls_3[0]

return find_different_ball(target_balls )
```

[kifile]

不支持 code?

[verzqli]

3 次，12 个球也是三次，知乎有篇文章讲过这个

[Exin]

因为 12 个球是 3 次，所以 8 个球我猜是 2 次

[lwlizhe]

记得知乎看过一个最少几头猪检测哪桶水有毒的问题；好像差不多；
（ https://www.zhihu.com/question/60227816 ）

根据高赞的回答，试着整活一下哈：

因为一个小球最多提供三个信息：
重、轻、普通重量

所以按三进制来分配小球编号；

又因为 3^2=9，大于 8 ；

所以最小 2 次？

不知道思路对不对

[lwlizhe]

@lwlizhe 发现问题漏洞了~

猪那个直接靠本身就可以判断结果……而小球这个，还要弄两组做对比，所以情况不一样

[zzh7982]

至少两次 ，随机选两个球正好重量不想等 1 次，第二次换掉一个球再称就能称出来

[ila]

1,8 个球平均分 ab 两份(每份 4 个),
2,把 a 份平均分成 a1 和 a2 两份(每份 2 个),
3,a1 和 a2 称重不相同,
4,把 a1 平均分成两份 a11 和 a12,
5,如果 a11 和 a12 称重不一样,则异常球在 a1 里
6,把 a2 平均分成 a21 和 a22 两份(相同重),
7,如果 a11 和 a21 称重不一样重,
8,那 a11 就是异常球.
至此,至少称重 3 次.

[shyrock]

如果给 8 个球的可能状态编码，因为 8 个里面有一个不正常，并且可能轻或者重，所以可能的状态编码共有 8x2=16 个。我们用于探寻问题空间的手段是天平，每次使用天平最多可以把球分成三组，左托盘、右托盘和不上天平，所以实际上可用一个三进制编码来记录称量结果，而要覆盖全部 16 种情况，3^2<16<3^3，所以至少需要三次称量。
称量操作的要点是：
1.尽量平均分组；
2.根据前面称量的结果动态剪掉可能性分支

[newInstance]

@Alixlucky 第二次为什么要拿轻的呢 （否则轻的那三个中拿两个比。）为什么说异常球不可能在重的那边呢？
@Alixlucky

[lwlizhe]

@lwlizhe 不过做法思路好像差不多，可能还有优化空间吧

三进制给小球编号：

000 001 002
010 011 012
020 021

因为只有 8 个球，所以结尾和第二位为 2 的天然少一个，所以不对其进行对比；

（一）第一步对比结尾为 0 的球和结尾为 1 的球；
因此是：
000 010 020 和 001 011 021

（ 1.1 ）如果平衡，那么异常球是结尾是 2 的那俩，随便找个球分别对比下，就知道异常球是哪个，是轻是重；所以三次；

（ 1.2 ）如果不平衡，那么异常球的结尾是 0 或 1 ；记录一下；

（二）然后对比第二位为 0 的球和结尾为 1 的球；
因此是：
000 001 002 和 010 011 012

（ 2.1 ）如果平衡，那么异常球第二位是 2，结合第一步中所述的，异常球结尾是 0 或 1 ；范围确定为 020 和 021，再随便找个球分别对比下，就知道异常球是哪个，是轻是重；所以四次；

（ 2.2 ）如果不平衡，那么异常球第二位是 0 或 1，因此范围确定为 000，010，011，001 这四个；

（三）尴尬的是，这次没有第三位可供再次对比了，都是 0 ；
但是因为 000 跟 010 、001 都组队过，唯一没组队的是 011，所以这次对比的是
000，011 和 010 001

这次肯定是不平衡的，但是可以根据上次结果判断一下：

上次结果是 000 001 这边重，这次是 000，011 这边重的话，这说明异常球是这两次中相同的部分；所以是 000 或 010 ；
那么随便拿个球对比下 000，如果相等，那就是 010 轻；如果不等，那就是 000 重；四次；

上次结果是 000 001 这边重，这次是 000，011 这边轻的话，那说明异常球是两次中不同的部分，所以是 001 和 011 ；跟上面同理，可验证是异常球及其轻重

同理可验证 000 001 这边轻的情况； 共计四次

[lwlizhe]

顺便提一下，各位看清题哦，不仅要知道哪个球是异常球，还要知道是轻还是重~~

[lwlizhe]

@lwlizhe 更正：

（二）中应该是这样：
然后对比第二位为 0 的球和第二位为 1 的球

[lambdAlan]

最好 3 次最坏 4 次吧。不妨设更轻
第一次：左右各 4 个，分为 A,B 两队堆。拿出较轻的那一堆 A
第二次：将较轻的那一堆 4 个分为 2 份
2.1 如果平衡，，说明 A 中的 4 个是正常的，进一步说明球是较重的且存在 B 堆中，此时将 B 拿去称，进入第三次
2.2 如果不平衡，拿出较轻的一边，还剩 2 个，此时再进行一次即可，也就是三次。
第三次：将 B 中的 4 个分为 2 份，因为球较重，这次选出较重的一头（还剩 2 个）再称一次即可

[pkookp8]

第一次 12 比 34，相等则
第二次 12 比 78，相等则
第三次 1 比 5，相等则
第四次 1 比 6

[mxT52CRuqR6o5]

第一次称 123,456
如果不平衡则
第二次称 124,357
第三次称 134,267
左重 左重 左重 ->1 重
左轻 左轻 左轻 ->1 轻
左重 左重 左轻 ->2 重
左轻 左轻 左重 ->2 轻
左重 左轻 左重 ->3 重
左轻 左重 左轻 ->3 轻
左轻 左重 左重 ->4 重
左重 左轻 左轻 ->4 轻
左轻 左轻 平衡 ->5 重
左重 左重 平衡 ->5 轻
左轻 平衡 左轻 ->6 重
左重 平衡 左重 ->6 轻
如果第一次平衡
第二次称 1,7 -> 7 轻或 7 重
第三次称 1,8 -> 8 轻或 8 重
只要称 3 次就能找出缺陷球并确定轻重

[ila]

@szxczyc 是的,最理想两次,
3 个和 3 个称重相同,
剩下 2 个里其中 1 个和 3 个里的其中 1 个称重,
找到异常

[pkookp8]

@pkookp8 知道为什么可以 3 次了
第一次，123 对 456，不相等(左重)则
第二次，14 对 25

球有三种状态，3*8 有 24 种状态
天平有轻重相等，3^3 等于 27>24

[JeffGe]

单从信息论的角度讲，所有不同可能性是“1 重、1 轻、2 重、2 轻、……”共 16 种，天平最多提供“左<右、左=右、左>右”3 种不同信息，确定异常球**且**确定异常球是轻是重至少需要 ceil(log3(16))=3 次，上面说 2 次的不用看绝对是错的。