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
|
28
mxT52CRuqR6o5 2021-02-02 11:49:25 +08:00
|
29
doushiyinweini 2021-02-02 11:52:09 +08:00
分治法, 2 次
|
30
mxT52CRuqR6o5 2021-02-02 12:45:58 +08:00
|
31
lance6716 2021-02-02 13:22:15 +08:00 via Android
|
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
|
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
|
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 次? 不知道思路对不对 |
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
|
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
顺便提一下,各位看清题哦,不仅要知道哪个球是异常球,还要知道是轻还是重~~
|
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 次就能找出缺陷球并确定轻重 |
61
pkookp8 2021-02-02 20:35:10 +08:00 via Android
|
62
JeffGe 2021-02-02 20:47:02 +08:00 via Android
单从信息论的角度讲,所有不同可能性是“1 重、1 轻、2 重、2 轻、……”共 16 种,天平最多提供“左<右、左=右、左>右”3 种不同信息,确定异常球**且**确定异常球是轻是重至少需要 ceil(log3(16))=3 次,上面说 2 次的不用看绝对是错的。
|