一道笔试题求答案

[Yokin]

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

[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 个称重,
找到异常