儿童文学

儿童文学-西方文学www.hy2811.com

乌有国王遇到了个难题:国王与毒酒

发布时间:2019-08-01 编辑 :本站 / 13次点击
您现在的位置:儿童文学 > 当代文学 > 正文
TAG:

乌有国王遇到了个难题:国王与毒酒

分析与解答答案:只需要2名囚犯就可以保证找出毒酒。

这是一道很有意思的题目。

首先我们看题目说囚犯喝下毒酒后23~24小时毒发,自然就会想,23人够吗?显然23人是可以的(每人喝22种酒,在23~24小时内毒死一人,确定毒酒在这22种之内,剩下22人每人喝一种,在46~48小时内就可以确定毒酒),问题是23人是最少的人数吗?题友们可能会联想到之前我们发过一道类似的题,用老鼠试毒药(公众号中回复老鼠与毒药查看),背后的思路是二进制编码,所以那题用10只老鼠就可以在1000瓶水中找出1瓶毒药(因为21o=1024>1000)。 那么本题只需从500桶酒中找出1桶毒酒,理应用更少的人。 根据上题的思路,9人就可以找出毒酒(用二进制编码,29=512>500),问题是9人是最少的人数吗?(具体的方法可在公众号中回复老鼠与毒药参考该期问题的方法)再读一下题目,发现本题和老鼠试毒药题除了测试样本数量不同以外,还有中毒时间的不同。 本题的中毒时间为23~24小时,而共有48小时可以测试,也就是说可以测试两轮,于是测试人数可以减少到8人(2^8×2=512>500),那么8人就是最少的人数了吗?进一步思考,我们发现,可以把500桶酒分成32组(25=32),每组15~16桶(24=16),第一轮5个人在23~24小时判断出毒酒在哪一组(25=32),毒死一人,第二轮剩下的4人在46~48小时判断出毒酒是哪一桶(24=16)。

这样看来,5人应该是最少的测试人数了。 以上的方法背后的思路都是二进制,有没有其他思路呢?本题的死亡时间非常精确,在23~24小时之间,又有什么用处呢?下面请看题友会微信群里(回复题友会可查看加入方法)的大神们的奇思妙解:“两个囚犯就够了!把500桶酒摆成23×23的矩阵(实际上23×22=506已经超过500)。

囚犯A每隔一小时喝一行的取样混合液,囚犯B每隔一小时喝一列的取样混合液,然后根据两人的死亡时间,就可以确定毒酒是哪桶了。 ”本题很容易和前面老鼠试毒药的题混淆,误以为都可以利用二进制方法找出最佳解。

实际上本题因为死亡时间的精确性、毒发时间与测试时间的时间差,使建立坐标成为可能。 换一种思路,也许你就会发现一片新的天地。 拓展思维:(1)如果需要测试的酒的数量有10000桶,那么最少需要几名囚犯呢?(2)如果需要测试的毒酒的数量有2桶,那么最少需要几名囚犯呢?。