《(完整版)离散数学实验指导书及其答案.pdf》由会员分享，可在线阅读，更多相关《(完整版)离散数学实验指导书及其答案.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验一 命题逻辑公式化简【实验目的】加深对五个基本联结词（否定、合取、析取、条件、双条件）的理解、掌握利用基本等价公式化简公式的方法。【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。实验用例：用化简命题逻辑公式的方法设计一个 5 人表决开关电路，要求 3 人以上（含3 人）同意则表决通过（表决开关亮）。【实验原理和方法】（1）写出 5 人表决开关电路真值表，从真值表得出 5 人表决开关电路的主合取公式（或主析取公式），将公式化简成尽可能含五个基本联结词最少的等价公式。（2）上面公式中的每一个联结词是一个开关元件，将它们定义成 C 语言中的函数。（3）输入 5 人表决值（0 或 1），
2、调用上面定义的函数，将 5 人表决开关电路真值表的等价公式写成一个函数表达式。（4）输出函数表达式的结果，如果是 1，则表明表决通过，否则表决不通过。参考代码：#include int vote(int a,int b,int c,int d,int e)/五人中任取三人的不同的取法有 10 种。if(a&b&c|a&b&d|a&b&e|a&c&d|a&c&e|a&d&e|b&c&d|b&c&e|b&d&e|c&d&e)return 1;else return 0;void main()int a,b,c,d,e;printf(请输入第五个人的表决值（0 或 1，空格分开）：);scanf(%
3、d%d%d%d%d,&a,&b,&c,&d,&e);if(vote(a,b,c,d,e)printf(很好，表决通过！n);else printf(遗憾，表决没有通过！n);/注：联结词不定义成函数，否则太繁 实验二 命题逻辑推理【实验目的】加深对命题逻辑推理方法的理解。【实验内容】用命题逻辑推理的方法解决逻辑推理问题。实验用例：根据下面的命题，试用逻辑推理方法确定谁是作案者，写出推理过程。（1）营业员 A 或 B 偷了手表；（2）若 A 作案，则作案不在营业时间；（3）若 B 提供的证据正确，则货柜末上锁；（4）若 B 提供的证据不正确，则作案发生在营业时间；（5）货柜上了锁。【实验原理和方
4、法】（1）符号化上面的命题，将它们作为条件，营业员 A 偷了手表作为结论，得一个复合命题。（2）将复合命题中要用到的联结词定义成 C 语言中的函数，用变量表示相应的命题变元。将复合命题写成一个函数表达式。（3）函数表达式中的变量赋初值 1。如果函数表达式的值为 1，则结论有效，A 偷了手表，否则是 B 偷了手表。用命题题变元表示：A:营业员 A 偷了手表 B:营业员 B 偷了手表 C:作案不在营业时间 D:B 提供的证据正确 E:货柜末上锁 则上面的命题符号化为(A|B)&(!A|C)&(!D|E)&(D|!C)&!E 要求找到满足上面式子的变元 A，B 的指派便是结果。C 语言算法：int
5、A,B,C,D,E;for(A=0;A=1;A+)for(B=0;B=1;B+)for(C=0;C=1;C+)for(D=0;D=1;D+)for(E=0;E=1;E+)if(A|B)&(!A|C)&(!D|E)&(D|!C)&!E)printf(A=%d,B=%dn,A,B);/*实验结果是：A=0，B=1，即 B 偷了手表*/实验三 集合运算【实验目的】掌握用计算机求集合的交、并、差和补运算的方法。【实验内容】编程实现集合的交、并、差和补运算。【实验原理和方法】（1）用数组 A，B，C，E 表示集合。输入数组 A，B，E（全集），输入数据时要求检查数据是否重复（集合中的数据要求不重复），要
6、求集合 A，B 是集合 E 的子集。以下每一个运算都要求先将集合 C 置成空集。（2）二个集合的交运算：把数组 A 中元素逐一与数组 B 中的元素进行比较，将相同的元素放在数组 C 中，数组 C 便是集合 A 和集合 B 的交。C 语言算法：for(i=0;im;i+)for(j=0;jn;j+)if(ai=bj)ck+=ai;（3）二个集合的并运算：把数组 A 中各个元素先保存在数组 C 中。将数组 B 中的元素逐一与数组 B 中的元素进行比较，把不相同的元素添加到数组 C 中，数组 C 便是集合 A 和集合 B 的并。C 语言算法：for(i=0;im;i+)ci=ai;for(i=0;i
7、n;i+)for(j=0;jm;j+)if(bi=cj)break;if(j=m)cm+k=bi;k+;（4）二个集合的差运算：把数组 A 中各个元素先保存在数组 C 中。将数组 B 中的元素逐一与数组 B 中的元素进行比较，把相同的元素从数组 C 中删除，数组 C 便是集合 A 和集合B 的差 A-B。C 语言算法：for(i=0;im;i+)ci=ai;for(i=0;in;i+)for(j=0;jm;j+)if(bi=cj)for(k=j;km;k+)ck=ck+1;/*移位*/m-;break;（5）集合的补运算：将数组 E 中的元素逐一与数组 A 中的元素进行比较，把不相同的元素保存
8、到数组 C 中，数组 C 便是集合 A 关于集合 E 的补集。求补集是一种种特殊的集合差运算。实验四 二元关系及其性质 【实验目的】掌握二元关系在计算机上的表示方法，并掌握如果判定关系的性质。【实验内容】编程判断一个二元关系是否为等价关系，如果是，求其商集。等价关系：集合 A 上的二元关系 R 同时具有自反性、对称性和传递性，则称 R 是 A 上的等价关系。【实验原理和方法】（1）A 上的二元关系用一个 nn 关系矩阵 R=nnijr)(表示，定义一个 nn 数组 rnn表示 nn 矩阵关系。（2）若 R 对角线上的元素都是 1，则 R 具有自反性。C 语言算法：int i,flag=1;fo
9、r(i=0;iN&flag;i+)if(rii!=1)flag=0;如果 flag=1，则 R 是自反关系（3）若 R 是对称矩阵，则 R 具有对称性。对称矩阵的判断方法是：RrRrjiij有,。C 语言算法：int i,j,flag=1;for(i=0;iN&flag;i+)for(j=i+1;jN&flag;j+)if(rij&rji!=1)flag=0;如果 flag=1，则 R 是对称关系（4）关系的传递性判断方法：对任意 i，j，k，若111ikjkijrrr有且。C 语言算法：int i,j,k,flag=1;for(i=0;iN&flag;i+)for(j=0;jN&flag;j
10、+)for(k=0;kN&flag;k+)if(rij&rjk&rik!=1)flag=0;如果 flag=1，则 R 是传递关系（5）求商集的方法：商集是由等价类组成的集合。已知 R 是等价关系，下面的算法是把等价类分行打印出来。C 语言算法：int i,j,flag=1;int aN;for(i=0;iN;i+)ai=i+1;/*i 代表第 i 个元素*/for(i=0;iN;i+)if(ai)printf();for(j=0;jN;j+)if(rij&aj!=0)printf(%d,aj);/*打印和第 i 个元素有关系的所有元素*/aj=0;printf(n);实验五 关系闭包运算 【
11、实验目的】掌握求关系闭包的方法。【实验内容】编程求一个关系的闭包，要求传递闭包用 warshall 方法。【实验原理和方法】设 N 元关元系用 rNN表示，cNN表示各个闭包，函数 initc(r)表示将 cNN初始化为 rNN。（1）自反闭包：AIRRr)(。C 语言算法：将关系矩阵的对角线上所有元素设为 1。initc(r);/*将关系矩阵的对角线上所有元素设为 1*/for(i=0;iN;i+)cii=1;（2）对称闭包：RRRs)(C 语言算法：在关系矩阵的基础上，若1,1jiijrr令。initc(r);for(i=0;iN;i+)for(j=0;jN;j+)if(cij)cji=1
12、;/*将关系矩阵的对角线上所有元素设为 1*/（3）传递闭包：nRRRRt2)(，或用 warshall 方法。方法 1：nRRRRt2)(，下面求得的关系矩阵 T=nnijb)(就是)(Rt。int bNN;initc(r);/*用 c 装好 r*/for(m=1;mN;m+)/*得 r 的 m 次方,用 c 装好*/for(i=0;iN;i+)for(j=0;jN;j+)bij=0;for(k=0;kN;k+)bij+=cik*rkj;if(bij)bij=1;initc(b);/*把 r 的 m 次方 b 赋给 c 保存*/方法 2：warshall 方法 initc(r);/*用 c
13、装好 r*/for(i=0;iN;i+)for(j=0;jN;j+)if(cji)for(k=0;kN;k+)cjk=cjk+cik;if(cjk)cjk=1;实验六 欧拉图判定和应用 【实验目的】掌握判断欧拉图的方法。【实验内容】判断一个图是不是，如果是，求出所有欧拉路【实验原理和方法】（1）用关系矩阵 R=nnijr)(表示图。（2）对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。C 语言算法：flag=1;for(i=1;i=n&flag;i+)sum=0;for(j=1;j=n;j+)if(rij)sum+;if(sum%2=0)flag=0;如果 flag 该无向图是欧拉图（3
14、）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。C 语言算法：flag=1;for(i=1;i=n&flag;i+)sum1=0;sum2=0;for(j=1;j=n;j+)if(rij)sum1+;for(j=1;j=n;j+)if(rji)sum2+;if(sum1%2=0|sum2%2=0)flag=0;如果 flag 该有向图是欧拉图（4）求出欧拉路的方法：欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有欧拉路。C 语言算法：int count=0,cur=0,rNN;/rNN为图的邻接矩阵，cur 为当前结点编号，count为欧拉路的数量。int sequenceM;/
15、sequence 保留访问点的序列，M 为图的边数 输入图信息;void try1(int k)/k 表示边的序号 int i,pre=cur;/j 保留前一个点的位置,pre 为前一结点的编号 for(i=0;iN;i+)if(rcuri)/当前第 cur 点到第 i 点连通 /删除当前点与第 i 点的边，记下第 k 次到达点 i，把第 i 个点设为当前点 rcuri=0;cur=sequencek=i;if(kM)try1(k+1);/试下一个点 else prt1();/经过了所有边，打印一个解/上面条件不满足，说明当前点的出度为 0，回溯，试下一位置 rprei=1;cur=pre;实
16、验七 最优二叉树的应用 【实验目的】掌握求最优二叉树的方法。【实验内容】最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率，求各通信符号对应的前缀码。【实验原理和方法】（1）用一维数组 fN存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。（2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。#include#include#define N 13 struct tree float num;struct tree*Lnode;struct tree*Rnode;*fpN;/保存结点 char s2*N;/放前缀码 void inite_node(float
17、f,int n)/生成叶子结点 int i;struct tree*pt;for(i=0;inum=fi;pt-Lnode=NULL;pt-Rnode=NULL;fpi=pt;void sort(struct tree*array,int n)/将第 N-n 个点插入到已排好序的序列中。int i;struct tree*temp;for(i=N-n;inumarrayi+1-num)temp=arrayi+1;arrayi+1=arrayi;arrayi=temp;struct tree*construct_tree(float f,int n)/建立树 int i;struct tree*
18、pt;for(i=1;inum=fpi-1-num+fpi-num;pt-Lnode=fpi-1;pt-Rnode=fpi;fpi=pt;/w1+w2 sort(fp,N-i);return fpN-1;void preorder(struct tree*p,int k,char c)int j;if(p!=NULL)if(c=l)sk=0;else sk=1;if(p-Lnode=NULL)/P 指向叶子 printf(%.2f:,p-num);for(j=0;jLnode,k+1,l);preorder(p-Rnode,k+1,r);void main()float fN=2,3,5,7,
19、11,13,17,19,23,29,31,37,41;struct tree*head;inite_node(f,N);/初始化结点 head=construct_tree(f,N);/生成最优树 s0=0;preorder(head,0,l);/遍历树 实验八 群的判定【实验目的】掌握群的判定方法。【实验内容】输入代数系统(A,*)的集合 A 和*运算的运算表，判断(A，*)是否是群。【实验原理和方法】（1）用一维数组 an存贮集合 A。（2）用二维数组 opnn存贮运算表。（3）根据群的定义，代数系统(A，*)若为群，除运算表已表明运算*封闭外，还应该满足下列三个条件：*运算可结合、有幺元
20、 e、A 中任何元素都有逆元。*运算可结合：for(i=0;iN;i+)for(j=0;jN;j+)for(k=0;kN;k+)for(l=0;lN;l+)if(opij=al)x=l;/*opij 代表 a*b*/if(opjk=al)y=l;/*opjk 代表 b*c*/if(opiy!=opxk)/*opiy代表 a*(b*c)*/printf(%d*%d)*%d=%d,%d*(%d*%d)=%d,运算是不可结合！n,ai,aj,ak,opxk,ai,aj,ak,opiy);flag=0;/*不满足结合性*/if(flag)printf(运算是可结合！n);有幺元 e:flag=0;for(i=0;iN;i+)for(j=0;jN;j+)if(opij!=aj|opji!=aj)break;if(j=N)printf(群有幺元%d！n,ai);e=ai;flag=1;break;if(!flag)printf(群没有幺元！n);A 中任何元素都有逆元：flag=1;for(i=0;iN;i+)for(j=0;jN;j+)if(opij=e&opji=e)break;/*e 是幺元*/if(j=N)flag=0;printf(A 中元素%d 没有逆元！n,aj);if(flag)printf(A 中任何元素都有逆元！n);