logo资料库

离散数学实验报告2.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.81M 资料格式：pdf 举报 版权申诉
第1页 / 共34页
第2页 / 共34页
第3页 / 共34页
第4页 / 共34页
第5页 / 共34页
第6页 / 共34页
第7页 / 共34页
第8页 / 共34页
资料共34页，剩余部分请下载后查看
    离散数学实验报告 （实验 ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间
    目录 第一章 实验概述.......................................................................................................... 3 1.1 实验目的 ......................................................................................................... 3 1.2 实验内容 ......................................................................................................... 3 1.3 实验环境 ......................................................................................................... 3 第二章 实验原理和实现过程...................................................................................... 4 2.1 实验原理 ......................................................................................................... 4 2.1.1 求有限集上给定关系的自反、对称和传递闭包 ............................... 4 2.1.2 求有限集上等价关系的数目 ............................................................... 4 2.1.3 求解商集，输入集合和等价关系，求相应的商集 ........................... 5 2.2 实验过程（算法描述） ................................................................................. 6 2.2.1 程序整体思路 ....................................................................................... 6 2.2.2 实现“关系元素的提取和提取元素的赋值”的算法 ........................ 6 2.2.3 实现“求有限集上给定关系的自反、对称和传递闭包”的算法....... 6 2.2.4 实现“求有限集上等价关系的数目”的算法...................................... 7 2.2.5 实现“求解商集，输入集合和等价关系，求相应的商集”的算法7 第三章 实验数据及结果分析...................................................................................... 8 3.1 输入集合和关系的功能测试及结果分析...................................................... 8 3.1.1 输入集合元素 ........................................................................................ 8 3.1.2 输入关系 ................................................................................................ 8 3.2 操作选择的功能测试和结果分析 ................................................................. 9 3.2.1 选择“1”求自反、对称、传递闭包 .................................................. 9 3.2.2 选择“2”求等价关系........................................................................... 10 3.2.3 选择“3”求商集 ................................................................................ 11 3.2.4 选择其它按钮 ...................................................................................... 12 3.2.5 选择继续输入 ...................................................................................... 12 3.2.5 选择不继续输入 .................................................................................. 13 3.2.6 选择“4”退出系统 ............................................................................ 14 第四章 实验收获和心得体会.................................................................................... 15 4.1 实验收获 ....................................................................................................... 15 I
    4.2 心得体会 ....................................................................................................... 15 第五章 实验源程序清单............................................................................................ 16 5.1 程序代码 ....................................................................................................... 16 II
    第一章 实验概述 1.1 实验目的 掌握关系的概念与性质，基本的关系运算，关系的各种闭包的求法。理解等 价类的概念，掌握等价类的求解方法。 具体说来，有以下几点—— 1. 掌握离散数学中涉及的相关概念。 2. 培养学生的逻辑思维能力和算法设计的思想。 3. 熟练掌握 C/C++语言程序设计的基本方法和各种调试手段。 4. 熟练掌握包括数组、链表以及邻接表或邻接矩阵等数据结构的建立和运 用。 1.2 实验内容 1. 求有限集上给定关系的自反、对称和传递闭包。（有两种求解方法，只做 一种为 A，两种都做为 B） 2. 求有限集上等价关系的数目。（有两种求解方法，只做一种为 A，两种都 做为 B） 3. 求解商集，输入集合和等价关系，求相应的商集。（C） 注意：题目类型分为A，B，C三类，其中A为基本题，完成A类题目可达到设 计的基本要求，其他均为加分题，并按字母顺序分数增加越高。 1.3 实验环境 C 或 C＋＋语言编程环境实现。 3
    第二章 实验原理和实现过程 2.1 实验原理 2.1.1 求有限集上给定关系的自反、对称和传递闭包 关系采用关系矩阵的形式表示会比较容易处理。自反闭包和对称闭包的求法 比较简单，传递闭包有两种方法求解。一种直接通过定义，另一种称为Warshall 算法。 Warshall算法： 设R的关系矩阵为M (1)令矩阵A=M (2)置i=1 (3)对所有的j，若A[j，i]=1，则 对于 k=1，2，„，n，令A[j，k]=A[j，k]+A[i，k] (4)i=i+l． (5)若i≤n，则转到(3)，否则结束。 2.1.2 求有限集上等价关系的数目 集合上的等价关系与该集合的划分之间存在一一对应关系。一个等价关系对 应一个划分，一个划分也对应一个等价关系。我们把 n 个元素的集合划分成 k 块的方法数叫第二类 Stirling 数，表示为 S(n,k)。例如有甲、乙、丙、丁四人， 若所有人分成 1 组，只有所有人在同一组这个方法，因此 S(4,1) = 1；若所有 人分成 4 组，只可以人人独立一组，因此 S(4,4) = 1；若分成 2 组，可以是甲 乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三 人同一组另一人独立一组，即是： 1. {A,B},{C,D} 2. {A,C},{B,D} 3. {A,D},{B,C} 4. {A},{B,C,D} 5. {B},{A,C,D} 6. {C},{A,B,D} 7. {D},{A,B,C} 因此 S(4,2) = 7。 4
    给定 S(n,n) = S(n,1) = 1，有递归关系 S(n,k) = S(n − 1,k − 1) + kS(n − 1,k) 上面的递推式可以用组合证明：一方面，如果将元素 1 单独拿出来划分成 1 个集合，那么方法数是 S(n-1,k-1)；另一方面，如果元素 1 所在的集合不止一 个元素，那么可以先将剩下的 n-1 个元素划分好了以后再选一个集合把 1 放进去， 方法数是 k*S(n-1,k)；有加法原理得证。 第二类 Stirling 数可用递推和递归两种方法求解。 集合上所有等价类的个数即为 k 从 1 到 n，所有 S(n,k)之和。 2.1.3 求解商集，输入集合和等价关系，求相应的商集 商集即等价类构成的集合，要求商集，首先需要判断输入的关系是否为等价 关系，否则没有商集。确定集合A={a1,a2,a3,„,an}关于R的等价类的算法如下： (1) 令A中每一个元素自成一个子集，如A1={a1},A2={a2},„,An={an} (2) 对R中每个二元组< x,y >，判定x和y所属子集。假设x属于Ai，y属于Aj， 若Ai<>Aj，则将Ai并入Aj，并置Ai为空；或将Aj并入Ai，并置Aj为空。一般将元素少 的集合合并到元素多的集合。 (3) A1 ,A2,„,An中所有非空子集构成的集合即为所求商集。 要实现集合的并运算，采用并查集(union-find sets)是一种不错的方法。 并查集是一种树型的数据结构，多棵树构成一个森林，每棵树构成一个集合，树 中的每个节点就是该集合的元素，找一个代表元素作为该树(集合)的祖先。并查 集可用于快速实现处理一些不相交集合（Disjoint Sets）的并。一般用途就是 用来维护某种等价类。并查集支持以下三种操作： (1) Make_Set(x) 把每一个元素初始化为一个集合 初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本 身。 (2) Find_Set(x) 查找一个元素所在的集合 查找一个元素所在的集合，只要找到这个元素所在集合的祖先即可。判断两 个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。 (3) Union(x,y) 合并x,y所在的两个集合 合并两个不相交集合操作很简单：首先设置一个数组Father[x]，表示x的" 父亲"的编号。那么，合并两个不相交集合的方法就是，找到其中一个集合的祖 先，将另外一个集合的祖先指向它。 关于并查集的具体操作实现请参考有关资料。 5
    2.2 实验过程（算法描述） 2.2.1 程序整体思路 本程序完成了实验所要求的全部功能，其基本思路是——“运用模块化的思 想，将实现“求有限集上给定关系的自反、对称和传递闭包”、“求有限集上等价 关系的数目”和“求解商集，输入集合和等价关系，求相应的商集”的子函数分 开编写，然后将它们以子函数的形式添加到主函数 main 的代码前面，在要使用 相应的子函数时，进行子函数调用就可以实现相应的功能了。” 本程序的一大特色就是开发者灵活使用了 C 语言中的数组概念来进行开发， 用数组来模拟关系矩阵的运算，通过相应的算法实现了全部的功能。 2.2.2 实现“关系元素的提取和提取元素的赋值”的算法 在关系元素的提取中，开发者熟练地运用数组和指针，先将用户输入的字符 保存在数组中，然后利用指针指向输入的第一个字符，对它进行判断。如果是 a 到 z 之间的字母，说明是集合中的元素，将其保存到另一个数组中，然后修改指 针，使它指向原数组中的另一个元素。如果不属于 a 到 z 之间，说明不是集合中 的元素，直接修改指针，使它指向原数组中的另一个元素。就这样依次对用户输 入的关系表达式进行提取，最后就得到了我们的集合元素。 在提取元素的赋值中，依次将储存了提取的关系元素数组中的每两个元素和 集合元素数组中的元素进行比较，发现匹配的之后，将表征初始关系矩阵的二维 数组的相应元素赋值为 1，其它的赋值为 0。这样就建立了初始关系矩阵。 2.2.3 实现“求有限集上给定关系的自反、对称和传递闭包”的算法 在求取自反闭包的关系矩阵中，只需将初始关系矩阵主对角线上的所有元素 赋值为 1 即可。 在求取对称闭包的关系矩阵中，根据“对称关系的关系矩阵关于主对角线对 称”的原理，将初始关系矩阵中除对角线之外的其他数值进行判断，若发现值为 1 的元素，就将此元素关于主对角线对称的相应元素赋值为 1，这样就实现的了 对称闭包关系矩阵的求取。 在求取对称闭包的关系矩阵中，有两种算法—— 1) 直接通过定义算法 根据“传递关系的关系矩阵的特征——如果 Aij=1,且 Ajk=1,则 Aik=1”的 原理，将初始关系矩阵中的所有元素进行对应的规则判断，如果满足条件的话， 按照定义将相对应的元素赋值为 1，这样就得到的了对称闭包关系矩阵。 6
    2) Warshall 算法 设R的关系矩阵为M (1)令矩阵A=M (2)置i=1 (3)对所有的j，若A[j，i]=1，则 对于 k=1，2，„，n，令A[j，k]=A[j，k]+A[i，k] (4)i=i+l． (5)若i≤n，则转到(3)，否则结束。 所得的矩阵 A 即为传递闭包的关系矩阵。 2.2.4 实现“求有限集上等价关系的数目”的算法 在实现“求有限集上等价关系的数目”的功能时，有两种算法—— 1) 递推算法 该算法先将初始矩阵中第一列和主对角线上的元素都赋值为 1，然后依 次将上一行的两个元素按照 S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)的思路进 行相加，结果保存在相应的单元中，最终所得的矩阵即为满足输出条件的矩阵 2) 递归算法 该算法遵循求等价关系中 S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)的 原则，利用了 C 语言中递归的思想，在递归调用子函数的内部，间接地调用自身， 把问题转化为规模缩小了的同类问题的子问题，然后递归调用函数来表示问题的 解。 2.2.5 实现“求解商集，输入集合和等价关系，求相应的商集”的算法 商集即等价类构成的集合，要求商集，首先需要判断输入的关系是否为等价 关系，否则没有商集。实现的算法比较简单，根据“等价关系是自反的、对称的 和传递的”的性质，将求得的自反闭包、对称闭包以及传递闭包的关系矩阵依次 和初始关系矩阵进行比较，如果他们完全相同，就说明是等价关系，否则不是。 确定集合A={a1,a2,a3,„,an}关于R的等价类的算法如下： (1) 令A中每一个元素自成一个子集，如A1={a1},A2={a2},„,An={an} (2) 对R中每个二元组< x,y >，判定x和y所属子集。假设x属于Ai，y属于Aj， 若Ai<>Aj，则将Ai并入Aj，并置Ai为空；或将Aj并入Ai，并置Aj为空。一般将元素少 的集合合并到元素多的集合。 (3) A1 ,A2,„,An中所有非空子集构成的集合即为所求商集。 在实现这种功能时，没有使用到实验指导书中所建议的“并查集”的概念， 但是也能够很好的实现了功能。 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料