问题描述

100瓶水，一瓶有毒，有一种试纸，不过需要一个小时才能出结果，问最少需要几片试纸才能在一小时内找到有毒的那一瓶。

答案

7

算法

算法的思想就是把数字用二进制表示。

算法详细

首先我们需要准备七张试纸：

1. 然后对瓶子的编号进行二进制排序
   比如：一号瓶子是000 0001；七号瓶子是000 0111；100号瓶子则是110 0100。
2. 按编号把瓶子的液体滴到试纸上
   比如：一号瓶是000 0001，就把一号液体滴到1号试纸；7好瓶是000 0111，把七号液体滴到1、2、3号试纸上。
3. 静等试纸变色
   如果是1、3、5、7号试纸均变色，那么对应的101 0101 = 85号瓶就是有毒的。

算法的代码实现

#include <iostream>
#include <bitset>

using namespace std;

int findPoisonousBottle(bool testResults[]) {
    int bottleNumber = 0;
    for (int i = 0; i < 7; ++i) {
        if (testResults[i]) {
            bottleNumber |= (1 << i);
        }
    }
    return bottleNumber;
}

int main() {
    // 示例：假设测试后第0、2、5位试纸变蓝（从低位到高位）
    bool testResults[7] = {true, false, true, false, false, true, false};
    
    int poisonousBottle = findPoisonousBottle(testResults);
    cout << "有毒的瓶子编号是：" << poisonousBottle << endl;
    
    return 0;
}

参考文献

宋云飞.西安财经大学.2020.09.15