《(完整版)离散数学实验指导书及其答案》由会员分享,可在线阅读,更多相关《(完整版)离散数学实验指导书及其答案(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);