使用程序解决一道逻辑推理题

今天看朋友发了一个老问题，一道很有意思的推理题：（转载请指明出于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;
}