一道笔试题求答案

重量

异常

思路

答案

62 条回复 • 2021-02-02 20:47:02 +08:00

1

JerryY

2021-02-01 21:56:59 +08:00

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

2

Jooooooooo

2021-02-01 21:57:54 +08:00

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

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

3

LadyChunsKite

2021-02-01 22:04:14 +08:00

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

4

lance6716

2021-02-01 22:11:36 +08:00 via Android

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

具体咋操作，就慢慢想吧

5

yeqizhang

2021-02-01 22:15:13 +08:00 via Android

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

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

6

Caballarii

2021-02-01 22:24:01 +08:00

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

7

yeqizhang

2021-02-01 22:24:38 +08:00 via Android

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

8

yeqizhang

2021-02-01 22:29:56 +08:00 via Android

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

9

lemon6

2021-02-02 00:22:26 +08:00

1

3 次啊，2 分法！！

10

lxy42

2021-02-02 00:28:34 +08:00

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

11

bushenx

2021-02-02 01:10:35 +08:00 via Android

二分，最好 3 最坏 4 吧

12

szxczyc

2021-02-02 02:35:19 +08:00 via iPhone

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

13

hawhaw

2021-02-02 06:37:33 +08:00 via Android

三次

14

kunkunzhang

2021-02-02 08:50:42 +08:00

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

15

k3Sv1

2021-02-02 08:55:35 +08:00 via iPhone

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

16

IvanLi127

2021-02-02 09:04:12 +08:00 via Android

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

17

Biwood

2021-02-02 09:04:42 +08:00 via Android

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

18

Biwood

2021-02-02 09:09:13 +08:00 via Android

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

19

JKeita

2021-02-02 09:15:13 +08:00

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

20

DonaldY

2021-02-02 09:24:52 +08:00

两次

21

stukiller

2021-02-02 10:02:37 +08:00

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

22

toan

2021-02-02 10:13:00 +08:00

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

23

huang119412

2021-02-02 10:16:00 +08:00

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

24

Lumuy

2021-02-02 11:20:06 +08:00

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

25

Lumuy

2021-02-02 11:24:47 +08:00

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

最少三次，最多四次

26

Alixlucky

2021-02-02 11:36:54 +08:00

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

27

mxT52CRuqR6o5

2021-02-02 11:40:33 +08:00

1

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

28

mxT52CRuqR6o5

2021-02-02 11:49:25 +08:00

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

29

doushiyinweini

2021-02-02 11:52:09 +08:00

分治法, 2 次

30

mxT52CRuqR6o5

2021-02-02 12:45:58 +08:00

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

31

lance6716

2021-02-02 13:22:15 +08:00 via Android

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

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

32

CareiOS

2021-02-02 13:25:41 +08:00

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

33

superrichman

2021-02-02 13:34:14 +08:00 via iPhone

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

34

superrichman

2021-02-02 13:40:59 +08:00 via iPhone

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

35

yaphets666

2021-02-02 13:44:43 +08:00

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

36

CareiOS

2021-02-02 13:47:15 +08:00

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

37

leaveeel

2021-02-02 13:56:59 +08:00

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 次

38

mxT52CRuqR6o5

2021-02-02 13:57:48 +08:00

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

39

mxT52CRuqR6o5

2021-02-02 14:00:03 +08:00

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

40

yzbythesea

2021-02-02 14:01:11 +08:00

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

41

mxT52CRuqR6o5

2021-02-02 14:04:19 +08:00

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

42

kifile

2021-02-02 14:07:37 +08:00

来一份伪代码吧

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 )

43

mxT52CRuqR6o5

2021-02-02 14:09:46 +08:00

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

44

kifile

2021-02-02 14:10:41 +08:00

来一份伪代码吧

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

45

kifile

2021-02-02 14:11:00 +08:00

不支持 code?

46

verzqli

2021-02-02 16:59:09 +08:00

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

47

Exin

2021-02-02 17:04:41 +08:00

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

48

lwlizhe

2021-02-02 17:32:22 +08:00

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

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

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

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

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

所以最小 2 次？

不知道思路对不对

49

lwlizhe

2021-02-02 17:34:44 +08:00

@lwlizhe 发现问题漏洞了~

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

50

zzh7982

2021-02-02 17:38:59 +08:00

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

51

ila

2021-02-02 17:40:00 +08:00

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 次.

52

shyrock

2021-02-02 18:27:32 +08:00

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

53

newInstance

2021-02-02 18:43:25 +08:00

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

54

lwlizhe

2021-02-02 18:44:27 +08:00

@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 这边轻的情况；共计四次

55

lwlizhe

2021-02-02 18:46:37 +08:00

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

56

lwlizhe

2021-02-02 18:53:23 +08:00

@lwlizhe 更正：

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

57

lambdAlan

2021-02-02 19:04:37 +08:00

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

58

pkookp8

2021-02-02 19:33:28 +08:00 via Android

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

59

mxT52CRuqR6o5

2021-02-02 20:06:10 +08:00

2

第一次称 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 次就能找出缺陷球并确定轻重

60

ila

2021-02-02 20:08:50 +08:00

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

61

pkookp8

2021-02-02 20:35:10 +08:00 via Android

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

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

62

JeffGe

2021-02-02 20:47:02 +08:00 via Android

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