编程艺术家经典试题解读：猜生日问题 |
您所在的位置：网站首页 › 猜生日的逻辑题 › 编程艺术家经典试题解读：猜生日问题 |
编程艺术家经典试题解读：猜生日问题
|
阅读更多
这是一道很多人知道的经典题目，其中的逻辑推理堪称短小精悍试题的典范。 题目： 张老师的生日为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）程序源代码： package com.sinosuperman.test; import java.util.ArrayList; import java.util.List; public class Test { /** * @param args */ public static void main(String[] args) { List dates = new ArrayList(); dates.add(new MonDay(3, 4)); dates.add(new MonDay(3, 5)); dates.add(new MonDay(3, 8)); dates.add(new MonDay(6, 4)); dates.add(new MonDay(6, 7)); dates.add(new MonDay(9, 1)); dates.add(new MonDay(9, 5)); dates.add(new MonDay(12, 1)); dates.add(new MonDay(12, 2)); dates.add(new MonDay(12, 8)); System.out.println("张老师：小明知道月，小强知道日，现在你们能猜出来我的生日吗？就在这些里面："); System.out.println(dates); System.out.println("\n小明：如果小强不知道，那我也不知道。"); System.out.print("通过这句话可以知道：\n如果小强知道的话，一定在这些日期之中："); List dates1 = MonDayUtil.getInstance().getDatesWithDuplicateDays(dates); System.out.println(dates1); System.out.print("如果小强不知道的话，一定在这些日期之中："); List dates11 = MonDayUtil.getInstance().getDatesWithDistinctMon(dates); System.out.println(dates11); System.out.println("\n小强：刚才我不知道，现在我知道了。"); System.out.print("通过这句话可以知道：\n一定在这些日期之中："); List dates2 = MonDayUtil.getInstance().getDatesWithDistinctMon(dates1); System.out.println(dates2); System.out.println("\n小明：我也知道了。"); System.out.print("通过这句话知道：\n一定在这些日期之中："); List dates3 = MonDayUtil.getInstance().getDatesWithDistinctDay(dates2); System.out.println(dates3); System.out.println("-注意：\n如果只有一个，说明题目可解；\n如果多个日期，说明题目条件不全；\n如果没有日期，说明题目错误。）"); } } class MonDayUtil { private static MonDayUtil instance = new MonDayUtil(); public static MonDayUtil getInstance() { return instance; } public List getDatesWithDuplicateDays(List srcList) { List resultList = new ArrayList(); List monList = getMonNum(srcList); for (Integer m : monList) { List datesOfMon = getDatesOfMon(m, srcList); List daysOfDates = getDaysOfDates(datesOfMon); List otherDatesOfMon = getOtherDatesOfMon(m, srcList); List otherDaysOfDates = getDaysOfDates(otherDatesOfMon); if (otherDaysOfDates.containsAll(daysOfDates)) { resultList.addAll(datesOfMon); } } return resultList; } public List getDatesWithDistinctMon(List srcList) { List resultList = new ArrayList(); List dayList = getDayNum(srcList); for (Integer d : dayList) { List datesOfDay = getDatesOfDay(d, srcList); if (datesOfDay.size() == 1) { resultList.addAll(datesOfDay); } } return resultList; } public List getDatesWithDistinctDay(List srcList) { List resultList = new ArrayList(); List monList = getMonNum(srcList); for (Integer m : monList) { List datesOfMon = getDatesOfMon(m, srcList); if (datesOfMon.size() == 1) { resultList.addAll(datesOfMon); } } return resultList; } private List getDatesOfDay(int day, List srcList) { List resultList = new ArrayList(); for (MonDay md : srcList) { if (md.getDay() == day) { resultList.add(md); } } return resultList; } private List getDayNum(List srcList) { List resultList = new ArrayList(); for (MonDay md : srcList) { if (!resultList.contains(md.getDay())) { resultList.add(md.getDay()); } } return resultList; } private List getDaysOfDates(List srcList) { List resultList = new ArrayList(); for (MonDay md : srcList) { if (!resultList.contains(md.getDay())) { resultList.add(md.getDay()); } } return resultList; } private List getMonNum(List srcList) { List resultList = new ArrayList(); for (MonDay md : srcList) { if (!resultList.contains(md.getMon())) { resultList.add(md.getMon()); } } return resultList; } private List getDatesOfMon(int mon, List srcList) { List resultList = new ArrayList(); for (MonDay md : srcList) { if (md.getMon() == mon) { resultList.add(md); } } return resultList; } private List getOtherDatesOfMon(int mon, List srcList) { List resultList = new ArrayList(); for (MonDay md : srcList) { if (md.getMon() != mon) { resultList.add(md); } } return resultList; } } class MonDay { private int mon; private int day; public MonDay(int mon, int day) { this.mon = mon; this.day = day; } public int getMon() { return mon; } public int getDay() { return day; } public String toString() { return mon + "/" + day; } }（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构成的集合。 具体的逻辑过程，与逻辑分析一致，只是把数学语言，转化为计算机语言。 分享到：
Mac OS X Lion操作系统常用快捷键
|
实战Memcached缓存系统（8）Memcached异 ...
2012-01-15 15:50
浏览 259
评论(0)
查看更多
评论
发表评论
|
您还没有登录,请您登录后再发表评论 【本文地址】