这是为了在算法课上加分。问题状态
A king has a wine cellar of N bottles, and a single bottle has been poisoned.
The poison takes approximately a month to work. The king wants the exact bottle identified using the fewest testers possible within a months time.
我的解决方案是
将
N个瓶子分成M个批处理并使用“M 个测试器”第一个测试者品尝第一批和最后一批
第二位测试员品尝了第一批和第二批。
第三位测试员品尝了第二批和第三批。
继续进行 M 批处理，测试人员重叠批处理。
当品尝了受污染 Wine 的两名测试员生病时，该批处理的酒就被鉴定出来了。
M-2测试人员从受污染的批处理中给每个人留下一瓶，第三个生病的测试人员识别出受污染的瓶子。
但是，该算法需要双倍的工作时间:一个月用于识别受污染的批处理，第二个月用于识别受污染的瓶子。有没有更高效的算法？
最佳答案
我们可以用 log2(N) 来做具有非常简洁的算法的测试人员。
让我用一个简单的例子来证明它。假设 N = 1000 .
如果我们给瓶子贴上标签0通过999 , 然后每个瓶子都可以用一个唯一的二进制数表示，范围从 0000000000 (0 十进制)到 111100111 (999 十进制)。
声明:我们只需要10个测试人员就可以找到毒瓶。注:log2(N) = log2(1000) = 10 .
算法:对于M th 瓶子，我们首先得到 M 的 10 位二进制表示.如果i二进制数的第 bit 是 1 ，我们让 i th 测试员从瓶子里喝了酒。注:0 < M <1000, 0 < i <10 .
考虑一个例子，我们有 1st , 4th , 9th测试员死了，一个月后其他测试员还活着。我们得出结论 289th瓶子是自0100100001以来中毒的那个是十进制数的二进制表示 289 .
为什么是10测试人员足以识别中毒者 1000瓶子？
因为 10每个测试人员最后是死是活，我们总共可以有 1024组合，每个组合都可用于从多达 1024 中唯一识别一瓶中毒的瓶子瓶子。
关于算法设计——用最少的测试人员识别酒窖中的单瓶，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14406604/