《离散课后复习河北工业大学.doc》由会员分享，可在线阅读，更多相关《离散课后复习河北工业大学.doc（13页珍藏版）》请在三一文库上搜索。
1、实验一真值计算1、实验目的熟悉五个常用联结词合取、析取、条件和双条件的概念，掌握真值表技术。2、实验内容与要求定义1设P表示一个命题，由命题联结词和命题P连接成P，称r P为P的否定 式复合命题，P读“非P”。称I为否定联结词。P是真，当且仅当P为假；P是假， 当且仅当P为真。定义2 设P和Q为两个命题，由命题联结词八将P和Q连接成PAQ,称PAQ为命 题P和Q的合取式复合命题，PAQ读做“P与Q”，或“P且Q”。称八为合取联结词。当且 仅当P和Q的真值同为真，命题PAQ的真值才为真；否则，PAQ的真值为假。定义3 设P和Q为两个命题，由命题联结词V把P和Q连接成PVQ,称PVQ为命 题P和Q
2、的析取式复合命题，PVQ读做“P或Q”。称/为析取联结词。当且仅当P和Q的 真值同为假，PVQ的真值为假；否则，PVQ的真值为真。定义4 设P和Q为两个命题，由命题联结词一把P和Q连接成P-Q,称P-Q为命 题P和Q的条件式复合命题，简称条件命题。P-Q读做“P条件Q”或者“若P则Q”。称 为条件联结词。当P的真值为真而Q的真值为假时，命题P-Q的真值为假；否则，P-Q 的真值为真。定义5令P、Q是两个命题，由命题联结词把P和Q连接成PoQ，称PoQ为 命题P和Q的双条件式复合命题，简称双条件命题，PQ读做“P当且仅当Q”，或“P等 价Q。称村为双条件联结词。当P和Q的真值相同时，P-Q的真值
3、为真：否则，P0Q 的真值为假。本实验要求从键盘输入两个命题P和Q的真值，求它们的合取、析取、条件和双条件的真 值。用C语言或MATLAB实现。3. 实验步骤：在输入P、Q真值后，会依次输出合取、析取、条件、双条件的真值。本实验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择, 如1与T、0与F的置换等。但本实验在操作易于理解方面也有很人的体现。4. 源程序：(1) 方法一：# iiicludevoid main(void)printf(“输入 P、Q 的真值(1 为 T, 0 为 F)： n“);mt RQ;scanf(H%d&P);输入 P、Q 的值scanfC%cT；
4、&Q);/求真值pmuff合取：%dirP&Q);pmirff 析取：dntP|Q);pmitf(”条件：dS”,!P|Q);pmHff 双条件:%dirP&Q+!P& !Q);(2) 方法二：# iiicludeusing namespace std;mt mam()char PQint i;cout请输入两个命题的真值(T/T):endl;fbr(i=l;i=4;i-H-)cmP;cmQ;双条件为THendl; 双条件为F-endl; 双条件为F-endl; 双条件为T-endl;if Fileslicrosoft Visual StudioMyPro jectssdf ieDebugsd
5、f.p 件 、八0取取怡条输1合析条双pr0 10Q的真值1为T, 0为F：:0any key to continue（2）方法二:-nixca E：C与C+Microsot Visual Studi oMyProjectsoikoyDebugoikoy.exe实验二关系闭包计算1、实验目的熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法。2、实验内容与要求定义6设R是A上的二元关系，R的自反(对称、传递)闭包是关系R1,则 R1是自反的(对称的、传递的) RRl 对任何自反的(对称的、传递的)关系R2,若RcR2,则RlcR2oR的自反、对称和传递闭包分别记为r(R)
6、、s(R)和t(R)o定理1令RcAxA,则 r(R)=RUIA s(R)=RUR(3) t(R)=RUR2UR3.WarshaU算法：设R是n个元素集合上的二元关系，M是R的关系矩阵；(1) 置新矩阵A:=M(2) 置 i:=l；(3) forj=l to n doif Aj j=l then dofor k=l to n doAj,k:=A|j,k+Ai.k(4) i=i+I；(5) if i=n then to (3)else stop本实验要求从键盘输入一个关系的关系矩阵，计算其自反闭包、对称闭包和传递闭包, 计算传递闭包时使用Warshall算法。用C语言或MATLAB实现。3. 实
7、验步骤：输入一个3*3维矩阵 由i(R)=RUIA； s(R)=RUR-l； t(R)=RUR2UR3列出的算 法计算自反、对称、传递闭包并输出。本实验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择, 且每步均有注释，使程序更清晰。但本实验在操作易于理解方面也有很人的体现。4 源程序: 熟悉Waishall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法 令RAXA,则r(R)=R UIAs(R)=RUR-lt(R)=RUR2UR3 */# iiicludevoid main(void)int ijjk;mt I习习=1,0,0,0,1,0,0,0,1;mt a3 3
8、,b33,c33;pnntfCiW 输入 3x3 的二维矩阵： for(i=0;i3;i+)输入矩阵for(j=0j3j+)scanfC%d”，&aij);pnntf(-S 反闭包：nM); for(i=0;K3;i+)自反闭包for(j=0j3j+)printf(”3d,bij);prmtf(nnH);pmuff对称闭包：nM); for(i=0;i3;i+)对称闭包for(j=0j3j+) cij=aij|a|ji; priiitf(M%3d-,cij)；prmtf(nnH);pmirff传递闭包：nM);for(i=0;i3;i+)传递闭包for(j=0j3j+)if(aji=l)for
9、(k=0;k3;k+)for(i=0;i3;i+)传递闭包的输出for(j=0j3j+) pnntf(%3d”,aij);pnngn”)；5.实验结果：cT E：C与C+Microsot Visual StudioMyFrojectserdcxDebugerdcx.exe:1 03”/0 10闭；0闭 10 lffll01010 110 11 : 1 1 0 : 1111111ress any key to continue实验三计算两结点间长度为m的路的数目1、实验目的熟悉邻接矩阵和两结点间长度为m的路的数目的关系并编程计算。2、实验内容与要求定义7给定简单图G=, V=V, v2，vn,
10、V中的结点按下标由小到大编序，则n阶方阵A=(aJ称为图G的邻接矩阵。其中V.定理2设A为简单图G的邻接矩阵，则A中的1行j列元素3有等于G中联结 到的长度为m的链（或路）的数目。本实验要求从键盘输入图的邻接矩阵和一正整数m,计算结点两两之间长度为m的路 的数目。考虑有向图和无向图。用C语言或MATLAB实现。3. 实验步骤：本实验在编写源程序时，对实验要求进行了两种方式的阐释：一种是输入关系矩阵及其 阶数，然后依次列出路长度为1n的关系矩阵；另一种是输入关系矩阵及其阶数，然后指定 路长度的关系矩阵。本实验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择， 且每步均冇注释，
11、使程序更清晰。但本实验在操作易于理解方面也有很人的体现。4. 程序：(1)方法一：#mclude/计算两结点间长度为m的路的数目using namespace std;mt mam()mt i,j,k;int m,nJ；mta100100,b100100;mtc100100;int s;cout请输入关系矩阵阶数：Vendl;ciiim;n=m;cout请输入关系矩阵:endl;fbr(i=O;im;i+)for(j=OjmJ+)cmaij;cout7* * */Hendrfbr(i=O;im;i+)for(j=Ojm;j+)coutw长度为1的路的矩阵:yvendl;for(i=0;im;i
12、+)输出长度为1的路for(j=Ojm;j+)coutbijH H; coutendl;for(t=0;tn-l;t+)求长度为 2u 的路coutM长度为Ht+2n的路的矩阵:Hendl; for(i=0:im;i+)for(j=Ojmj+)s=0; fbi(k=0;km;k+) s+=aik*bk|j;cij=s；for(j=Ojmj 卄)bij=cij；for(i=0;im;i+)输出长度为2n的路for(j=Ojmj 卄)coutbijv” “； coutendl;return 0;运行结果:(2)方法二#mclude/计算两结点间长度为m的路的数目 using namespace s
13、td;mtmt i,j,k;int m,n,t;int a100100,b100100;mtc100100;int s;cout请输入关系矩阵阶数：endl; ciiim;cout请输入路的长度：endl;ciiin;cout请输入关系矩阵：endl; for(i=O;im;i+)for(j=Ojmj+) cmaij;for(i=O;im;i+) for(j=Ojm;j+) biUJ=aij;coutM长度为HnH的路的矩阵:Hendl;for(t=0;tn-l;t+)求长度为 n 的路for(i=0:im;i+)for(j=Ojmj+)s=0;fbr(k=O;km;k+)s+=aik*bk|
14、j;cij=s； for(i=0;im;i-H-) for(j=Ojmj+)bij=ci|j；for(i=0;im;i+)输出长度为n的路for(j=Ojm;j+)coutbij, ”; coutendl;return 0;5 运行结果：- X长度为2的路的矩阵：1 0 1 2 12 2 2Press any key to continueca E：C与C+Microsot Visual StudioMyFrojectsuhjDebuguhj.exe请输入关系矩阵阶数: 请输入路的长度： 备输入关系矩阵：0 101 0 1L 1 1实验四最优树的构造1、实验目的熟悉最优树的构造算法，掌握最优树
15、的构造过程。2、实验内容与要求定义8在权分别为wp w2，wt的加权二叉树T中，若权是的叶结点，其级/为L(w则 呱了)=工叱厶(叫)称为加权二叉树T的权，并记为w(T)。已知y, , z=iWf为权，T。为加权二叉树，其权为w(T0),如果对任意加权二叉树T,它的权是w(T),均有w(Tq)w(T),则称Tq是最优树或Huffiiian树。定理3设T为加权W,巧，wt且VWw2WWwt的最优树，贝lj(1) 加权W和w?的叶结点vwl和vw2是兄弟。(2) 以叶结点&和心2为儿子的分枝结点，它是所有分枝结点的级最高者。定理4设T为加权W,勺， wt且wlw2*Wt的最优树，若将以加权W 和的
16、叶结点为儿子的分枝结点改为加权W1+w2的叶结点而得到一棵新树T,则T是 最优树。根据上述两个定理，求一棵有t个权的最优树，可简化为求一棵有t-1个权的最优树， 而这又可简化为求一棵有t-2个权的最优树，依此类推。具体作法是：首先找出两个最小的 权值，设y和w?。然后对t-1个权W+W2，、与，wf求作一棵最优树，并且将这棵树 中的结W+V2代之以W w2,依此类推。本实验要求从键盘输入一组权值，构造出对应的最优树，列出构造过程。用C语言或 MATLAB 实现。3. 实验步骤：本实验要求先输入叶子节点的个数，然后输入其权值，最后根据冒泡法排序并使最小的 两数相加，最后输出最优树的构造过程。本实
17、验源程序力求简洁易懂，所以在设计时应用简单的语句并省去了许多繁杂的选择, 且每步均有注释，使程序更清晰。但本实验在操作易于理解方面也有很人的体现。4. 程序：#mclude/从键盘输入一组权值，构造出对应的最优树，列出构造过程using namespace std;mt mam()int i,j,k,temp,n;mt t=0;inta100;cout请输入叶子节点个数：“；ciiin;cout输入一组权值：endl;fbr(i=O;in;i-H-)cinai;coutendl;cout最优树构造过程：endl;for(i=0;in;i+)输出该数组coutaicoutendl;fbr(k=O
18、;kn;k+)for(i=0;in-l-t;i+)/冒泡法，共比较 n-l-t 轮for(j=OjaU+l)temp=aj; 若人数在前，则交换两数顺序aj=aj+l;aj+l=temp;aO=aO+al;将两个最小值相加并赋给a0for(i=l;in-t;i-H-) 从a2开始将所有数向前移一位 ai=ai+l;for(i=0;in-l -t;i+)/ 输出数组coutaiH ”；coutendl;t+；return 0; 5 运行结果:ca E：C与C+Microsot Visual StudioMyProjectssvjvcvDebugsvjvcv. exe请输入叶子节点个数：丄3输人一组权值：2 3 5 7 11 13 17 19 23 29 31 37 41最优树构造过程：2 3 5 7 11 13 17 19 23 29 31 37 415 5 7 11 13 17 19 23 29 31 37 4110 7 11 13 17 19 23 29 31 37 41171113171923293137 4124171719232931374134192324293137414224293134374153313437414265374142537842536595 65 78143 95238Press any key to continue戕狗拼音半=