(完整版)离散数学实验指导书及其答案

《(完整版)离散数学实验指导书及其答案》由会员分享，可在线阅读，更多相关《(完整版)离散数学实验指导书及其答案（15页珍藏版）》请在金锄头文库上搜索。

1、实验一 命题逻辑公式化简 【实验目的】加深对五个基本联结词（否定、合取、析取、条件、双条件）的理解、掌握利用基本等价公式化简公式的方法。 【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。 实验用例：用化简命题逻辑公式的方法设计一个 5 人表决开关电路，要求 3 人以上（含3 人）同意则表决通过（表决开关亮） 。 【实验原理和方法】 （1） 写出 5 人表决开关电路真值表， 从真值表得出 5 人表决开关电路的主合取公式 （或主析取公式） ，将公式化简成尽可能含五个基本联结词最少的等价公式。 （2）上面公式中的每一个联结词是一个开关元件，将它们定义成 C 语言中的函数。 （3）输入 5

2、人表决值（0 或 1） ，调用上面定义的函数，将 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

3、; printf(请输入第五个人的表决值（0 或 1，空格分开） ：); scanf(%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、据正确，则货柜末上锁； （4）若 B 提供的证据不正确，则作案发生在营业时间； （5）货柜上了锁。 【实验原理和方法】 （1）符号化上面的命题，将它们作为条件，营业员 A 偷了手表作为结论，得一个复合命题。 （2）将复合命题中要用到的联结词定义成 C 语言中的函数，用变量表示相应的命题变元。将复合命题写成一个函数表达式。 （3）函数表达式中的变量赋初值 1。如果函数表达式的值为 1，则结论有效， A 偷了手表，否则是 B 偷了手表。 用命题题变元表示： A:营业员 A 偷了手表 B:营业员 B 偷了手表 C:作案不在营业时间 D:B 提供的证据正确 E:货柜末上锁 则上面的命题符号化为 (A|

5、B) & (!A|C) & (!D|E) & (D|!C) & !E 要求找到满足上面式子的变元 A，B 的指派便是结果。 C 语言算法： int 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 偷了手表*/ 实验三 集合运算 【实验目的】掌握用计算机求集合的交、并、差和补运算的方法。 【实验内

6、容】编程实现集合的交、并、差和补运算。 【实验原理和方法】 （1）用数组 A，B，C，E 表示集合。输入数组 A，B，E（全集） ，输入数据时要求检查数据是否重复（集合中的数据要求不重复） ，要求集合 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 中各个元素先保存在数组

7、C 中。将数组 B 中的元素逐一与数组 B 中的元素进行比较，把不相同的元素添加到数组 C 中，数组 C 便是集合 A 和集合 B 的并。 C 语言算法： for(i=0;im;i+) ci=ai; for(i=0;in;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;

8、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 中的元素进行比较，把不相同的元素保存到数组 C 中，数组 C 便是集合 A 关于集合 E 的补集。 求补集是一种种特殊的集合差运算。 实验四 二元关系及其性质 【实验目的】掌握二元关系在计算机上的表示方法，并掌握如果判定关系的性质。 【实验内容】 编程判断一个二元关系是否为等价关系，如果是，求其商集。 等价关系：集合 A 上的二元关系 R 同时具有自反性、对称性和传递性，则称 R

9、 是 A 上的等价关系。 【实验原理和方法】 （1） A 上的二元关系用一个 nn 关系矩阵 R=nnijr)(表示， 定义一个 nn 数组 rnn表示 nn 矩阵关系。 （2）若 R 对角线上的元素都是 1，则 R 具有自反性。 C 语言算法： int i,flag=1; for(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

10、=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+) for(k=0;kN & flag;k+) if(rij &rjk & rik!=1) flag=0; 如果 flag=1， 则 R 是传递关系 （5）求商集的方法：商集是由等价类组成的集合。已知 R 是等价关系，下面的算法是把等价类分行打印出来。

11、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); 实验五 关系闭包运算 【实验目的】掌握求关系闭包的方法。 【实验内容】编程求一个关系的闭包，要求传递闭包用 warshall 方法。 【实验原理和方法】 设 N 元关元系用 rNN表示，cNN表示各个闭包，函数 initc

12、(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;/*将关系矩阵的对角线上所有元素设为 1*/ （3）传递闭包：nRRRRt2)(，或用 warshall 方法。 方法 1：nRRRRt2)(，下面求得的关系矩

13、阵 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 装好 r*/ for(i=0;iN;i+) for(j=0;jN;j+) if(cji) for(k=0;kN;k+) cjk=cj

14、k+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）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。 C 语言算法： fl

15、ag=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;/ sequence 保留访问

16、点的序列，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; 实

17、验七 最优二叉树的应用 【实验目的】掌握求最优二叉树的方法。 【实验内容】最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率，求各通信符号对应的前缀码。 【实验原理和方法】 （1）用一维数组 fN存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。 （2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。 #include #include #define N 13 struct tree float num; struct tree *Lnode; struct tree *Rnode; * fpN;/保存结点 char s2*N;/放前缀码 void init

18、e_node(float 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

19、f,int n)/建立树 int i; struct tree *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); pre

20、order(p-Rnode,k+1,r); void main() float fN=2,3,5,7,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存贮运算

21、表。 （3）根据群的定义，代数系统(A，*)若为群，除运算表已表明运算*封闭外，还应该满足下列三个条件：*运算可结合、有幺元 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,op

22、xk,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);