C++趣味算法之侦探推理攻略
游戏说明
「侦探推理」是一款经典的数学推理游戏,需要通过推理和判断,找出隐藏在谜题中的答案。而本篇文章将教大家利用C++编程实现这个游戏,并提供完整攻略。
游戏规则
游戏中,有5位嫌疑犯和5个证人,他们在房间内,相互之间发生了一些事情。现在,我们知道有3个嫌疑犯和2个证人的事情发生了,需要利用已知条件推理出真正的罪犯和证人。
- 五位嫌疑犯分别为:A、B、C、D、E;
- 五个证人分别为:1、2、3、4、5;
- 有3个嫌疑犯、2个证人参与了这起事件;
- 每个人都知道真实情况,但不会说谎。
以下是游戏主持人提供的10个陈述:
- A说:“我不是罪犯,1和3是证人”;
- B说:“2是证人”;
- C说:“我不是罪犯,4是证人”;
- D说:“我不是罪犯,5是证人”;
- E说:“我是罪犯,3是证人”;
- 1说:“A不是罪犯,B是罪犯”;
- 2说:“C不是罪犯,D是罪犯”;
- 3说:“E不是罪犯,A是罪犯”;
- 4说:“B不是罪犯,E是罪犯”;
- 5说:“D不是罪犯,C是罪犯”。
现在,你需要通过分析上述陈述,找出3个罪犯和2个证人,并用C++编程打印出答案。
解题思路
本游戏可以使用计算机程序求解,为了方便实现和理解,我们可以把每个人的陈述当做一个“约束条件”,在程序中对这些约束条件进行求解。
- 我们可以使用一个二维数组
constraint[5][5]
来表示每个人的陈述,其中第一维代表人,第二维代表陈述,如果第i个人的陈述j成立,那么constraint[i][j]
就是true
。 - 根据题目,假设第i个人是罪犯,那么此时由他提供的陈述一定全部是假话,被他排除的人就是其他的两个罪犯和一个证人。因此,我们可以找到所有能够推翻该假设的陈述,一一尝试,如果都不行,就说明假设成立。这个过程可以递归实现,每次假设下一个人是罪犯,直到找到3个罪犯为止。
- 同理,如果假设第i个人是证人,那么此时由他提供的陈述一定全部是真话,他所提到的罪犯已经排除,剩下的就是其他的两个证人和两个罪犯。同样可以递归实现,每次假设下一个人是证人,直到找到2个证人为止。
- 上述两个过程可以交替进行,因为找到一个罪犯就意味着找到一个证人,找到一个证人就意味着找到一个罪犯。
代码实现
#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个还是证人的假设为例:
- E说:“我是罪犯,3是证人”。这句话是假话,否则E就是罪犯,那么3就不可能是证人了。
- 1说:“A不是罪犯,B是罪犯”。这句话是假话,否则E不可能是罪犯,与1的陈述矛盾。
- 2说:“C不是罪犯,D是罪犯”。这句话是真话,否则E不可能是罪犯,1又不是罪犯,与2的陈述矛盾。
- 3说:“E不是罪犯,A是罪犯”。这句话是假话,否则E就不可能是证人,与E的陈述矛盾。
- 4说:“B不是罪犯,E是罪犯”。这句话是真话,否则E不可能是罪犯,与2的陈述矛盾。
- 5说:“D不是罪犯,C是罪犯”。这句话是假话,否则E不可能是罪犯,4又不是罪犯,与5的陈述矛盾。
根据上述推理,我们可以得出,如果假设第5个人是证人,那么3、4、E是罪犯,1、2是证人。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++趣味算法之侦探推理 - Python技术站