← 完整题目索引

PROJECT EULER · #0352

血液检测

Blood Tests

仅题目 · 待解原题 ↗

羊群中的每只 25 羊都必须接受罕见病毒检测,已知该病毒会影响羊群的 2%。 针对血液样本存在准确且极其灵敏的 PCR 测试,可产生明确的阳性/阴性结果,但非常耗时且昂贵。

由于成本较高,主管兽医建议不要进行25单独测试,而是可以使用以下程序代替:

将羊分为 5 组,每组中有 5 羊。 对于每组,5 样品混合在一起并执行单个测试。然后,

  • 如果结果为阴性,则该组中的所有羊都被视为没有病毒。
  • 如果结果呈阳性,5 将进行额外测试(对每只动物进行单独测试)以确定受影响的个体。

由于任何特定动物的感染概率仅为 0.02,因此每组的第一个测试(针对合并样本)将是:

  • 阴性(无需更多测试),概率为 0.985=0.9039207968
  • 呈阳性(需要 5 额外测试),概率为 10.9039207968=0.0960792032

因此,每组的预期测试数量为 1+0.0960792032×5=1.480396016
因此,平均仅使用 1.480396016×5=7.40198008 测试即可筛选所有 5 组,这比 70% 节省了巨大的成本!

尽管我们刚刚描述的方案似乎非常有效,但它仍然可以相当大地改进(始终假设测试足够灵敏并且不存在因混合不同样本而引起的不利影响)。例如:

  • 我们可以首先对所有 25 样本的混合物进行测试。可以证实,在大约60.35%的情况下,该测试将为阴性,因此不需要进行更多测试。仅需要对其余的 39.65% 进行进一步测试。
  • 如果我们知道一组 5 中至少有一只动物被感染,并且第一个 4 个体检测结果为阴性,则无需对第五只动物进行检测(我们知道它一定被感染)。
  • 我们可以尝试不同数量的组/每组中不同数量的动物,并在每个级别调整这些数量,以便最大限度地减少预期的测试总数。

为了简化非常广泛的可能性,我们在设计最具成本效益的测试方案时设置了一个限制:每当我们从混合样本开始时,在我们开始检查任何其他动物之前,必须对所有参与该样本的羊进行全面筛查(即必须对所有羊做出感染/无病毒的结论)。

对于当前的示例,事实证明,最具成本效益的测试方案(我们将其称为最佳策略)平均只需要 4.155452 测试!

使用最佳策略,让 T(s,p) 代表筛选 s 羊群中任何个体中存在 p 概率的病毒所需的平均测试次数。
因此,T(25,0.02)=4.155452T(25,0.10)=12.702124 四舍五入到小数点后六位。

查找 p=0.01,0.02,0.03,0.50T(10000,p)
将您的答案四舍五入到小数点后六位。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。