? ? ? ? 今天看朋友發了一個老問題，一道很有意思的推理題：（轉載請指明出于breaksoftware的csdn博客）

? ? ? ? 小明和小強都是張老師的學生，張老師的生日是M月N日，2人都知道張老師的生日是下列10組中的一天：

? ? ? ? 3月4日 3月5日 3月8日
? ? ? ??6月4日 6月7日
? ? ? ??9月1日 9月5日
? ? ? ??12月1日 12月2日 12月8日
? ? ? ? 張老師將M值告訴了小明，將N值告訴了小強，張老師問他們知道他的生日是哪一天嗎？
? ? ? ? 小明說：如果我不知道的話，小強肯定不知道
? ? ? ? 小強說：本來我也不知道，但是現在我知道了
? ? ? ? 小明說：哦，那我也知道了
? ? ? ? 據上面信息，推斷出張老師的生日是哪一天？

? ? ? ? 這個邏輯題，如何用程序實現？其實這是一個建模過程，我們需要用專業的術語重新描述這個邏輯。

? ? ? ? 這個問題數據只有2個：月數和天數。邏輯是參雜2個人角度看問題的3句話。我們分析這個問題時，首先要保持第三者的視角，逐個從其他兩個視角去分析這個問題。然后就是建立模型，我們看這樣的數據有個特征：{Key,Value}鍵值對。但是可以看出這是個MultiMap，即一個鍵可以對應多個值。

? ? ? ? 我們沿著這個思路走.可以發現，站在小明的角度，我們可以將數據建立成一個MultiMap。他眼中的數據使用月數M為鍵，天數N為值。以后我們稱下表為“小明表”。

? ? ? ? 可以站在小強的角度，我們將數據建立成一個新的MultiMap。他眼中的數據使用天數N為鍵，月數M為值。以后我們稱下標為“小強表”。

? ? ? ? 我們再回到第三者的角度，可以得出，這兩張表對于小明和小強都是可見的。

? ? ? ? 我們將小明和小強的對話，一條一條轉換為約束條件。

? ? ? ? 1?小明說：如果我不知道的話，小強肯定不知道

? ? ? ? 小明是看了“小強表”之后得出以上結論。這句話意味著：他所知的M值在“小強表”中不存在Key Value唯一對應關系。即12月2日和6月7日，這兩個月份12和6都不是老師的生日月數。因為如果是M是12或6，小明在不知道N的情況下，無法給定如此“拽”的回答。于是逐步排除出一下結果（紅色代表排除的選項）

? ? ? ? 2?小強說：本來我也不知道，但是現在我知道了

? ? ? ? 小強在看到上圖后，得出上面結論。這個說明，小強知道的N在上表中是Key Value唯一對應關系。于是得出

? ? ? ? 因為小強知道N是多少，所以剩下的選項中，他知道正確答案了。只是我們還不知道。我們期待小明的話。

? ? ? ? 3?小明說：哦，那我也知道了

? ? ? ? 對于小明，他和我們一樣，可以看到上圖。于是他知道N的值只可能是1、4、8。于是修改“小明表”為

? ? ? ? 由于此時小明已經知道了答案。可以見得M值在上表中是Key Value唯一對應關系。于是我們可以排除3和12。得出

? ? ? ? 此時有兩個答案。我們此時結合篩選后的“小強表”

? ? ? ? 此時，我們可以說6月4日在“小強表”中已被排除，所以我們選擇9月1日。或者我們從這個兩個表中找到了唯一的共同選項，從而得知是9月1日。

? ? ? ? 草編了一下代碼

// ACM.cpp : 定義控制臺應用程序的入口點。
//#include "stdafx.h"
#include <list>
/*
小明和小強都是張老師的學生，張老師的生日是M月N日，
2人都知道張老師的生日是下列10組中的一天，
張老師將M值告訴了小明，將N值告訴了小強，
張老師問他們知道他的生日是哪一天嗎？
3月4日 3月5日 3月8日
6月4日 6月7日
9月1日 9月5日
12月1日 12月2日 12月8日
小明說：如果我不知道的話，小強肯定不知道
小強說：本來我也不知道，但是現在我知道了
小明說：哦，那我也知道了
據上面信息，推斷出張老師的生日是哪一天？
*/
struct stBirthday{int nMonth;int nDay;bool bMaybe;bool bMaybeSecond;bool bMaybeThird;
};static stBirthday g_BirthdayArray[] = {{3,4,false,false,true},{3,5,false,false,true},{3,8,false,false,true},{6,4,false,false,true},{6,7,false,false,true},{9,1,false,false,true},{9,5,false,false,true},{12,1,false,false,true},{12,2,false,false,true},{12,8,false,false,true},
};int g_nArrayCount = sizeof(g_BirthdayArray)/sizeof(stBirthday);typedef std::list<stBirthday> ListBirthday;
typedef ListBirthday::iterator ListBirthdayIter;void XiaoMingFirst(ListBirthday& listBirthday)
{// 小明知道月數后，說：如果我不知道，小強肯定也不知道// 這意味著小明看了他所知道月數里的每個天數在其他月數里都能找到// 于是天數具有唯一性的選項是“不可能”的for ( ListBirthdayIter it = listBirthday.begin(); it != listBirthday.end(); it++ ) {if ( it->bMaybe ) {// 該值可能在之后的邏輯中提前被設置，所以不用比較// 這個日期是存在可能的continue;}for ( ListBirthdayIter iter = it; iter != listBirthday.end(); iter++){if ( iter == it ) {// 不和自身比較continue;}if ( it->nDay == iter->nDay ) {// 第一個答案的提煉的思想就是：// 小明看了他所知道月數里的每個天數在其他月數里都能找到// 所以，沒有小明的答案，小強肯定不知道確切的幾月幾日// 于是，我們將有天數有重復的答案認定為可能的選項it->bMaybe = iter->bMaybe = true;}}}for ( ListBirthdayIter it = listBirthday.begin(); it != listBirthday.end(); it++){if ( it->bMaybe ) {continue;}// 經過上輪處理，需要將該月里可能同時存在“可能”和“不可能”的選項的可能性都設置為“不可能”// 因為小明看了他所知道月數里的每個日數在其他月數里“都”能找到,我們要配合“都”這個必要條件for ( ListBirthdayIter iter = listBirthday.begin(); iter != listBirthday.end(); iter++){if ( it->nMonth == iter->nMonth ) {iter->bMaybe = false;}}}
}void XiaoQiangFirst(ListBirthday& listBirthday)
{// 小強分析了小明回答后，回答：本來我也不知道，但是現在我知道了// 這意味著小明的答案給小強提供了月數信息// 因為小明的回答讓他在待選擇的多個結果中排除了其他可能性，只有一個選擇// 于是編碼的思路就是：// 1 在已經“不可能”的月數中，尋找其對應的天數在“可能”的月中是否有對應關系// 或者// 2 在已經“可能”的月數中，尋找其對應的天數在“不可能”的月中是否有對應關系// 以下編碼選擇1思路實現for ( ListBirthdayIter it = listBirthday.begin(); it != listBirthday.end(); it++ ) {if ( it->bMaybe ) {// 尋找“不可能”的月數，于是“可能”的月數不作為可選條件continue;}for ( ListBirthdayIter iter = listBirthday.begin(); iter != listBirthday.end(); iter++){if ( false == iter->bMaybe ){// 在找到一個“不可能”的月數情況下，尋找“可能”的月數，以作下步篩選continue;}if ( it->nDay == iter->nDay ) {// 存在對應關系，則該“可能”日期經過第二輪篩選，還是“可能”的iter->bMaybeSecond = true;}}}
}void XiaoMingSecond(ListBirthday& listBirthday)
{// 小明在聽到小強的回答后，說：哦，那我也知道了。// 這意味著小強的答案已經為小明提供了天數信息// 在可能眾多的選項中，小明卻知道了答案，// 證明信息經過小強篩選過后，小明所知道的月數中，只有一個天數答案for ( ListBirthdayIter it = listBirthday.begin(); it != listBirthday.end(); it++ ) {if ( false == it->bMaybeSecond ) {it->bMaybeThird = false;continue;}for ( ListBirthdayIter iter = it; iter != listBirthday.end(); iter++){if ( iter == it ) {// 不和自身比較continue;}if ( false == iter->bMaybeSecond || false == iter->bMaybeThird ) {// 不滿足條件的不做比較continue;}if ( it->nMonth == iter->nMonth ) {// 經過兩輪篩選，如果有兩個選項是同一個月數的// 則可以認為該數月的所有選項都是“不可能”for ( ListBirthdayIter iterIn = it; iterIn != listBirthday.end(); iterIn++){if ( it->nMonth == iterIn->nMonth ) {iterIn->bMaybeThird = false;}}}}}
}void TestBirthday()
{ListBirthday listBirthday;for ( int n = 0; n < g_nArrayCount; n++ ) {listBirthday.push_back(g_BirthdayArray[n]);}XiaoMingFirst(listBirthday);printf("The First Result:\n");for ( ListBirthdayIter it = listBirthday.begin(); it != listBirthday.end(); it++ ) {if ( it->bMaybe ){printf("Month:%d Day:%d\n", it->nMonth, it->nDay);}			}XiaoQiangFirst(listBirthday);printf("The Second Result:\n");for ( ListBirthdayIter it = listBirthday.begin(); it != listBirthday.end(); it++ ) {if ( it->bMaybeSecond ){printf("Month:%d Day:%d\n", it->nMonth, it->nDay);}			}XiaoMingSecond(listBirthday);printf("The Third Result:\n");for ( ListBirthdayIter it = listBirthday.begin(); it != listBirthday.end(); it++ ) {if ( it->bMaybeThird ){printf("Month:%d Day:%d\n", it->nMonth, it->nDay);}			}
}int _tmain(int argc, _TCHAR* argv[])
{TestBirthday();return 0;
}

總結

以上是生活随笔為你收集整理的使用程序解决一道逻辑推理题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。