IBM Ponder This #116 · 2007 年 12 月

通常，若 n 个零件中有坏件，且一次可以测试任意一组，准确知道该组是否含坏件，就可以通过二分在约 log₂n 次测试内找到一个坏件。

本题改为 n 个零件中只有一个坏件，且它每次被测试时，无论单独还是混在组中，都只有一半概率表现为失效，另一半概率通过。研究以下算法找到坏件所需测试次数的期望。n 很大，忽略分组人数取整等低阶项，把答案写成 C log₂n，C 保留小数点后四位。

1. 每次随机选当前候选的一半测试，直到某组失效，再在该组中递归。
2. 将第一问的组大小改为 a 倍候选数。最优 a 是多少？需要多少次测试？
3. 把候选随机分成两个等大组，轮流测试，直到一组失效，再在该组中递归。
4. 改为每次分成三个等大组，依次轮流测试，直到一组失效，再递归。
5. 可选附加问：第四种方法还不是最优算法。最优算法需要多少次测试？

解答

认真尝试后再打开

待补充。