C++趣味算法之偵探推理
題目描述
明明同學(xué)最近迷上了偵探漫畫《柯南》并沉醉于推理游戲之中,于是他召集了一群同學(xué)玩推理游戲。游戲的內(nèi)容是這樣的,明明的同學(xué)們先商量好由其中的一個人充當(dāng)罪犯(在明明不知情的情況下),明明的任務(wù)就是找出這個罪犯。接著,明明逐個詢問每一個同學(xué),被詢問者可能會說:
證詞內(nèi)容:
I am guilty.
I am not guilty.
XXX is guilty.
XXX is not guilty.
Today is XXX
證詞含義:
我是罪犯
我不是罪犯
xxx 是罪犯( xxx 表示某個同學(xué)的名字)
xxx 不是罪犯
今天是xxx ( xxx 表示星期幾,是 Monday Tuesday wednesday Thursday Fnday Saturday 其中之一)?
證詞中出現(xiàn)的其他話,都不列入邏輯推理的內(nèi)容。明明所知道的是,他的同學(xué)中有 N 個人始終說假話,其余的人始終說真。現(xiàn)在,明明需要你幫助他從他同學(xué)的話中推斷出誰是真正的兇手,請記住,兇手只有一個!
輸入描述
輸入若干行。
第一行有三個整數(shù),M(1 ≤ M ≤ 20)、N(1 ≤ N ≤ M)和P(1 ≤ P ≤ 100);M 是參加游戲的明明的同學(xué)數(shù),N 是其中始終說謊的人數(shù),P 是證言的總數(shù)。
接下來 M 行,每行是明明的一個同學(xué)的名字(英文字母組成,沒有主格,全部大寫)。
往后有 P 行,每行開始是某個同學(xué)的名宇,緊跟著一個冒號和一個空格,后面是一句證詞,符合前表中所列格式。證詞每行不會超過 250 個字符。
輸入中不會出現(xiàn)連續(xù)的兩個空格,而且每行開頭和結(jié)尾也沒有空格。
輸出描述
如果你的程序能確定誰是罪犯,則輸出他的名字;如果程序判斷出不止一個人可能是罪犯,則輸出 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
運(yùn)行限制
最大運(yùn)行時間:1s
最大運(yùn)行內(nèi)存:128M
算法實現(xiàn)
/*
大模擬問題
*/
#include <bits/stdc++.h>
using namespace std;
//m:總?cè)藬?shù) n:始終說謊人數(shù) p:說話的總數(shù)
int m, n, p;
//judge[i]:第i句話是真是假,真1假-1不清楚0 w[i]:第i局話是編號多少的的人說的
int judge[21], w[200];
//err:矛盾標(biāo)記 nx:當(dāng)前可能的罪犯
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函數(shù)標(biāo)記一個人說話真假
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; //清除標(biāo)記
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; //說假話的人數(shù)
int no = 0; //不清楚真假的的人數(shù)
for (int i = 1; i <= m; i++) {
if (judge[i] == -1) //假
cnt++;
if (judge[i] == 0) //不清楚
no++;
}
//如果出現(xiàn)Impossible的情況,err = 1,出現(xiàn)矛盾
//如果cnt<=n<=cnt+no,即假設(shè)合理
if (!err && cnt <= n && cnt + no >= n) {
if (nx && nx != px) { //如果出現(xiàn)了兩個合理的罪犯
cout << "Cannot Determine";
return 0;
} else {
nx = px;
}
}
}
}
if (!nx)
cout << "Impossible";
else
cout << name[nx];
return 0;
}
以上所述是小編給大家介紹的C++趣味算法之偵探推理,希望對大家有所幫助。在此也非常感謝大家對腳本之家網(wǎng)站的支持!
相關(guān)文章
從c++標(biāo)準(zhǔn)庫指針萃取器談一下traits技法(推薦)
本篇文章基于gcc中標(biāo)準(zhǔn)庫源碼剖析一下標(biāo)準(zhǔn)庫中的模板類pointer_traits,并且以此為例理解一下traits技法,對c++ traits技法源碼分析感興趣的朋友跟隨小編一起看看吧2021-07-07
C語言如何實現(xiàn)Unix時間戳與本地時間轉(zhuǎn)化
這篇文章主要介紹了C語言如何實現(xiàn)Unix時間戳與本地時間轉(zhuǎn)化的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
Ubuntu配置sublime text 3的c編譯環(huán)境的具體步驟
下面小編就為大家?guī)硪黄猆buntu配置sublime text 3的c編譯環(huán)境的具體步驟。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-03-03

