最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

C++趣味算法之偵探推理

 更新時間:2021年12月02日 09:26:25   作者:指北針_N  
本文詳細講解了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 個字符。

輸入中不會出現連續(xù)的兩個空格,而且每行開頭和結尾也沒有空格。

輸出描述

如果你的程序能確定誰是罪犯,則輸出他的名字;如果程序判斷出不止一個人可能是罪犯,則輸出 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

算法實現

/*
大模擬問題
*/
 
#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++趣味算法之偵探推理,希望對大家有所幫助。在此也非常感謝大家對腳本之家網站的支持!

相關文章

  • 使用c++實現OpenCV繪制旋轉矩形圖形

    使用c++實現OpenCV繪制旋轉矩形圖形

    這篇文章主要給大家介紹了使用c++實現OpenCV繪制圖形旋轉矩形的方法案例,通過圖文及代碼形式進行了詳細的描述,有需要的朋友可以參考下,希望可以有所幫助
    2021-08-08
  • C++ 使用模板實現一個List的實例

    C++ 使用模板實現一個List的實例

    這篇文章主要介紹了 C++ 使用模板實現一個List的實例的相關資料,需要的朋友可以參考下
    2017-05-05
  • C++計算ICMP頭的校驗和實例

    C++計算ICMP頭的校驗和實例

    這篇文章主要介紹了C++計算ICMP頭的校驗和的方法,代碼簡單實用,對于校驗ICMP報文來說有不錯的實用價值,需要的朋友可以參考下
    2014-10-10
  • C++11中隱式類型轉換的實現示例

    C++11中隱式類型轉換的實現示例

    C++類型轉換分為:隱式類型轉換和顯式類型轉換,本文主要介紹了C++11中隱式類型轉換的實現示例,具有一定的參考價值,感興趣的可以了解一下
    2024-06-06
  • c++ 數組定義及初始化詳解

    c++ 數組定義及初始化詳解

    這篇文章主要介紹了c++ 數組定義及初始化詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-12-12
  • 詳解C++11的std::addressof源碼解析

    詳解C++11的std::addressof源碼解析

    std::addressof的作用是獲取一個對象的實際地址,即使這個對象的&操作符已被重載,本文詳細的介紹了源碼解析,感興趣的可以了解一下
    2021-06-06
  • C語言數據結構之二叉樹詳解

    C語言數據結構之二叉樹詳解

    二叉樹(Binary tree)是樹形結構的一個重要類型。許多實際問題抽象出來的數據結構往往是二叉樹形式。本文將通過示例詳細講解一下二叉樹,需要的可以參考一下
    2022-03-03
  • C語言實現任何文件的加密解密功能

    C語言實現任何文件的加密解密功能

    這篇文章主要為大家詳細介紹了C語言實現任何文件的加密解密功能,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-03-03
  • C語言讀取data.json文件并存入MySQL數據庫小案例(推薦)

    C語言讀取data.json文件并存入MySQL數據庫小案例(推薦)

    本文介紹如何使用C語言結合cJSON庫讀取JSON文件,并將數據存儲到MySQL數據庫中,示例代碼包括創(chuàng)建MySQL表的SQL語句和C語言代碼,以及如何編譯和運行程序,確保已安裝必要的庫以支持程序運行
    2024-10-10
  • C++中string使用+號與int拼接方式

    C++中string使用+號與int拼接方式

    這篇文章主要介紹了C++中string使用+號與int拼接方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-07-07

最新評論

平塘县| 公主岭市| 东平县| 若尔盖县| 黄梅县| 东山县| 福海县| 德阳市| 襄樊市| 北票市| 楚雄市| 阜南县| 兰州市| 定远县| 贞丰县| 望奎县| 丹巴县| 潞城市| 应城市| 新竹市| 叙永县| 南开区| 赣州市| 八宿县| 天津市| 柞水县| 娱乐| 绍兴市| 渝中区| 鸡东县| 涟源市| 册亨县| 青海省| 绍兴县| 岱山县| 莱西市| 美姑县| 金川县| 旬阳县| 西藏| 诸暨市|