资源描述
实验一 真值计算1、实验目的 熟悉五个常用联结词合取、析取、条件和双条件的概念，掌握真值表技术。2、实验内容与要求定义1设P表示一个命题，由命题联结词和命题P连接成P，称P为P的否定式复合命题， P读“非P”。称为否定联结词。P是真，当且仅当P为假；P是假，当且仅当P为真。定义2设P和Q为两个命题，由命题联结词将P和Q连接成PQ，称PQ为命题P和Q的合取式复合命题，PQ读做“P与Q”，或“P且Q”。称为合取联结词。当且仅当P和Q的真值同为真，命题PQ的真值才为真；否则，PQ的真值为假。定义3设P和Q为两个命题，由命题联结词把P和Q连接成PQ，称PQ为命题P和Q的析取式复合命题，PQ读做“P或Q”。称为析取联结词。当且仅当P和Q的真值同为假，PQ的真值为假；否则，PQ的真值为真。定义4设P和Q为两个命题，由命题联结词把P和Q连接成PQ，称PQ为命题P和Q的条件式复合命题，简称条件命题。PQ读做“P条件Q”或者“若P则Q”。称为条件联结词。当P的真值为真而Q的真值为假时，命题PQ的真值为假；否则，PQ的真值为真。定义5令P、Q是两个命题，由命题联结词把P和Q连接成P Q，称P Q为命题P和Q的双条件式复合命题，简称双条件命题，P Q读做“P当且仅当Q”，或“P等价Q”。称为双条件联结词。当P和Q的真值相同时，P Q的真值为真；否则，P Q的真值为假。本实验要求从键盘输入两个命题P和Q的真值，求它们的合取、析取、条件和双条件的真值。用C语言或MATLAB实现。3. 实验步骤： 在输入P、Q真值后，会依次输出合取、析取、条件、双条件的真值。本实验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择，如1与T、0与F的置换等。但本实验在操作易于理解方面也有很大的体现。4.源程序：（1）方法一：#includevoid main(void)printf(输入P、Q的真值(1为T，0为F)：n);int P,Q;scanf(%d,&P); /输入P、Q的值scanf(%d,&Q); /求真值printf(合取：%dn,P&Q);printf(析取：%dn,P|Q);printf(条件：%dn,!P|Q);printf(双条件：%dn,P&Q+!P&!Q);（2）方法二：#includeusing namespace std;int main()char P,Q;int i;cout请输入两个命题的真值(T/F):endl;for(i=1;iP;cinQ;if(P=T&Q=T)cout合取为T，析取为T，条件为T，双条件为Tendl;else if(P=T&Q=F)cout合取为F，析取为T，条件为F，双条件为Fendl;else if(P=F&Q=T)cout合取为F，析取为T，条件为T，双条件为Fendl;else if(P=F&Q=F)cout合取为F，析取为F，条件为T，双条件为Tendl;5.实验结果：（1）方法一：（2）方法二：实验二 关系闭包计算1、实验目的 熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法。2、实验内容与要求定义6 设R是A上的二元关系，R的自反（对称、传递）闭包是关系R1，则 R1是自反的（对称的、传递的） RR1 对任何自反的（对称的、传递的）关系R2，若RR2，则R1R2。R的自反、对称和传递闭包分别记为r(R)、s(R)和t(R)。定理1 令RAA，则 r(R)=RIA s(R)=RR-1 t(R)=RR2R3Warshall算法：设R是n个元素集合上的二元关系，M是R的关系矩阵；(1) 置新矩阵A:=M(2) 置i:=1；(3) for j=1 to n do if Aj,i=1 then do for k=1 to n do Aj,k:=Aj,k+Ai,k(4) i=i+1；(5) if i=n then to (3)(6) (7)(8)(9)(10)(11)(12)(13)(14)(15)(16)(17)(18)(19)(20)(21)(22)(23)(24)else stop本实验要求从键盘输入一个关系的关系矩阵，计算其自反闭包、对称闭包和传递闭包，计算传递闭包时使用Warshall算法。用C语言或MATLAB实现。3.实验步骤： 输入一个3*3维矩阵 由r(R)=RIA；s(R)=RR-1；t(R)=RR2R3列出的算法计算自反、对称、传递闭包并输出。 本实验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择，且每步均有注释，使程序更清晰。但本实验在操作易于理解方面也有很大的体现。4.源程序：/*熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法令R AXA，则 r(R)=RIA s(R)=RR-1 t(R)=RR2R3*/#includevoid main(void)int i,j,k;int I33=1,0,0,0,1,0,0,0,1;int a33,b33,c33;printf(请输入3x3的二维矩阵：n);for(i=0;i3;i+) /输入矩阵for(j=0;j3;j+)scanf(%d,&aij);printf(自反闭包：n);for(i=0;i3;i+) /自反闭包for(j=0;j3;j+)bij=aij|Iij;printf(%3d,bij);printf(n);printf(对称闭包：n);for(i=0;i3;i+) /对称闭包for(j=0;j3;j+)cij=aij|aji;printf(%3d,cij);printf(n);printf(传递闭包：n);for(i=0;i3;i+) /传递闭包for(j=0;j3;j+)if(aji=1)for(k=0;k3;k+)ajk=ajk|aik;for(i=0;i3;i+) /传递闭包的输出for(j=0;j3;j+)printf(%3d,aij);printf(n);5.实验结果：实验三 计算两结点间长度为m的路的数目1、实验目的 熟悉邻接矩阵和两结点间长度为m的路的数目的关系并编程计算。2、实验内容与要求定义7 给定简单图G=，V=v1，v2，vn，V中的结点按下标由小到大编序，则n阶方阵A=(aij)称为图G的邻接矩阵。其中 i，j=1，2，n。定理2 设A为简单图G的邻接矩阵，则Am中的i行j列元素amij等于G中联结vi到vj的长度为m的链(或路)的数目。本实验要求从键盘输入图的邻接矩阵和一正整数m，计算结点两两之间长度为m的路的数目。考虑有向图和无向图。用C语言或MATLAB实现。3.实验步骤： 本实验在编写源程序时，对实验要求进行了两种方式的阐释：一种是输入关系矩阵及其阶数，然后依次列出路长度为1n的关系矩阵；另一种是输入关系矩阵及其阶数，然后指定路长度的关系矩阵。本实验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择，且每步均有注释，使程序更清晰。但本实验在操作易于理解方面也有很大的体现。4.程序：（1）方法一：#include/计算两结点间长度为m的路的数目using namespace std;int main()int i,j,k;int m,n,t;int a100100,b100100;int c100100;int s;cout请输入关系矩阵阶数：m;n=m;cout请输入关系矩阵：endl;for(i=0;im;i+)for(j=0;jaij;cout/*/endl;for(i=0;im;i+)for(j=0;jm;j+)bij=aij;cout长度为1的路的矩阵：endl;for(i=0;im;i+) /输出长度为1的路for(j=0;jm;j+)coutbij ;coutendl;for(t=0;tn-1;t+) /求长度为2n的路cout长度为t+2的路的矩阵：endl;for(i=0;im;i+)for(j=0;jm;j+)s=0;for(k=0;km;k+)s+=aik*bkj;cij=s;for(i=0;im;i+)for(j=0;jm;j+)bij=cij;for(i=0;im;i+) /输出长度为2n的路for(j=0;jm;j+)coutbij ;coutendl;return 0;运行结果：（2）方法二#include/计算两结点间长度为m的路的数目using namespace std;int main()int i,j,k;int m,n,t;int a100100,b100100;int c100100;int s;cout请输入关系矩阵阶数：m;cout请输入路的长度：n;cout请输入关系矩阵：endl;for(i=0;im;i+)for(j=0;jaij;cout/*/endl;for(i=0;im;i+)for(j=0;jm;j+)bij=aij;cout长度为n的路的矩阵：endl;for(t=0;tn-1;t+) /求长度为n的路for(i=0;im;i+)for(j=0;jm;j+)s=0;for(k=0;km;k+)s+=aik*bkj;cij=s;for(i=0;im;i+)for(j=0;jm;j+)bij=cij;for(i=0;im;i+) /输出长度为n的路for(j=0;jm;j+)coutbij ;coutendl;return 0;5.运行结果：实验四 最优树的构造1、实验目的 熟悉最优树的构造算法，掌握最优树的构造过程。2、实验内容与要求定义8 在权分别为w1，w2，wt的加权二叉树T中，若权是wi的叶结点，其级为L(wi)，则 称为加权二叉树T的权，并记为w(T)。已知w1，w2，wt为权，T0为加权二叉树，其权为w(T0)，如果对任意加权二叉树T，它的权是w(T)，均有w(T0)w(T)，则称T0是最优树或Huffman树。定理3 设T为加权w1，w2，wt且w1w2wt的最优树，则(1) 加权w1和w2的叶结点vw1和vw2是兄弟。(2) 以叶结点vw1和vw2为儿子的分枝结点，它是所有分枝结点的级最高者。定理4 设T为加权w1，w2，wt且w1w2wt的最优树，若将以加权w1和w2的叶结点为儿子的分枝结点改为加权w1+w2的叶结点而得到一棵新树T1，则T1是最优树。根据上述两个定理，求一棵有t个权的最优树，可简化为求一棵有t-1个权的最优树，而这又可简化为求一棵有t-2个权的最优树，依此类推。具体作法是：首先找出两个最小的权值，设w1和w2。然后对t-1个权w1+w2，w3，wt求作一棵最优树，并且将这棵树中的结w1+w2代之以w1 w2，依此类推。本实验要求从键盘输入一组权值，构造出对应的最优树，列出构造过程。用C语言或MATLAB实现。3.实验步骤： 本实验要求先输入叶子节点的个数，然后输入其权值，最后根据冒泡法排序并使最小的两数相加，最后输出最优树的构造过程。本实验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择，且每步均有注释，使程序更清晰。但本实验在操作易于理解方面也有很大的体现。4.程序：#include/从键盘输入一组权值，构造出对应的最优树，列出构造过程using namespace std;int main()int i,j,k,temp,n;int t=0;int a100;coutn;cout输入一组权值：endl;for(i=0;iai;coutendl;cout最优树构造过程：endl;for(i=0;in;i+) /输出该数组coutai ;coutendl;for(k=0;kn;k+)for(i=0;in-1-t;i+) /冒泡法，共比较n-1-t轮for(j=0;jaj+1)temp=aj; /若大数在前，则交换两数顺序aj=aj+1;aj+1=temp;a0=a0+a1; /将两个最小值相加并赋给a0for(i=1;in-t;i+) /从a2开始将所有数向前移一位ai=ai+1;for(i=0;in-1-t;i+)/输出数组coutai ;coutendl;t+;return 0;5.运行结果：
展开阅读全文