标准实验报告模板.docx

电 子 科 技 大 学实 验 报 告学生姓名： 学 号： 指导教师：实验地点： 实验时间：一、实验室名称： 二、实验项目名称：三、实验学时：四、实验原理：数理逻辑是用数学的方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支、计算机学科、人工智能、语言学等学科均有十分密切的联系，并且日益显示出它的重要作用和更加广泛的应用前景。要很好地使用计算机，就必须学习逻辑。命题逻辑是谓词逻辑的基础，谓词逻辑是在命题逻辑的基础上，对命题进行进一步的细分，分解出命题中的主语、谓语等，以便能处理句子的内部结构之间的逻辑关系，而非仅仅是句子之间的逻辑关系。五、实验目的：本实验通过编写一些简单的prolog程序，让计算机来解答相应的逻辑问题，培养理论联系实际和自主学习的能力，提高程序设计水平。六、实验内容：使用prolog编写程序解决如下问题1）有五个房子，每个房子的颜色不同，里面分别住着不同国家的人，每个人都有自己养的不同的宠物，喜欢和不同的饮料，抽不同牌子的烟。现在已知以下的一些信息：英国人（englishman）住在红色（red）的房子里。 西班牙人（spaniard）养了一条狗（dog）。 挪威人（norwegian）住在左边的第一个房子里。 黄房子（yellow）里的人喜欢抽kools牌的香烟。 抽chesterfields牌香烟的人与养狐狸（fox）的人是邻居。 挪威人（norwegian）住在蓝色（blue）的房子旁边。 抽winston牌香烟的人养了一只蜗牛（Snails）。 抽Lucky Strike牌香烟的人喜欢喝桔子汁（orange juice）。 乌克兰人（ukrainian）喜欢喝茶（tea）。 日本人（japanese）抽parliaments牌的烟。 抽kools牌的香烟的人与养马（horse）的人是邻居。 喜欢喝咖啡（coffee）的人住在绿（green）房子里。 绿（green）房子在象牙白（ivory）房子的右边（图中的右边）。 中间那个房子里的人喜欢喝牛奶（milk）。 根据以上条件，你能告诉我哪个房子里的人养斑马（zebra），哪个房子里的人喜欢喝水（water）吗？或者你能把所有的东西都对号入座吗？2） 糊涂先生给他的五个朋友写信，他写了五封信，但是当他的朋友收到信后，都告诉他：“你的信寄错了”。那么请你计算一下：出现这种情况的概率有多少？（假设糊涂先生是随机地往信封里装信的），你能不能把所有的情况都列出来呢？3） 把三个1，三个2，三个9排成一组数列，使得对于所有的数i, i属于1,9, 正好有i个数字位于其中。例如1, 9, 1, 2, 1, 8, 2, 4, 6, 2, 7, 9, 4, 5, 8, 6, 3, 4, 7, 5, 3, 9, 6, 8, 3, 5, 7.两个1中间都有一个数字，每两个2中间都有两个数字。求出满足条件的所有排列。4）设计完成图的广度优先搜索算法。七、实验器材（设备、元器件）：PC机一台，装有C/C+/JAVA语言集成开发环境。八、实验步骤：1） 每个房子有不同的颜色，所以就颜色来说就有5！种情况，而一共有五个特征：颜色、国籍、宠物、香烟和饮料。所以一共就有5!*5种情况，即600种。不是很多，完全可以使用程序穷举出来。在此程序中使用结构h(C,N,P,Y,D)来储存房间的信息。C,N,P,Y,D分别对应颜色、国籍、宠物、香烟和饮料。由于有五个房间，所以使用列表来储存所有房间的信息。此列表为：h(C1,N1,P1,Y1,D1),h(C2,N2,P2,Y2,D2),h(C3,N3,P3,Y3,D3),h(C4,N4,P4,Y4,D4),h(C5,N5,P5,Y5,D5)一开始所有房间的情况都是未知的，所以就使用变量来代表每个房间的情况。在后面的条件中经常要读取房间的某个信息，所以下面就先编写五个谓词来完成这项工作。color(h(C,N,P,Y,D),C).nation(h(C,N,P,Y,D),N).pet(h(C,N,P,Y,D),P).yan(h(C,N,P,Y,D),Y).drink(h(C,N,P,Y,D),D).条件中还用到了房间之间的相对位置的信息，下面的谓词就是完成这个任务的。next(A,B,A,B,C,D,E).next(B,C,A,B,C,D,E).next(C,D,A,B,C,D,E).next(D,E,A,B,C,D,E).next(B,A,A,B,C,D,E).next(C,B,A,B,C,D,E).next(D,C,A,B,C,D,E).next(E,D,A,B,C,D,E).用语言来描述就是：首先Z5是个房子，对应于member(Z5,X)；然后它的宠物是fox，对应于pet(Z5,fox)；它的邻居是Z6，对应于next(Z6,Z5,X)；最后Z6的人抽chesterfields，对应于yan(Z6,chesterfields)。因此只要把原始的条件稍加分解，就变成了我们的Prolog程序。2）我们先来分析一下问题。往五个不同的信封里装五封不同的信，一共有5！=120种装法，这实际上是5封信的全排列。由于所有的信都装错了，所以一号信不在一号信封里，二号信不在二号信封里，.，如果用列表1,2,3,4,5表示所有的信都装对了的情况（1在第一位，2在第二位,.）。那么5,4,3,2,1就是一种装错了的情况。 先回顾一下全排列的程序：% delete(A,B,C), B为列表，A为B中的某个元素，C为把B中的元素A除去后的列表。delete(A,A|X,X).delete(A,B|X,B|Y) :- delete(A,X,Y).% permutation(A,B), 列表A为列表B的全排列之一时，成功。permutation(,).permutation(A|X,Y) :- delete(A,Y,Y1), permutation(X,Y1).我们使用谓词permutation/2可以生成所有的排列情况，所以下面的任务就是编写校验部分。先来看some_element_right/2谓词：% some_element_right(A,B) 如果列表A与B中存在位置相同的元素则成功。some_element_right(A|X,A|Y).some_element_right(A|X,B|Y):-some_element_right(X,Y).它的原理很简单，我们来看看它的功能：?- some_element_right(3,2,1,1,2,3).yes?- some_element_right(3,2,1,2,1,3).no第一个询问失成功，因为元素2在两个列表中的位置相同；第二个询问失败，因为找不到位置相同的元素。最后我们来编写主程序：letter(X,Y):- permutation(X,Y), not(some_element_right(X,Y).not/1谓词表示否定，所以上面的第二各自目标的意思就是：列表X与Y没有位置相同的元素。3）这个题目初看起来比较困难，因为如果把这27个数字全排列，然后再来判断排列的合法性，是很费时间的。和8皇后问题一样，这个问题也可以使用回溯法，并且把产程和测试的过程交织在一起，一级一级地过滤，题目中对于每个数字i，其实都是一个约束条件，这样一共就有九个条件：每两个1中间都有一个数字，每两个2中间都有两个数字.用prolog可以很直观地表达这9个条件：% sequence(Xs) :- Xs is a list of 27sequence(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_).% question(Ss) :- Ss is a solution toquestion(Ss):-sequence(Ss),sublist1(9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9, Ss),sublist1(8,_,_,_,_,_,_,_,_,8,_,_,_,_,_,_,_,_,8, Ss),sublist1(7,_,_,_,_,_,_,_,7,_,_,_,_,_,_,_,7, Ss),sublist1(6,_,_,_,_,_,_,6,_,_,_,_,_,_,6, Ss),sublist1(5,_,_,_,_,_,5,_,_,_,_,_,5, Ss),sublist1(4,_,_,_,_,4,_,_,_,_,4, Ss),sublist1(3,_,_,_,3,_,_,_,3, Ss),sublist1(2,_,_,2,_,_,2, Ss),sublist1(1,_,1,_,1, Ss).这里用谓词scquence/1来产生一个长度为27的未知列表，这个列表中的元素都是不确定的，因此都是用变量表示(当然也可编写程序来产生任意长度的变量列表)。剩下的谓词question/1一目了然，它调用了谓词sublist1/2。这个谓词可以判断或者产生一个列表的子列表。%sublist1(As,Bs). is ture if As is a sublist of Bs.sublist1(,).sublist1(,_|_).sublist1(X,_|Y):-sublist1(X,Y).sublist1(A|X,A|Y):-headlist(X,Y).headlist(,).headlist(,_|_).headlist(A|X,A|Y):-headlist(X,Y).注意子列表和子集是有区别的，集合中的元素没有顺序，而列表中的元素是有顺序的，所谓子列表就是从原列表中任意截取出的一段列表。因此在程序sublist1中，一旦发现As和Bs有相同的头元素的话，就调用headlist/2来判断剩下的部分的头是否都元素相同，直到子列表为空。由于prolog谓词的多态性，这个sublist1/2不仅能用来判断子列表，也能用来产生子列表：?- sublist1(X,1,2,3,4),write(X),nl,fail.此处略去空列表433, 422, 32, 3, 411, 21, 2, 31, 2, 3, 4sublist1/2在question/1中的作用就更加具有prolog的特点了，它并不是完全意义上的产生子列表，也不是完全地判断，而是二者兼而有之。例如头一句：sublist1(9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9, Ss),由于我们已经给出了子列表的模式，那么通过这个子句之后的Ss就包含9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9这样的子列表了。?- sequence(Ss),sublist1(9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9, Ss),write(Ss),nl,fail._G440, _G443, _G446, _G449, _G452, _G455, 9, _G165, _G168, _G171, _G174, _G177, _G180, _G183, _G186, _G189, 9, _G195, _G198, _G201, _G204, _G207, _G210, _G213, _G216, _G219, 9_G440, _G443, _G446, _G449, _G452, 9, _G165, _G168, _G171, _G174, _G177, _G180, _G183, _G186, _G189, 9, _G195, _G198, _G201, _G204, _G207, _G210, _G213, _G216, _G219, 9, _G518_G440, _G443, _G446, _G449, 9, _G165, _G168, _G171, _G174, _G177, _G180, _G183, _G186, _G189, 9, _G195, _G198, _G201, _G204, _G207, _G210, _G213, _G216, _G219, 9, _G515, _G518_G440, _G443, _G446, 9, _G165, _G168, _G171, _G174, _G177, _G180, _G183, _G186, _G189, 9, _G195, _G198, _G201, _G204, _G207, _G210, _G213, _G216, _G219, 9, _G512, _G515, _G518_G440, _G443, 9, _G165, _G168, _G171, _G174, _G177, _G180, _G183, _G186, _G189, 9, _G195, _G198, _G201, _G204, _G207, _G210, _G213, _G216, _G219, 9, _G509, _G512, _G515, _G518_G440, 9, _G165, _G168, _G171, _G174, _G177, _G180, _G183, _G186, _G189, 9, _G195, _G198, _G201, _G204, _G207, _G210, _G213, _G216, _G219, 9, _G506, _G509, _G512, _G515, _G5189, _G165, _G168, _G171, _G174, _G177, _G180, _G183, _G186, _G189, 9, _G195, _G198, _G201, _G204, _G207, _G210, _G213, _G216, _G219, 9, _G503, _G506, _G509, _G512, _G515, _G518 如此类推，经过一层一层地过滤，最终得到的就是满足所有条件的序列了。注意这里要把长的列表放在前面测试，以尽快过滤掉大多数的错误的解。因为对于拥有子列表i,.,i,.,i的Ss的个数来说，是随着i的增大而减少的，通过简单的计算可以得出Ss的个数为25-2*i，也就是说i=9的时候有7中可能，而i=1的时候有23种，如果我们先对9进行处理的话，候选答案一下子就减小为7个了。这也是产生并测试中常用的技术：能够剔除更多错误解的条件应该最先拿来判断。程序很短，但是体现出来prolog回溯和模式匹配方面的强大功能。4）广度搜索的Prolog程序较简单：%append(L1,L2,L3). 当列表L3是L1与L2连接而成时，append/3谓词成功。append(, X, X).append(A|X, Y, A|Z) :- append(X,Y,Z).sub(a,b).sub(a,c).sub(a,d).sub(b,e).sub(c,f).sub(c,g).sub(d,i).sub(d,h).route(,X,X).route(Links,Current,Des):-route(PreLinks,Current,Next),sub(Next,Des),append(PreLinks,Next,Links).?- route(L,a,f).L = c,fappend/3谓词的作用是把两个表合成为一个表。上面的route/3使用广度搜索来找出答案。九、实验数据及结果分析：1）的运行结果：?- solve(X,TT,TTT).X = h(yellow,norwegian,fox,kools,water),h(blue,ukrainian,horse,chesterfields,tea),h(red,englishman,snails,winston,milk),h(iory,spaniard,dog,Lucky Strike,orange juice),h(green,japanese,zebra,parliaments,coffee)TT = h(green,japanese,zebra,parliaments,coffee)TTT = h(yellow,norwegian,fox,kools,water) ;X = h(yellow,norwegian,fox,kools,water),h(blue,ukrainian,horse,chesterfields,tea),h(red,englishman,snails,winston,milk),h(green,japanese,zebra,parliaments,coffee),h(ivory,spaniard,dog,Lucky Strike,orange juice)TT = h(green,japanese,zebra,parliaments,coffee)TTT = h(yellow,norwegian,fox,kools,water) no2）的运行结果?- letter(X,1,2,3,4,5),write(X),nl,fail.2,1,4,5,32,1,5,3,42,3,1,5,42,3,4,5,12,3,5,1,42,4,1,5,32,4,5,1,32,4,5,3,12,5,1,3,42,5,4,1,32,5,4,3,13,1,2,5,43,1,4,5,23,1,5,2,43,4,1,5,23,4,2,5,13,4,5,1,23,4,5,2,13,5,1,2,43,5,2,1,43,5,4,1,23,5,4,2,14,1,2,5,34,1,5,2,34,1,5,3,24,3,1,5,24,3,2,5,14,3,5,1,24,3,5,2,14,5,1,2,34,5,1,3,24,5,2,1,34,5,2,3,15,1,2,3,45,1,4