C++趣味算法之侦探推理

C++趣味算法之侦探推理攻略

游戏说明

「侦探推理」是一款经典的数学推理游戏，需要通过推理和判断，找出隐藏在谜题中的答案。而本篇文章将教大家利用C++编程实现这个游戏，并提供完整攻略。

游戏规则

游戏中，有5位嫌疑犯和5个证人，他们在房间内，相互之间发生了一些事情。现在，我们知道有3个嫌疑犯和2个证人的事情发生了，需要利用已知条件推理出真正的罪犯和证人。

1. 五位嫌疑犯分别为：A、B、C、D、E；
2. 五个证人分别为：1、2、3、4、5；
3. 有3个嫌疑犯、2个证人参与了这起事件；
4. 每个人都知道真实情况，但不会说谎。

以下是游戏主持人提供的10个陈述：

1. A说：“我不是罪犯，1和3是证人”；
2. B说：“2是证人”；
3. C说：“我不是罪犯，4是证人”；
4. D说：“我不是罪犯，5是证人”；
5. E说：“我是罪犯，3是证人”；
6. 1说：“A不是罪犯，B是罪犯”；
7. 2说：“C不是罪犯，D是罪犯”；
8. 3说：“E不是罪犯，A是罪犯”；
9. 4说：“B不是罪犯，E是罪犯”；
10. 5说：“D不是罪犯，C是罪犯”。

现在，你需要通过分析上述陈述，找出3个罪犯和2个证人，并用C++编程打印出答案。

解题思路

本游戏可以使用计算机程序求解，为了方便实现和理解，我们可以把每个人的陈述当做一个“约束条件”，在程序中对这些约束条件进行求解。

1. 我们可以使用一个二维数组constraint[5][5]来表示每个人的陈述，其中第一维代表人，第二维代表陈述，如果第i个人的陈述j成立，那么constraint[i][j]就是true。
2. 根据题目，假设第i个人是罪犯，那么此时由他提供的陈述一定全部是假话，被他排除的人就是其他的两个罪犯和一个证人。因此，我们可以找到所有能够推翻该假设的陈述，一一尝试，如果都不行，就说明假设成立。这个过程可以递归实现，每次假设下一个人是罪犯，直到找到3个罪犯为止。
3. 同理，如果假设第i个人是证人，那么此时由他提供的陈述一定全部是真话，他所提到的罪犯已经排除，剩下的就是其他的两个证人和两个罪犯。同样可以递归实现，每次假设下一个人是证人，直到找到2个证人为止。
4. 上述两个过程可以交替进行，因为找到一个罪犯就意味着找到一个证人，找到一个证人就意味着找到一个罪犯。

代码实现

#include <iostream>
using namespace std;

bool constraint[5][5]; // 前5个代表嫌疑犯，后5个代表证人

// 判断该假设下是否有矛盾
bool check(bool suspect[]) {
    for (int i = 0; i < 5; i++) {
        int num_false = 0;
        int num_unknown = 0;
        for (int j = 0; j < 5; j++) {
            if (constraint[i][j]) { // 第i个人陈述j成立
                if (suspect[j % 5] == (j >= 5)) {
                    // j表示这是关于哪个人的陈述，如果是关于证人则要减去5
                    // 如果当前假设与陈述矛盾，则计数器+1
                    num_false++;
                } else {
                    num_unknown++;
                }
            }
        }
        if (num_false == 3 || (num_false == 2 && num_unknown == 0)) {
            // 如果当前假设下有矛盾，则返回false
            return false;
        }
    }
    return true;
}

// 寻找罪犯
bool findSuspect(bool suspect[], int count) {
    if (count == 3) { // 找到3个罪犯
        return true;
    }
    for (int i = 0; i < 5; i++) {
        if (suspect[i]) { // 如果i已经被排除
            continue;
        }
        suspect[i] = true;
        if (check(suspect)) { // 如果假设成立
            if (findSuspect(suspect, count + 1)) {
                return true; // 递归查找下一个罪犯
            }
        }
        suspect[i] = false;
    }
    return false;
}

// 寻找证人
bool findWitness(bool witness[], int count) {
    if (count == 2) { // 找到2个证人
        return true;
    }
    for (int i = 5; i < 10; i++) {
        if (witness[i - 5]) { // 如果i已经被排除
            continue;
        }
        witness[i - 5] = true;
        if (check(witness)) { // 如果假设成立
            if (findWitness(witness, count + 1)) {
                return true; // 递归查找下一个证人
            }
        }
        witness[i - 5] = false;
    }
    return false;
}

int main() {
    bool suspect[5] = {false}; // 初始假设下五个嫌疑犯都不是罪犯
    bool witness[5] = {false}; // 初始假设下五个证人都不是证人
    findSuspect(suspect, 0);
    findWitness(witness, 0);
    cout << "罪犯是：";
    for (int i = 0; i < 5; i++) {
        if (suspect[i]) {
            cout << char('A' + i) << " ";
        }
    }
    cout << endl << "证人是：";
    for (int i = 0; i < 5; i++) {
        if (witness[i]) {
            cout << i + 1 << " ";
        }
    }
    return 0;
}

示例说明

以第5个还是证人的假设为例：

1. E说：“我是罪犯，3是证人”。这句话是假话，否则E就是罪犯，那么3就不可能是证人了。
2. 1说：“A不是罪犯，B是罪犯”。这句话是假话，否则E不可能是罪犯，与1的陈述矛盾。
3. 2说：“C不是罪犯，D是罪犯”。这句话是真话，否则E不可能是罪犯，1又不是罪犯，与2的陈述矛盾。
4. 3说：“E不是罪犯，A是罪犯”。这句话是假话，否则E就不可能是证人，与E的陈述矛盾。
5. 4说：“B不是罪犯，E是罪犯”。这句话是真话，否则E不可能是罪犯，与2的陈述矛盾。
6. 5说：“D不是罪犯，C是罪犯”。这句话是假话，否则E不可能是罪犯，4又不是罪犯，与5的陈述矛盾。

根据上述推理，我们可以得出，如果假设第5个人是证人，那么3、4、E是罪犯，1、2是证人。