这是算法类中的额外功劳.问题表明
国王有一个N瓶酒窖,一瓶已经中毒.
毒药大约需要一个月的时间.国王希望在几个月的时间内使用最少的测试者识别确切的瓶子.
我的解决方案是
将N瓶子分成几M批并使用"M测试员"
第一个测试者尝试第一个和最后一个批次
第二个测试者尝试第一批和第二批.
第三个测试者尝试第二和第三批.
继续M批次,测试人员重叠.
当两位品尝了受污染葡萄酒的测试人员生病时,已确定该批次.该M-2测试人员留下每个品尝到来自被感染的很多一瓶,而生病的第三测试仪识别被感染的瓶子.
然而,该算法需要两倍的时间分配工作:一个月识别受污染的批次,第二个月识别受污染的瓶子.有更高效的算法吗？
我们可以log2(N)通过一个非常简洁的算法与测试人员一起完成.
让我用一个简单的例子来演示它.假设N = 1000.
如果我们标记瓶子0通过999,则每个瓶可通过唯一的二进制数范围从表示0000000000(0十进制)至111100111(999十进制).
声明:我们只需要10名测试人员就可以找到有毒的瓶子.注意:log2(N) = log2(1000) = 10.
算法:对于Mth瓶,我们首先得到10位二进制表示M.如果i二进制数的位数是1,我们让i测试人员从瓶子里喝酒.注意:0 < M <1000, 0 < i <10.
考虑我们有一个例子1st,4th,9th测试仪正在死亡和其他测试者在一个月后还活着.我们得出结论,289th瓶子是中毒的,因为它0100100001是十进制数的二进制表示289.
为什么10测试人员足以识别1000瓶中有毒的？
因为10最终每个测试者都死了或活着,我们可以有多种1024组合,每种组合都可以用来唯一地识别一个瓶子中毒的1024瓶子.
这是一个经典的谜题,所以我不想立即给出答案,但这里有一个暗示:假设你将酒瓶分成两组,每组包含一半瓶子,然后每个人测试一个人.那会让你有办法缩小哪一瓶中毒到一半的瓶子.
所以问题是 - 有没有办法提出许多不同的方法将酒瓶分成两半并同时运行上述方法？作为提示,请考虑N的二进制表示.
希望这可以帮助!