资源描述：
《用电脑解决爱因斯坦难题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、用电脑解决爱因斯坦难题河南路明一、问题的提出爱因斯坦在20世纪初出的这个谜语，题目是这样的：1、在一条街上，有5座房子，喷了5种颜色。2、每个房里住着不同国籍的人。3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物。提示：1、英国人住红色房子2、瑞典人养狗3、丹麦人喝茶4、绿色房子在白色房子左面5、绿色房子主人喝咖啡6、抽PallMall香烟的人养鸟7、黄色房子主人抽Dunhill香烟8、住在中间房子的人喝牛奶9、挪威人住第一间房10、抽Blends香烟的人住在养猫的人隔壁11、养马的人住在抽Dunhill香烟的人隔
2、壁12、抽BlueMaster的人喝啤酒13、德国人抽Prince香烟14、挪威人住蓝色房子隔壁15、抽Blends香烟的人有一个喝水的邻居问题是：谁养鱼？据说，98%的人答不出这道题！二、分析这是一道很典型的逻辑推理题，对于此题使用表格方法，通过假设找出矛盾，从而得到正确答案，是比较快速的方法，但即使是这样我见到的最快解出此题的人也用了十几分钟，那么电脑需要多久呢？答案是不到一秒钟！如果让电脑完全按人类的推理来进行工作，那恐怕代码要写非常长，而且对于以后遇到类似的问题几乎没有什么参考价值。我们可以采用表格法进行递归穷举
3、，利用电脑的强大的计算能力加上一些不复杂的逻辑来实现它，但是对于5!的5次方超过248亿个可能性，计算量相当的惊人。而采用按“国籍”、“饮料”、“色彩”、“香烟”、“宠物”五项信息依次对表格进行可能性填充，一旦不符合逻辑条件则立即中止向后面的信息进行判断，这样就可大大减少运算次数。三、设计我们将使用二维数组InfoArray实现对各信息的初始化，二维数组矩阵Matrix记录表格定义，数组used来存贮与之对应的信息选项是否已用过。AccordWithLogic函数判断是否符合命题逻辑，可以对命题的条件先作一下整理再按信息
4、类别依次来判断，而且输入条件不能涉及到未填充的信息。例如：当前才填充到“饮料”信息就不能去判断涉及到“香烟”的第15个条件，因为还没有向表格中填充任何香烟，那么得出的判断结果是不正确的。FillMatrix函数是程序的主体，它以递归的方式列举了所有的排列可能性。PrintResult函数用于打印结果。整个代码是一个大循环，使用了backtracing的设计思想。四、Delphi代码实现unitUnit1;interfaceusesWindows,Messages,SysUtils,Variants,Classes,Gra
5、phics,Controls,Forms,Dialogs,StdCtrls;typeTForm1=class(TForm)Memo1:TMemo;Button4:TButton;Label1:TLabel;Label3:TLabel;procedureButton4Click(Sender:TObject);private{Privatedeclarations}public{Publicdeclarations}end;varForm1:TForm1;implementation{$R*.dfm}varMatrix:a
6、rray[0..4,0..4]ofsmallint;//表格MatrixRowCount:integer=4;//表格最大行数,即信息数MatrixColCount:integer=4;//表格最大列数,即每项信息的个数//实现对各信息的初始化InfoArray:array[0..4,0..4]ofstring=(('挪威人','英国人','瑞典人','丹麦人','德国人'),('茶','咖啡','牛奶','啤酒','水'),('红色','绿色','黄色','蓝色','白色'),('Prince','PallMall',
7、'Dunhill','Blends','BlueMaster'),('狗','鸟','马','猫','鱼'));used:array[0..4,0..4]ofinteger;//与InfoArray对应的元素是否已用过count_get,count_pro:integer;//结果的个数、共进行了多少次递归运算//取得信息号和项目序号所对应的值并和给定值进行对比functionCompareItem(InfoID,ItemIndex:Integer;CompareText:string):Boolean;beginif(
8、ItemIndex<=MatrixColCount)and(ItemIndex>=0)thenResult:=InfoArray[InfoID,Matrix[InfoID,ItemIndex]]=CompareTextelseResult:=False;end;//采用按'国籍'、'饮料'、'色彩'、'香烟'、'宠物
