个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
25
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++趣味算法之侦探推理由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说:
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 。
最后此篇关于C++趣味算法之侦探推理的文章就讲到这里了,如果你想了解更多关于C++趣味算法之侦探推理的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
25
4
0
我是一名优秀的程序员,十分优秀！