爱因斯坦思考题设计报告书.docx
- 文档编号:12592870
- 上传时间:2023-06-06
- 格式:DOCX
- 页数:17
- 大小:114.04KB
爱因斯坦思考题设计报告书.docx
《爱因斯坦思考题设计报告书.docx》由会员分享,可在线阅读,更多相关《爱因斯坦思考题设计报告书.docx(17页珍藏版)》请在冰点文库上搜索。
爱因斯坦思考题设计报告书
计算机科学与技术学院
程序设计报告
专业:
计算机科学与技术
班级:
2011级03班
学号:
姓名:
2013年10月19日
程序设计报告书
一、前言
这是一个很有趣的逻辑推理题,传说是爱因斯坦提出来的,他宣称世界上只有2%的人能解出这个题目,传说不一定属实,但是这个推理题还是很有意思的。
二、题目
A题:
要求:
算法分析、类的设计、编程实现:
确定每个国家的人住什么颜色的房子,饮料,香烟,宠物。
图形界面(显示过程和结果)
a、在一条街上,有5座房子,喷了5种颜色。
b、每个房子里住着不同国籍的人。
c、每个人喝着不同的饮料,抽不同品牌的香烟,养不同的宠物。
1、英国人住红色房子。
2、瑞典人养狗。
3、丹麦人喝茶。
4、绿色房子在白色房子左面。
5、绿色房子主人喝咖啡。
6、抽PallMall香烟的人养鸟。
7、黄色房子主人抽Dunhill香烟。
8、住在中间房子的人喝牛奶。
9、挪威人住第一间房。
10、抽Blends香烟的人住在养猫的人隔壁。
11、养马的人住抽Dunhill香烟的人隔壁。
12、抽BlueMaster的人喝啤酒。
13、德国人抽Prince香烟。
14、挪威人住蓝色房子隔壁。
15、抽Blends香烟的人有一个喝水的邻居。
三、设计分析
这个题目的答案就包含在5个种类共25个元素的所有组合当中,当某一个组合能够满足以上15条线索时,就可以从中找到答案,以下就是一个满足全部线索的组合,可以看出本题的答案是住在绿色房子中的德国人养鱼作为宠物:
房子
国家
饮料
宠物
烟
黄色
挪威
水
猫
Dunhill
蓝色
丹麦
茶
马
Blends
红色
英国
牛奶
鸟
PallMall
绿色
德国
咖啡
鱼
Prince
白色
瑞士
啤酒
狗
BlueMaster
用计算机解决这个问题的本质就是枚举这5个种类25个元素的所有组合,应用15条线索对每个组合进行判断,能够满足全部线索的组合就是最终的结果。
和其它用穷举法算法一样,解决这个推理题也需要解决三个关键点:
定义能够描述这个问题的数据模型、基于这个数据模型的一套枚举算法和应用15条线索判断结果是否正确的方法。
考察这个问题的描述,需要枚举结果的元素分为5个类别,分别是房子(颜色)、国家、饮料类型、宠物种类和香烟的品牌。
根据题意,5个种类的元素不能重复,但是彼此存在联系,这个联系简单描述就是:
某个国家的人只能住在某个颜色的房子中,喝一种饮料,养一种宠物并抽一种品牌的香烟。
定义数据模型时可以采用“组”(group)的概念来定义这种关系,每个“组”包含5个种类的各一个元素,保证了对上述固定关系的约束。
每个元素都由两个属性,一个是类型,一个是值,比如“咖啡”,其类型是饮料,值是咖啡,可以这样对元素进行定义:
61 typedefstructtagItem
62 {
63 ITEM_TYPEtype;
64 intvalue;
65 }ITEM;
确定了元素的数据定义,“组”的数据定义就可以确定了:
107 typedefstructtagGroup
108 {
109 ITEMitems[GROUPS_ITEMS];
110 }GROUP;
这个GROUP的数据定义虽然清晰明了,但是对GROUP内的元素的定位不是很直观,比如对GROUP内的某个元素操作时需要遍历所有的元素逐个比较类型来定位元素,这就存在一个算法的效率问题。
既然GROUP内的item用数组进行组织,而数组的下标天生就具有位置关系,何不利用这一点简化数据定义呢?
首先对ITEM_TYPE的值进行一些约束,为每个类型赋一个明确的值,这个值就是item数据的位置,固定了值之后的ITEM_TYPE定义如下:
42 typedefenumtagItemType
43 {
44 type_house=0,
45 type_nation=1,
46 type_drink=2,
47 type_pet=3,
48 type_cigaret=4
49 }ITEM_TYPE;
对GROUP也重新定义:
107 typedefstructtagGroup
108 {
109 intitemValue[GROUPS_ITEMS];
110 }GROUP;
这样定义GROUP可以显著简化数据定位问题,比如“住在中间那个房子里的人喝牛奶”这个线索,就可以这样用代码实现:
groups[2].itemValue[type_drink]=DRINK_MILK;
接下来要处理15条线索的数学模型问题。
先分析一下这15条线索,大致可以分成三类:
第一类是描述某些元素之间具有固定绑定关系的线索,比如,“丹麦人喝茶”和“住绿房子的人喝咖啡”等等,线索1、2、3、5、6、7、12、13可归为此类;第二类是描述某些元素类型所在的“组”所具有的相邻关系的线索,比如,“养马的人和抽Dunhill牌香烟的人相邻”和“抽Blends牌香烟的人和养猫的人相邻”等等,线索10、11、14、15可归为此类;第三类就是不能描述元素之间固定关系或关系比较弱的线索,比如,“绿房子紧挨着白房子,在白房子的左边”和“住在中间那个房子里的人喝牛奶”等等。
对于第一类具有绑定关系的线索,其数学模型可以这样定义:
67 typedefstructtagBind
68 {
69 ITEM_TYPEfirst_type;
70 intfirst_val;
71 ITEM_TYPEsecond_type;
72 intsecond_val;
73 }BIND;
first_type和first_val是一个绑定关系中前一个元素的类型和值,second_type和second_val是绑定关系中后一个元素的类型和值。
以线索6“绿房子的主人喝咖啡”为例,first_type就是type_house,first_val就是COLOR_GREEN(COLOR_GREEN是个整数型常量),second_type就是type_drink,second_val就是DRINK_COFFEE(DRINK_COFFEE是个整数型常量)。
线索1、2、3、5、6、7、12、13就可以存储在binds数组中:
75 constBINDbinds[]=
76 {
77 {type_house,COLOR_RED,type_nation,NATION_ENGLAND},
78 {type_nation,NATION_SWEDEND,type_pet,PET_DOG},
79 {type_nation,NATION_DANMARK,type_drink,DRINK_TEA},
80 {type_house,COLOR_GREEN,type_drink,DRINK_COFFEE},
81 {type_cigaret,CIGARET_PALLMALL,type_pet,PET_BIRD},
82 {type_house,COLOR_YELLOW,type_cigaret,CIGARET_DUNHILL},
83 {type_cigaret,CIGARET_BLUEMASTER,type_drink,DRINK_BEER},
84 {type_nation,NATION_GERMANY,type_cigaret,CIGARET_PRINCE}
85 };
对于第二类描述元素所在的“组”具有相邻关系的线索,其数学模型可以这样定义:
89 typedefstructtagRelation
90 {
91 ITEM_TYPEtype;
92 intval;
93 ITEM_TYPErelation_type;
94 intrelation_val;
95 }RELATION;
type和val是某个“组”内的某个元素的类型和值,relation_type和relation_val是与该元素所在的“组”相邻的“组”中与之有关系的元素的类型和值。
以线索10“抽Blends牌香烟的人和养猫的人相邻”为例,type就是type_cigaret,val就是CIGARET_BLENDS(CIGARET_BLENDS是个整数型常量),relation_type是type_pet,relation_val是PET_CAT(PET_CAT是个整数型常量)。
线索10、11、14、15就可以存储在relations数组中:
097 constRELATIONrelations[]=
098 {
099 {type_cigaret,CIGARET_BLENDS,type_pet,PET_CAT},
100 {type_pet,PET_HORSE,type_cigaret,CIGARET_DUNHILL},
101 {type_nation,NATION_NORWAY,type_house,COLOR_BLUE},
102 {type_cigaret,CIGARET_BLENDS,type_drink,DRINK_WATER}
103 };
对于第三类线索,无法建立统一的数学模型,只能在枚举算法进行过程中直接使用它们过滤掉一些不符合条件的组合结果。
比如线索8“住在中间那个房子里的人喝牛奶”,就是对每个饮料类型组合结果直接判断groups[2].itemValue[type_drink]的值是否等于DRINK_MILK,如果不满足这个线索就不再继续下一个元素类型的枚举。
再比如线索4“绿房子紧挨着白房子,在白房子的左边”,就是在对房子类型进行组合排列时,将绿房子和白房子看成一个整体进行排列组合的枚举,得到的结果直接符合了线索4的要求。
解决了数据模型的定义,接下来就要考虑如何判定一个组合结果符合题目要求的全部线索。
这个判别是关键点,如果不能正确地从上亿个组合结果中识别出正确的结果,后面将要介绍的枚举算法就成了无的放失。
根据本文建立的数学模型,第三类线索直接在枚举算法部分应用,因此只需要对枚举得到的组合结果应用第一类线索和第二类线索进行过滤即可。
具有绑定关系的线索描述的是一个“组”内两种元素之间的固定关系,判断的方法就是遍历全部的“组”,找到BIND数据中的first_type和first_val标识的元素所在的组group,然后检查group组中类型为second_type的元素的值是否等于second_val,如果group中类型为second_type对应元素的值与second_val的值不一致就直接返回检查失败,否则就说明当前的组合结果满足此BIND数据对应的线索,然后对下一个BIND数据重复上述检查过程,直到检查完binds数组中所有线索对应的BIND数据。
图
(1)是具有绑定关系的线索检查流程图:
图
(1)具有绑定关系的线索检查流程图
“组”相邻关系的线索描述的是相邻的两个组之间元素的固定关系,判断的方法就是遍历全部的“组”,找到RELATION数据中的type和val标识的元素所在的组group,然后分别检查与group相邻的两个组(第一个组和最后一个组只有一个相邻的组)中类型为relation_type的元素对应的值是否等于relation_val,如果相邻的组中没有一个能满足RELATION数据就表示当前组合结果不满足线索,直接返回检查失败。
相邻的组中只要一个组中的元素满足RELATION数据描述的关系就表示当前组合结果符合RELATION数据对应的线索,需要对下一个RELATION数据重复上述检查过程,直到检查完relations数组中的全部线索对应的RELATION数据。
图
(2)是具有“组”相邻关系的线索检查流程图:
CheckGroupRelation()函数需要根据当前组group的位置进行适当的处理,如果当前组是第一个组或最后一个组,则group的相邻组只有一个,就是最靠近group的组,其它情况下group的相邻组都是两个。
CheckGroupRelation()函数的实现如下:
162 boolCheckGroupRelation(GROUP*groups,intgroupIdx,ITEM_TYPEtype,intvalue)
163 {
164 if(groupIdx==0)
165 {
166 if(GetGroupItemValue(&groups[groupIdx+1],type)!
=value)
167 {
168 returnfalse;
169 }
170 }
171 elseif(groupIdx==(GROUPS_COUNT-1))
172 {
173 if(GetGroupItemValue(&groups[groupIdx-1],type)!
=value)
174 {
175 returnfalse;
176 }
177 }
178 else
179 {
180 if((GetGroupItemValue(&groups[groupIdx-1],type)!
=value)
181 &&(GetGroupItemValue(&groups[groupIdx+1],type)!
=value))
182 {
183 returnfalse;
184 }
185 }
186
187 returntrue;
188 }
最后是枚举算法部分的说明。
前面系列文章中多次使用穷举法解决问题,但都是一维线性组合的枚举,本题则有些特殊,因为需要对不同类型的元素分别用穷举法进行枚举,因此不是简单的线性组合。
本文算法采用的枚举方法是对不同类型的元素分别用穷举法进行枚举,然后再进行组合,这个组合不是线性关系的组合,而是类似阶乘的几何关系的组合。
具体思路就是按照group中的元素顺序,首先对房子根据颜色组合进行穷举,每得到一组房子颜色组合后,就在此基础上对住在房子里的人的国籍进行穷举,在房子颜色和国籍的组合结果基础上,在对饮料类型进行穷举,依次类推,直到穷举完最后一种类型得到完整的穷举组合。
现在来具体推算一下穷举的过程,首先是对房子颜色进行穷举。
因为是5种颜色的不重复组合,因此应该有5!
=120个颜色组合结果,但是根据线索4“绿房子紧挨着白房子,在白房子的左边”,相当于绿房子和白房子有稳定的绑定关系,实际就只有4!
=24个颜色组合结果。
接下来对24个房子颜色组合结果中的每一个结果再进行住户国籍的穷举,理论上国籍也有5!
=120个结果,但是根据线索9“挪威人住在第一个房子里面”,相当于固定第一个房子住得人始终是挪威人,因此就只有4!
=24个国籍组合结果。
穷举完房子颜色和国籍后就已经有24x24=576个组合结果了,接下来需要对这576个组合结果中的每一个结果再进行饮料类型的穷举,理论上饮料类型也有5!
=120个结果,但是根据线索8“住在中间那个房子里的人喝牛奶”,相当于固定了一个饮料类型,因此也只有4!
=24个饮料组合类型。
穷举完饮料类型后就得到了576x24=13824个组合结果,接下来对13824个组合结果中的每一个结果再进行宠物种类的穷举,这一步没有线索可用,共有5!
=120个结果。
穷举完宠物种类后就得到了13824x120=1658880个组合结果,最后对1658880个组合结果中的每一个结果再进行香烟品牌的穷举,这一步依然没有线索可用,共有5!
=120个结果。
穷举完香烟品牌后就得到了全部组合共1658880x120=199065600个结果,剩下的事情就是对这将近2亿个结果进行判断。
以下就是对房子颜色进行穷举的算法实现:
369 /*遍历房子颜色*/
370 voidEnumHouseColors(GROUP*groups,intgroupIdx)
371 {
372 if(groupIdx==GROUPS_COUNT)/*递归终止条件*/
373 {
374 ArrangeHouseNations(groups);
375 return;
376 }
377
378 for(inti=COLOR_BLUE;i<=COLOR_YELLOW;i++)
379 {
380 if(!
IsGroupItemValueUsed(groups,groupIdx,type_house,i))
381 {
382 groups[groupIdx].itemValue[type_house]=i;
383 if(i==COLOR_GREEN)//应用线索(4):
绿房子紧挨着白房子,在白房子的左边;
384 {
385 groups[++groupIdx].itemValue[type_house]=COLOR_WHITE;
386 }
387
388 EnumHouseColors(groups,groupIdx+1);
393 }
394 }
395 }
EnumHouseColors()函数每得到一个房子颜色的穷举结果,就调用ArrangeHouseNations()函数进行进一步处理。
ArrangeHouseNations()函数做的事情就是继续枚举住在每个房子里的人的国籍,但是在这之前,先要根据已知条件进行预处理。
比如已知规则(9)的描述:
挪威人住在第一个房子里,就可以将group[0]的国籍锁定为NATION_NORWAY,从而减少一层遍历。
361 voidArrangeHouseNations(GROUP*groups)
362 {
363 /*应用规则(9):
挪威人住在第一个房子里面;*/
364 groups[0].itemValue[type_nation]=NATION_NORWAY;
365 EnumHouseNations(groups,1);/*从第二个房子开始*/
366 }
实际上,真正的遍历国籍过程是在EnumHouseNations()函数中完成。
EnumHouseNations()函数每得到一个完整的房子与国籍关系,就调用ArrangePeopleDrinks()函数进一步遍历每个人喝的饮料类型。
341 /*遍历国家*/
342 voidEnumHouseNations(GROUP*groups,intgroupIdx)
343 {
344 if(groupIdx==GROUPS_COUNT)/*递归终止条件*/
345 {
346 ArrangePeopleDrinks(groups);
347 return;
348 }
349
350 for(inti=NATION_NORWAY;i<=NATION_GERMANY;i++)
351 {
352 if(!
IsGroupItemValueUsed(groups,groupIdx,type_nation,i))
353 {
354 groups[groupIdx].itemValue[type_nation]=i;
355
356 EnumHouseNations(groups,groupIdx+1);
357 }
358 }
359 }
360
在每一组房子颜色和(住房客)国籍的对应关系上(根据前面的分析,将会有24x24=576组对应关系),ArrangePeopleDrinks()函数负责进一步排定它们和饮料类型的关系。
ArrangePeopleDrinks()函数直接调用EnumPeopleDrinks()函数进行饮料类型的枚举,规则(8):
“住在中间那个房子里的人和牛奶”直接体现在EnumPeopleDrinks()函数中:
313 voidEnumPeopleDrinks(GROUP*groups,intgroupIdx)
314 {
315 if(groupIdx==GROUPS_COUNT)/*递归终止条件*/
316 {
317 /*应用规则(8):
住在中间那个房子里的人喝牛奶;*/
318 if(groups[2].itemValue[type_drink]==DRINK_MILK)
319 {
320 ArrangePeoplePet(groups);
321 }
322 return;
323 }
324
325 for(inti=DRINK_TEA;i<=DRINK_MILK;i++)
326 {
327 if(!
IsGroupItemValueUsed(groups,groupIdx,type_drink,i))
328 {
329 groups[groupIdx].itemValue[type_drink]=i;
330 EnumPeopleDrinks(groups,groupIdx+1);
331 }
332 }
333 }
在确定完饮料类型后(根据前面的分析,将会得到576x24=13824组结果),就要进一步遍历每个人养的宠物(别忘了,鱼也算宠物)。
题目没有对宠物提供更多的线索,因此ArrangePeoplePet()函数就是简单的遍历全部宠物组合,得到120种人和宠物的组合:
288 voidEnumPeoplePats(GROUP*groups,intgroupIdx)
289 {
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 爱因斯坦 思考题 设计 报告书
![提示](https://static.bingdoc.com/images/bang_tan.gif)