一道有趣的算法题:15个瓶子,4只老鼠,测试哪瓶有毒?

请听题

有15个瓶子,其中最多有一瓶有毒,现在有四只老鼠,喝了有毒的水之后,第二天就会死。如何在第二天就可以判断出哪个瓶子有毒?

基本思路

  用二进制给每个瓶子进行编码0001-1111,如下图所示。四只老鼠分别喝第n位是1的瓶子的水,比如第1只老鼠喝1(0001)、3(0011)、5(0101)、7(0111)、9(1001)、11(1011)、13(1101)、15(1111)号瓶子的水。第二天,再通过4只老鼠的存活状态的组合来判断具体哪一瓶有毒。对于老鼠的存活状态,有生和死两种状态,0表示存活,1表示死亡,比如0011,即第1、2只老鼠死亡,第3、4只老鼠存活,0011进制表示的瓶子为3号瓶子,因此3号瓶子有毒。具体组合和结果如下图所示。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
- (void)drugWater:(NSString *)mice {
NSInteger drug = 0; // 有毒的瓶子编号
int mices[miceNum] = {0};

for (NSInteger i = 0; i < [mice length]; i++) {
mices[i] = [[mice substringWithRange:NSMakeRange(i, 1)] intValue];
}

for (NSInteger i = 0; i < miceNum; i++) {
drug |= (mices[i] << (miceNum - i - 1));
}

if (drug == 0) {
NSLog(@"%@", @"无毒");
} else {
NSLog(@"有毒的瓶子是第 %ld 瓶", (long)drug);
}
}

相关说明:

  • 方法传的mice参数为,4只老鼠的存活状态的字符串,比如0011。
  • 根据之前的分析结果,我们用位运算来得出有毒的瓶子号即可。

本文标题:一道有趣的算法题:15个瓶子,4只老鼠,测试哪瓶有毒?

文章作者:kim逸云

发布时间:2019年10月15日 - 10:10

最后更新:2020年01月03日 - 16:01

原始链接:http://cloverkim.com/mouse-drug-water.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。


------本文结束感谢阅读------
0%