PROJECT EULER · #0352
血液检测
Blood Tests
羊群中的每只
由于成本较高,主管兽医建议不要进行
将羊分为
- 如果结果为阴性,则该组中的所有羊都被视为没有病毒。
- 如果结果呈阳性,
将进行额外测试(对每只动物进行单独测试)以确定受影响的个体。
由于任何特定动物的感染概率仅为
- 阴性(无需更多测试),概率为
。 - 呈阳性(需要
额外测试),概率为 。
因此,每组的预期测试数量为
因此,平均仅使用
尽管我们刚刚描述的方案似乎非常有效,但它仍然可以相当大地改进(始终假设测试足够灵敏并且不存在因混合不同样本而引起的不利影响)。例如:
- 我们可以首先对所有
样本的混合物进行测试。可以证实,在大约 的情况下,该测试将为阴性,因此不需要进行更多测试。仅需要对其余的 进行进一步测试。 - 如果我们知道一组
中至少有一只动物被感染,并且第一个 个体检测结果为阴性,则无需对第五只动物进行检测(我们知道它一定被感染)。 - 我们可以尝试不同数量的组/每组中不同数量的动物,并在每个级别调整这些数量,以便最大限度地减少预期的测试总数。
为了简化非常广泛的可能性,我们在设计最具成本效益的测试方案时设置了一个限制:每当我们从混合样本开始时,在我们开始检查任何其他动物之前,必须对所有参与该样本的羊进行全面筛查(即必须对所有羊做出感染/无病毒的结论)。
对于当前的示例,事实证明,最具成本效益的测试方案(我们将其称为最佳策略)平均只需要
使用最佳策略,让
因此,
查找
将您的答案四舍五入到小数点后六位。
题解待补充
这道题的题目已收录,解题思路、代码和答案将在后续补充。