題目描述
明明同學最近迷上了偵探漫畫《柯南》并沉醉于推理游戲之中，于是他召集了一群同學玩推理游戲。游戲的內容是這樣的，明明的同學們先商量好由其中的一個人充當罪犯（在明明不知情的情況下），明明的任務就是找出這個罪犯。接著，明明逐個詢問每一個同學，被詢問者可能會說：
證詞內容：
I am guilty.
I am not guilty.
XXX is guilty.
XXX is not guilty.
Today is XXX
證詞含義：
我是罪犯
我不是罪犯
xxx 是罪犯（ xxx 表示某個同學的名字）
xxx 不是罪犯
今天是xxx （ xxx 表示星期幾，是 Monday Tuesday wednesday Thursday Fnday Saturday 其中之一）
證詞中出現的其他話，都不列入邏輯推理的內容。明明所知道的是，他的同學中有 N 個人始終說假話，其余的人始終說真。現在，明明需要你幫助他從他同學的話中推斷出誰是真正的兇手，請記住，兇手只有一個！
輸入描述
輸入若干行。
第一行有三個整數，M（1 ≤ M ≤ 20）、N（1 ≤ N ≤ M）和P（1 ≤ P ≤ 100）；M 是參加游戲的明明的同學數，N 是其中始終說謊的人數，P 是證言的總數。
接下來 M 行，每行是明明的一個同學的名字（英文字母組成，沒有主格，全部大寫）。
往后有 P 行，每行開始是某個同學的名宇，緊跟著一個冒號和一個空格，后面是一句證詞，符合前表中所列格式。證詞每行不會超過 250 個字符。
輸入中不會出現連續的兩個空格，而且每行開頭和結尾也沒有空格。
輸出描述
如果你的程序能確定誰是罪犯，則輸出他的名字；如果程序判斷出不止一個人可能是罪犯，則輸出 Cannot Determine；如果程序判斷出沒有人可能成為罪犯，則輸出 Impossible。
輸入輸出樣例
輸入
3 1 5
MIKE
CHARLES
KATE
MIKE: I am guilty.
MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??
輸出
MIKE
運行限制
最大運行時間：1s
最大運行內存：128M
算法實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
/*大模擬問題*/ #include <bits/stdc++.h>using namespace std; //m：總人數 n：始終說謊人數 p：說話的總數int m, n, p;//judge[i]：第i句話是真是假，真1假-1不清楚0 w[i]：第i局話是編號多少的的人說的int judge[21], w[200];//err：矛盾標記 nx：當前可能的罪犯int err, nx;//name[i]：所有人名字（編號為1~m） say[i]：所有人說的話 day[i]：所有星期幾名字string name[100], say[200];string day[10] = {"0", "Today is Sunday.", "Today is Monday.", "Today is Tuesday.", "Today is Wednesday.", "Today is Thursday.", "Today is Friday.", "Today is Saturday.", }; //sset函數標記一個人說話真假void sset(int who, int x) { if (judge[who] == -x) err = 1; //如果一個人既說真話又說假話，則矛盾 else judge[who] = x;} int main() { cin >> m >> n >> p; for (int i = 1; i <= m; i++) { cin >> name[i]; } for (int i = 1; i <= p; i++) { string nm; cin >> nm; //輸入說這句話人的名字 nm.erase(nm.end() - 1); //刪除nm中冒號，便于判斷這句話編號多少的的人說的 for (int j = 1; j <= m; j++) { if (name[j] == nm) w[i] = j; } getline(cin, say[i]); say[i].erase(say[i].begin()); //刪除say[i]中的起始空格 } for (int td = 1; td <= 7; td++) { //暴力枚舉今天是星期幾 for (int px = 1; px <= m; px++) { //暴力枚舉罪犯編號是幾號 err = 0; //清除標記 memset(judge, 0, sizeof(judge)); //初始化為不清楚真假 //依次判斷每一句說的話 for (int i = 1; i <= p; i++) { int who = w[i]; //說這句話人的編號 //如果一個人是罪犯，并且說自己是罪犯，則說的就是真話，否則就是假話 if (say[i] == "I am guilty.") sset(who, px == who ? 1 : -1); //如果一個人不是罪犯，并且說自己不是罪犯，則說的就是真話，否則就是假話 if (say[i] == "I am not guilty.") sset(who, px != who ? 1 : -1); //如果一個人說今天是星期幾，說對了就是真話，說錯了就是假話 for (int j = 1; j <= 7; j++) { if (say[i] == day[j]) sset(who, j == td ? 1 : -1); } //如果一個人說其他人不是罪犯，說對了就是真話，說錯了就是假話 for (int j = 1; j <= m; j++) { if (say[i] == name[j] + " is guilty.") sset(who, j == px ? 1 : -1); if (say[i] == name[j] + " is not guilty.") sset(who, j != px ? 1 : -1); } } int cnt = 0; //說假話的人數 int no = 0; //不清楚真假的的人數 for (int i = 1; i <= m; i++) { if (judge[i] == -1) //假 cnt++; if (judge[i] == 0) //不清楚 no++; } //如果出現Impossible的情況，err = 1，出現矛盾 //如果cnt<=n<=cnt+no,即假設合理 if (!err && cnt <= n && cnt + no >= n) { if (nx && nx != px) { //如果出現了兩個合理的罪犯 cout << "Cannot Determine"; return 0; } else { nx = px; } } } } if (!nx) cout << "Impossible"; else cout << name[nx]; return 0;} |
以上所述是小編給大家介紹的C++趣味算法之偵探推理，希望對大家有所幫助。在此也非常感謝大家對服務器之家網站的支持！
原文鏈接：https://blog.csdn.net/Hello_world_n/article/details/121630843
