离散作业_河北工业大学

1、实验一 真值计算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

2、”。称为析取联结词。当且仅当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 

3、1; Q的真值为真；否则，P « Q的真值为假。本实验要求从键盘输入两个命题P和Q的真值，求它们的合取、析取、条件和双条件的真值。用C语言或MATLAB实现。3. 实验步骤： 在输入P、Q真值后，会依次输出合取、析取、条件、双条件的真值。本实验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择，如1与T、0与F的置换等。但本实验在操作易于理解方面也有很大的体现。4.源程序：（1）方法一：#include<stdio.h>void main(void)printf("输入P、Q的真值(1为T，0为F)：n");int P,Q;scanf

4、("%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）方法二：#include<iostream>using namespace std;int main()char P,Q;int

5、i;cout<<"请输入两个命题的真值(T/F):"<<endl;for(i=1;i<=4;i+)cin>>P;cin>>Q;if(P='T'&&Q='T')cout<<"合取为T，析取为T，条件为T，双条件为T"<<endl;else if(P='T'&&Q='F')cout<<"合取为F，析取为T，条件为F，双条件为F"<<endl;e

6、lse if(P='F'&&Q='T')cout<<"合取为F，析取为T，条件为T，双条件为F"<<endl;else if(P='F'&&Q='F')cout<<"合取为F，析取为F，条件为T，双条件为T"<<endl;5.实验结果：（1）方法一：（2）方法二：实验二 关系闭包计算1、实验目的 熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法。2、实验内容与要求定义6 设R是A上的二元关

7、系，R的自反（对称、传递）闭包是关系R1，则 R1是自反的（对称的、传递的） RÍR1 对任何自反的（对称的、传递的）关系R2，若RÍR2，则R1ÍR2。R的自反、对称和传递闭包分别记为r(R)、s(R)和t(R)。定理1 令RÍA´A，则 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

8、,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列出的算法计算自反、对称、传递闭包并输出。 本实验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择

9、，且每步均有注释，使程序更清晰。但本实验在操作易于理解方面也有很大的体现。4.源程序：/*熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法令R AXA，则 r(R)=RIA s(R)=RR-1 t(R)=RR2R3*/#include<stdio.h>void 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;i<3;i+) /输入矩阵for(j=0;j<3;j+)scanf("%

10、d",&aij);printf("自反闭包：n");for(i=0;i<3;i+) /自反闭包for(j=0;j<3;j+)bij=aij|Iij;printf("%3d",bij);printf("n");printf("对称闭包：n");for(i=0;i<3;i+) /对称闭包for(j=0;j<3;j+)cij=aij|aji;printf("%3d",cij);printf("n");printf("传递闭包：n&

11、quot;);for(i=0;i<3;i+) /传递闭包for(j=0;j<3;j+)if(aji=1)for(k=0;k<3;k+)ajk=ajk|aik;for(i=0;i<3;i+) /传递闭包的输出for(j=0;j<3;j+)printf("%3d",aij);printf("n");5.实验结果：实验三 计算两结点间长度为m的路的数目1、实验目的 熟悉邻接矩阵和两结点间长度为m的路的数目的关系并编程计算。2、实验内容与要求定义7 给定简单图G=<V，E>，V=v1，v2，vn，V中的结点按下标由小到大

12、编序，则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的关系矩阵；另一种是输入关系矩阵及其阶数，然后指定路长度的关系矩阵。本实验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择，且每步均有注

13、释，使程序更清晰。但本实验在操作易于理解方面也有很大的体现。4.程序：（1）方法一：#include<iostream>/计算两结点间长度为m的路的数目using namespace std;int main()int i,j,k;int m,n,t;int a100100,b100100;int c100100;int s;cout<<"请输入关系矩阵阶数："<<endl;cin>>m;n=m;cout<<"请输入关系矩阵："<<endl;for(i=0;i<m;i+)for

14、(j=0;j<m;j+)cin>>aij;cout<<"/*/"<<endl;for(i=0;i<m;i+)for(j=0;j<m;j+)bij=aij;cout<<"长度为1的路的矩阵："<<endl;for(i=0;i<m;i+) /输出长度为1的路for(j=0;j<m;j+)cout<<bij<<" "cout<<endl;for(t=0;t<n-1;t+) /求长度为2n的路cout<&l

15、t;"长度为"<<t+2<<"的路的矩阵："<<endl;for(i=0;i<m;i+)for(j=0;j<m;j+)s=0;for(k=0;k<m;k+)s+=aik*bkj;cij=s;for(i=0;i<m;i+)for(j=0;j<m;j+)bij=cij;for(i=0;i<m;i+) /输出长度为2n的路for(j=0;j<m;j+)cout<<bij<<" "cout<<endl;return 0;运行结果：

16、（2）方法二#include<iostream>/计算两结点间长度为m的路的数目using namespace std;int main()int i,j,k;int m,n,t;int a100100,b100100;int c100100;int s;cout<<"请输入关系矩阵阶数："<<endl;cin>>m;cout<<"请输入路的长度："<<endl;cin>>n;cout<<"请输入关系矩阵："<<endl;for

17、(i=0;i<m;i+)for(j=0;j<m;j+)cin>>aij;cout<<"/*/"<<endl;for(i=0;i<m;i+)for(j=0;j<m;j+)bij=aij;cout<<"长度为"<<n<<"的路的矩阵："<<endl;for(t=0;t<n-1;t+) /求长度为n的路for(i=0;i<m;i+)for(j=0;j<m;j+)s=0;for(k=0;k<m;k+)s+=aik

18、*bkj;cij=s;for(i=0;i<m;i+)for(j=0;j<m;j+)bij=cij;for(i=0;i<m;i+) /输出长度为n的路for(j=0;j<m;j+)cout<<bij<<" "cout<<endl;return 0;5.运行结果：实验四 最优树的构造1、实验目的 熟悉最优树的构造算法，掌握最优树的构造过程。2、实验内容与要求定义8 在权分别为w1，w2，wt的加权二叉树T中，若权是wi的叶结点，其级为L(wi)，则 称为加权二叉树T的权，并记为w(T)。已知w1，w2，wt为权，T0为

19、加权二叉树，其权为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<iostream&g