一道笔试题求答案
大佬勿喷,初级开发,能力有限,没想到合适答案。
8 个外表一样的小球,其中 7 个球重量相同,1 个球为[异常球],可能重量更轻也可能更重,利用天平称重至少多少次可以确保找出这个[异常球],并且知道到底是轻了还是重了。
(1)请先说明思路。
(2)使用 js 实现此思路。
(3)如何从性能的角度优化第(2)步的 js 代码?
n 个球称几次能找出异常重量的球是有公式的
具体咋操作,就慢慢想吧
暂时没抽象出公式出来……
最少三次,最多四次
另外天平能减少的信息量确实不是一半,是多少有空我再想想
取 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 次
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 )
“`
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 )
“`
根据高赞的回答,试着整活一下哈:
因为一个小球最多提供三个信息:
重、轻、普通重量
所以按三进制来分配小球编号;
又因为 3^2=9,大于 8 ;
所以最小 2 次?
不知道思路对不对
猪那个直接靠本身就可以判断结果……而小球这个,还要弄两组做对比,所以情况不一样
三进制给小球编号:
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 这边轻的情况; 共计四次
(二)中应该是这样:
然后对比第二位为 0 的球和第二位为 1 的球
球有三种状态,3*8 有 24 种状态
天平有轻重相等,3^3 等于 27>24