这是一道很多人知道的经典题目,其中的逻辑推理堪称短小精悍试题的典范。
题目:
张老师的生日为M月D日,他将M值告诉给了小明,将D值告诉给了小强。然后给出如下这些日期:
3月4日,3月5日,3月8日,6月4日,6月7日,9月1日,9月5日,12月1日,12月2日,12月8日。
张老师:你们知道我的生日是哪天吗?
小明:如果小强不知道,那我也不知道。
小强:刚才我不知道,现在我知道了。
小明:我也知道了。
分析:
这是一类典型的条件推理问题。通常采用的方式,是通过条件的有序叠加,筛选出最终答案。
标记:
引入如下标记:
M0:张老师生日日期的月份,
D0:张老师生日日期的日子,
M:表示常量月,
D:表示常量日,
m:表示变量月,
d:表示变量日,
{MD}:张老师给出的所有日期的集合,
{d*{MD}}:表示 {d|任意日期md属于{MD},有md的日为d} 这样的集合,
{d~M0*{MD}}:表示 {d|任意日期md属于{MD},有md的月为M0,md的日为d} 这样的集合,
{d`M0*{MD}}:表示 {d|任意日期md属于{MD},有md的月为M0,md的日不为d} 这样的集合,
{m*{MD}}:表示 {m|任意日期md属于{MD},有md的月为m} 这样的集合,
{m~D0*{MD}}:表示 {m|任意日期md属于{MD},有md的日为D0,md的月为m} 这样的集合,
{m`D0*{MD}}:表示{m|任意日期md属于{MD},有md的日为D0,md的日不为d} 这样的集合。
解答:
(1)条件1:如果小强不知道,那小明也不知道。
首先此时,还不知道小强知道不知道。
如果小强不知道,根据条件1,有{d~M0|MD}包含于{d`M0|MD}。则由此得到一个日期集合{MD1a}。
如果小强知道,则条件1不可用,不过这时更容易推理,{m~D0|MD}与{m`D0|MD}无交集,则由此得到一个日期集合{MD1b}。
因此,{MD1a}和{MD1b}共同构成了条件1能推理出的日期集合{MD1}。
(2)条件2:小强在得知条件1前,不知道;在得知条件1后,知道。
首先,小强在得知条件1前不知道,说明{MD1b}可以排除。
然后,由于得知了条件1,小强也知道了目前的答案在{MD1a}中。
接着,考虑条件2,说明{m~D0|{MD1a}}只有一个元素,即单元集或称模为1,且该元素即为M0,这样小强就知道了M0和D0,就知道了正确的日期。
(3)条件3:小明在得知条件2后,知道了正确的日期。
首先,小明在听小强说“刚才不知道”后(即条件2中的“小强在得知条件1前,不知道”),就知道小强在得知条件1前并不知道答案,即小强此时知道了正确的日期在{MDa1}中,排除了{MD1b}。
然后,小明听小强说“现在知道”后(即条件2中的“小强在得知条件1后,知道”),就知道对于{d*{MD1a}}中个任意元素dx,有{m~dx*{MD1a}}只有一个元素,即是一个单元集或称模为1。
(4)旁观者的逻辑推理
在小明和小强的对话中,小强是在小明第一句话之后就知道了正确的日期。而小明是在小强的话之后才知道的,并说出了整个对话中的最后一句话。而旁观者,是在得知最后一句话后,才唯一确定了正确答案的。具体的逻辑过程,可依照(1)至(3)中的推理。
(5)程序源代码:
(6)程序解读
类MonDay用于表示日期。
类MonDayUtil中提供了逻辑推理中可以能用到的推理方式的工具,比如:
getDatesWithDuplicateDays:输入{MD},输出{MD}中满足m是md的日,且{d~m*{MD}}与{d`m*{MD}}有交集的md构成的集合。
getDatesWithDistinctMon:输入{MD},输出{MD}中满足d是md的月,且{m~d*{MD}}与{m`d*{MD}}无交集的md构成的集合。
getDatesWithDistinctDay:输入{MD},输出{MD}中满足m是md的月,且{d~m*{MD}}与{d`m*{MD}}无交集的md构成的集合。
具体的逻辑过程,与逻辑分析一致,只是把数学语言,转化为计算机语言。
分享到:
相关推荐
这是本人的第4大原创作品,不过与之前微软面试100题系列,红黑树系列,及十三个经典算法研究系列相比,编程艺术系列的某些篇文章的作者除了我本人自己,或多或少还得到了不少朋友的支持,我把这些朋友组织起来,成立...
【Python编程题】题目:猜数字游戏(10).zip
【Python编程题】题目:猜数字游戏(7).zip
【Python编程题】题目:猜数字游戏(6).zip
【Python编程题】题目:猜数字游戏(4).zip
【Python编程题】题目:猜数字游戏(9).zip
【Python编程题】题目:猜数字游戏(8).zip
【Python编程题】题目:猜数字游戏(5).zip
【Python编程题】题目:猜数字游戏(2).zip
【Python编程题】题目:猜数字游戏(1).zip
计算机编程艺术.编程不仅是工作,还是艺术,好书分享,经典好书,
UNIX编程艺术 UNIX编程艺术 UNIX编程艺术 UNIX编程艺术 UNIX编程艺术 UNIX编程艺术 UNIX编程艺术 UNIX编程艺术 UNIX编程艺术 UNIX编程艺术 UNIX编程艺术 UNIX编程艺术
JAVA经典编程试题:一些有关于java算法的试题及解法
UNIX编程艺术 书签 无水印 中文版
java编程200例(附:JAVA文档完全解读中文版)。针对java编程核心思想;以实例代码的形式剖析java技术;实用性强;内附JAVA文档中文版;可以边编程边参考文档。一举两得啊。极力推荐。
JAVA并发编程艺术 高清pdf : 1.并发变成的挑战 2. java并发机制的底层实现原理 3. java 内存模型 4. java并发编程基础 5.java中的锁。。。。。。。
Oracle 9i&10g编程艺术:深入数据库体系结构.pdf
电子协会 Python 1 - 6 级考试说明
《javascript dom编程艺术:第2版》讲述了javascript、dom 和html5 的基础知识,着重介绍dom 编程技术背后的思路和原则:平稳退化、渐进增强和以用户...《javascript dom编程艺术:第2版》适合web 设计师和开发人员阅读。
UNIX编程艺术(中文).pdfUNIX编程艺术(中文).pdfUNIX编程艺术(中文).pdfUNIX编程艺术(中文).pdfUNIX编程艺术(中文).pdfUNIX编程艺术(中文).pdfUNIX编程艺术(中文).pdfUNIX编程艺术(中文).pdf