一道笔试题求答案

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

两次