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