有4瓶药,其中一瓶有毒,老鼠喝到有毒的药水会死掉,每只老鼠只能喝一次,但是药水可以混到一起喝,那最少要几只老鼠才能找出哪瓶药有毒。
求求大佬帮帮我
这道题考察了我们对bit位的灵活运用,4对应的二进制为100,有三位,则理论上需要三只老鼠
具体操作逻辑是二进制为1的老鼠和对应的药水:
1 = 001 即 一号老鼠喝一号药水
2 = 010 即 二号老鼠喝二号药水
3 = 011 即 一号和二号老鼠喝三号药水
4 = 100 即 三号老鼠喝四号药水
根据哪几支老鼠死了就可以得出哪瓶药水有毒,(转换成对应的十进制)
对于这个题的话可以不需要第三只老鼠,通过反向判断,如果前两只老鼠都没死则可认定第四瓶药水有毒,所以最少只需要两只老鼠即可
代码参考,支持任何瓶药水的解决方案:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def get_toxic_num(mouseStatus: list, num):
'''
mouseStatus: 服药后老鼠的状态,0代表活着,1代表死亡
num: 药水总数
return: 返回有毒药水的编号
'''
toxicNum = int(''.join([str(i) for i in mouseStatus[::-1]]), 2)
if not toxicNum:
toxicNum = num
return toxicNum
def mouse_feed(potionNum):
'''
potionNum: 药水总数
return: 显示喝药水的方案, 返回需要的老鼠数
'''
num_bin = list(str(bin(potionNum))[2:])
needMouse = len(num_bin)
if num_bin[0] == '1' and '1' not in num_bin[1:]: # 如果二进制是以1开头,后面都是0的话则可以少用一只老鼠(如2,4,8等)
potionNum -= 1
needMouse -= 1
feeds = []
for i in range(potionNum):
num = list(str(bin(i+1))[2:])[::-1]
feeds.append([j+1 for j in range(len(num)) if num[j] == '1'])
for i in range(len(feeds)):
print('%d号药水需要给:' % (i+1), end='')
for j in feeds[i]:
print(j, end='号老鼠 ')
print('喝')
return needMouse
if __name__ == '__main__':
num = 4 # 药水数量
print('喂养方案:')
needMouse = mouse_feed(num)
print('%d瓶药水至少需要%d只老鼠'%(num, needMouse))
mouseStatus = [0, 0, 0]
print('根据服药后老鼠的状态得出,第%d瓶药水有毒' % (get_toxic_num(mouseStatus, num)))
您好,我是有问必答小助手,您的问题已经有小伙伴帮您解答,感谢您对有问必答的支持与关注!