zhaohanjiangit
zhaohanjiangit
2010-04-25 12:09
浏览 475
已采纳

白鼠与毒酒的算法问题

一个酒窖里有一千桶酒, 其中有一桶是毒酒 , 白鼠喝了毒酒一个星期后会死去。
现在问给你多少只白鼠(最少的),在一个星期内确定那桶毒酒。

给出算法过程

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • fivestaralex
    fivestaralex 2010-05-03 03:23
    已采纳

    设有N桶酒,有一桶是毒酒,编号从0到N-1,最少要K只白鼠
    显然,
    当N=2,K=1
    当N=3,K=2
    当N=4,K=2
    4桶酒编号0,1,2,3
    K=2,设有白鼠A和白鼠B
    A喝0,1,B喝0,2
    一星期后,有4种可能状态
    A死B死(0号有毒),A死B活(1号有毒),A活B死(2号有毒),A活B活(3号有毒)

    当N=5,K=3

    猜想白鼠的最终状态只有死活两种可能,通过白鼠一星期后的状态可以算出毒酒编号
    很自然想到二进制,例如当N=4时,0=00,1=01,2=10,3=11
    当N=8,K=3
    0=000,1=001,2=010,3=011,4=100,5=101,6=110,7=111
    白鼠A,B,C
    A喝0,1,2,3 (0XX)
    B喝0,1,4,5 (X0X)
    C喝0,2,4,6 (XX0)
    ABC的最终状态可以确定毒酒编号

    当N=1000时,可以类推至少要10只,你可以这样推出这10只白鼠具体是喝哪些编号的酒,规律很明显了

    回过来再想想,1000之内的任意一个数都可以用一个10位的二进制数表示(不够的话前面补0),白鼠与数位对应,第几位为0,则说明第几位的白鼠死了,而这个二进制的编号即为毒酒编号

    OK,够详细了吧

    点赞 评论
  • liaofeng_xiao
    liaofeng_xiao 2010-04-25 13:44

    10只老鼠

    老鼠都标上号

    这些老鼠药喝每一瓶水,每瓶水过来,老鼠喝了标1,不喝标0

    所有的水也都标上号

    一周后查看哪些老鼠死了,再看标号就OK。。。

    点赞 评论

相关推荐