算法——老鼠毒药问题
2019-06-12 Algorithm Java有16瓶水,其中一瓶有毒,小白鼠喝一滴有毒的水一小时后会死,要在一小时找出来哪瓶水有毒最少需要几只小白鼠 ?
构造题目
/**
* @author JianhuiChen
* @description 老鼠毒药问题
* @date 2019/6/12
*/
public class MousePoisonQuestion {
public static void main(String[] args) {
normalSolution();
}
/**
* 普通解法 16瓶水用16只老鼠来找 哪只死了代表哪瓶水有毒
*/
private static void normalSolution() {
final int bottleCount = 16;
List<Mouse> mouseList = new ArrayList<>();
for (int i = 0; i < bottleCount; i++) {
mouseList.add(new Mouse(i, Collections.singleton(i)));
}
findPoisonWater(bottleCount, mouseList, mouses -> mouses.stream()
.filter(Mouse::isDie)
.findFirst()
.get()
.getId());
}
/**
* 寻找有毒的水
*
* @param bottleCount 水的瓶数
* @param mouses 老鼠列表
* @param judge 根据老鼠喝完水的状态判断出毒药的编号
*/
private static void findPoisonWater(int bottleCount, List<Mouse> mouses, Function<List<Mouse>, Integer> judge) {
List<Water> waters = initWaters(bottleCount);
mouses.forEach(mouse -> mouse.setDie(waters));
// 一小时后
int resultPoisonId = judge.apply(mouses);
int poisonId = waters.indexOf(waters.stream().filter(Water::isPoison).findFirst().get());
Water water = waters.get(poisonId);
assert (water.isPoison()) : "判断有误,第" + poisonId + "瓶水不是毒药,正确答案是第" + resultPoisonId + "瓶";
System.out.println("恭喜你找出了包含毒药的水,共使用了" + mouses.size() + "只老鼠");
}
/**
* 初始化Len瓶水
*
* @param len 水瓶数
* @return 带有一瓶毒药的水列表
*/
private static List<Water> initWaters(int len) {
Boolean[] poisons = new Boolean[len];
poisons[new Random().nextInt(len)] = true;
return Arrays.stream(poisons)
.map(poison -> new Water(poison != null))
.collect(Collectors.toList());
}
/**
* 老鼠对象
*/
static class Mouse {
/**
* 老鼠喝过的水ID
*/
private Integer[] drinkWaterIds;
/**
* 老鼠ID
*/
private int id;
/**
* 老鼠是否死亡
*/
private boolean die;
Mouse(int id, Collection<Integer> drinkWaterIds) {
this.id = id;
this.drinkWaterIds = drinkWaterIds.toArray(new Integer[]{});
}
void setDie(List<Water> waters) {
this.die = Arrays.stream(drinkWaterIds)
.anyMatch(id -> waters.get(id).isPoison());
}
boolean isDie() {
return die;
}
int getId() {
return id;
}
}
/**
* 水对象
*/
static class Water {
/**
* 是否有毒
*/
private boolean poison;
Water(boolean poison) {
this.poison = poison;
}
boolean isPoison() {
return poison;
}
}
}
解题思考
显然,使用了十六只老鼠来找这瓶毒药肯定不是最优解,我们来想,16瓶水中有一瓶毒药一共有16种可能性,而老鼠有生存和死亡两种状态,假设我们使用0和1表示老鼠的生存与死亡,那么四只老鼠就能排列组合出16种可能性,我们来利用二进制排列出这16种情况。
🐭老鼠1 | 🐭老鼠2 | 🐭老鼠3 | 🐭老鼠4 | 🍺水 |
---|---|---|---|---|
0 | 0 | 0 | 1 🍺 | 瓶子1 |
0 | 0 | 1 🍺 | 0 | 瓶子2 |
0 | 0 | 1 🍺 | 1 🍺 | 瓶子3 |
0 | 1 🍺 | 0 | 0 | 瓶子4 |
0 | 1 🍺 | 0 | 1 🍺 | 瓶子5 |
0 | 1 🍺 | 1 🍺 | 0 | 瓶子6 |
0 | 1 🍺 | 1 🍺 | 1 🍺 | 瓶子7 |
1 🍺 | 0 | 0 | 0 | 瓶子8 |
1 🍺 | 0 | 0 | 1 🍺 | 瓶子9 |
1 🍺 | 0 | 1 🍺 | 0 | 瓶子10 |
1 🍺 | 0 | 1 🍺 | 1 🍺 | 瓶子11 |
1 🍺 | 1 🍺 | 0 | 0 | 瓶子12 |
1 🍺 | 1 🍺 | 0 | 1 🍺 | 瓶子13 |
1 🍺 | 1 🍺 | 1 🍺 | 0 | 瓶子14 |
1 🍺 | 1 🍺 | 1 🍺 | 1 🍺 | 瓶子15 |
排列下来即是
- 🐭老鼠1喝🍺 8,9,10,11,12,13,14,15
- 🐭老鼠2喝🍺 4,5,6,7,12,13,14,15
- 🐭老鼠3喝🍺 2,3,6,7,10,11,14,15
- 🐭老鼠4喝🍺 1,3,5,7,9,11,13,15
这样排列后,老鼠的生存与死亡状态都能得到一串二进制码,这串二进制码可以转换成有毒的瓶子信息,如
- 0010:表示🐭老鼠3死亡,其余🐭老鼠存活,代表🍺瓶子2是毒药
- 0000:表示没有🐭老鼠死亡,代表🍺瓶子16是毒药
编码实现
/**
* 使用二进制的思路解法
*/
private static void binarySolution() {
final int bottleCount = 16;
List<Mouse> mouseList = new ArrayList<>();
mouseList.add(new Mouse(1, Arrays.asList(8, 9, 10, 11, 12, 13, 14, 15)));
mouseList.add(new Mouse(2, Arrays.asList(4, 5, 6, 7, 12, 13, 14, 15)));
mouseList.add(new Mouse(3, Arrays.asList(2, 3, 6, 7, 10, 11, 14, 15)));
mouseList.add(new Mouse(4, Arrays.asList(1, 3, 5, 7, 9, 11, 13, 15)));
findPoisonWater(bottleCount, mouseList, mouses -> {
int num = -1;
for (Mouse m : mouses) {
num += Math.pow(2, m.isDie() ? (m.getId() - 1) : 0);
}
return num < 0 ? (bottleCount - 1) : num;
});
}
运行后程序将打印**“恭喜你找出了包含毒药的水,共使用了4只老鼠”**,代码运行成功了没错,但是通用性不足,只能够适用于16只老鼠的解法,能否编写一个根据瓶子数量作为参数的通用解法函数?只要理解解题思路,这个代码并不难,在此就不做演示了。
有兴趣的朋友可以在下方留言给出通用解法🐶
题目拓展
有16瓶水,其中只有一瓶水有毒,小白鼠喝一滴之后一小时会死。请问最少用多少只小白鼠,可以在1小时内找出至少14瓶无毒的水。
找14瓶无毒的水是可以转化为和上面那道一样的解题思路,我们将16瓶水分为8组两两一瓶,我们只需要找到一组水中包含毒药即可得到14瓶无毒的水,一组水只可能有两种状态,有毒或者无毒,所以我们可以将8组水看作8瓶水,至此题目就变成了“8瓶水用最少几只老鼠找那瓶有毒的水”,答案是3只。