实验一  命题逻辑推理

1.实验用例

根据下面的命题，试用逻辑推理方法确定谁是作案者，写出推理过程。

（1）营业员A或B偷了手表；

（2）若A作案，则作案不在营业时间；

（3）若B提供的证据正确，则货柜末上锁；

（4）若B提供的证据不正确，则作案发生在营业时间；

（5）货柜上了锁。

2.实验目的

加深对命题逻辑推理方法的理解。

3.实验内容

用命题逻辑推理的方法解决逻辑推理问题。

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的指派便是结果。

5．实验代码

6．实验结果

B偷了手表

实验二  关系的运用

1.实验原理和方法

在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则加上关系的转置矩阵（逻辑加法）

2．实验代码

5．实验结果

1.自反闭包

2.传递闭包

3.对称闭包

实验三  图论

1.实验用例

如下图所示的赋权图表示某七个城市 及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小并计算其最小值.

 

2实验原理和方法

为了求解最小代价，使花费的总代价最小，这是数学中经典的求解最小耗费生成树的算法。其核心思想是寻找每一步的最优解继而求得全局最优解。

为了求得最小耗费生成树，我们运用数学中经典的Krusal算法，此算法的核心思想是：

1、    假设该图G是不连通的，对该图的边以非降序权重新排列

2、    对于排序表中的每条边，如果现在把它放入T不会形成回路的话，则把它加入到生成树T中；否则丢弃

3、    输出最小生成树的结果，得到我们想要的答案

3．实验代码

4．实验结果

因而最后求得的最小耗费是：此时的最小耗费是：23+1+4+9+3+17=57（万元）

实验四  最优二叉树在通信编码中的应用

1.实验内容

输入一组通信符号的使用频率，求各通信符号对应的前缀码。

2.实验原理和方法

（1）用一维数组f[N]存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。

（2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。

3．实验代码

4．实验结果

第二篇：离散数学(集合的运算)实验报告

大连民族学院

计算机科学与工程学院实验报告

实验题目：                 集合的运算                    

课程名称：                 离散数学                      

实验类型：□演示性  □验证性  □操作性  □设计性  □综合性

专业：    网络工程         班级：网络111班

学生姓名：张山           学号：2011083123    

实验日期：20##年12月22日     实验地点：I区实验机房        

实验学时：8小时                    实验成绩：

指导教师签字：                               年   月   日

老师评语：

实验题目：集合的运算

实验原理：

1、实验内容与要求：

实验内容：本实验求两个集合间的运算，给定两个集合A、B，求集合A与集合B之间的交集、并集、差集、对称差集和笛卡尔乘积。

实验要求：对于给定的集合A、B。用C++/C语言设计一个程序（本实验采用C++），该程序能够完成两个集合间的各种运算，可根据需要选择输出某种运算结果，也可一次输出所有运算结果。

    2、实验算法：

实验算法分为如下几步：

（1）、设计整体框架

该程序采取操作、打印分离（求解和输出分开）的思想。即先设计函数求解各部分运算并将相应结果传入数组（所求集合）中，然后根据需要打印运算结果。

    （2）、建立一个集合类（Gather）

类体包括的数组a、b、c、d、e、f、g分别存储集合A、B以及所求各种运算的集合。接口（实现操作的函数）包括构造函数，菜单显示函数，求解操作函数，打印各种运算结果等函数。

    （3）、设计类体中的接口

构造函数：对对象进行初始化，建立集合A与集合B。

菜单显示函数：设计提示选项，给使用者操作提示。

操作函数：该函数是程序的主题部分，完成对集合的所有运算的求解过程，并将结果弹入（存入）对应数组（集合）中，用于打印。

具体操作如下：

1*求交集：根据集合中交集的定义，将数组a、b中元素挨个比较，把共同元素选出来，并存入数组c（交集集合）中，即求得集合A、B的交集。

2*求并集：根据集合中并集的定义，先将数组a中元素依次存入数组g（并集集合）中，存储集合A中某元素前，先将其与已存入g中的元素依次比较，若相同则存入下一个元素，否则直接存入g中，直到所有A中元素存储完毕。接着把b中元素依次存入数组g（并集集合）中，存储前将b中每个元素依次与已存入数组g中的集合A的元素比较，若数组g中没有与该元素相同的元素，则将该元素存入g（并集集合）中，否则进行下一次比较，直到所有b中元素比较并存储完毕，即求得A与B的并集。

3*求差集：根据集合中差集的定义知，差集分为两部分，A对B的差集（数组d）和B对A的差集（e）。设计求解A对B的差集，将集合A中元素依次与B中元素比较，若B中无元素与该元素相同，则将其存入数组d中（同时删除d中相同的元素，操作方法与求并集时删除相同元素类似），否则进行下一轮比较，直到A中所有元素比较完毕，即求得A对B的差集（数组d）。求解B对A的差集方法与求解A对B的差集类似，这里不再重复。

4*求对称差：根据集合中对称差集的定义，将3*中所求两部分差集求并集并存入数组f中即可。操作过程与求并集相似，这里不再重复。

5*求笛卡尔乘积：根据集合中笛卡尔乘积集的定义，分为A*B和B* A。先设计A* B是我算法，将a中元素循环依次与b中元素配对即可。求B* A与求A* B类似，这里不再重复。

实验步骤：

一、分析实验

阅读实验指导书和离散数学课本，充分理解整个实验的实验内容及要求，以便对实验进行科学的设计。然后对整个实验进行“解剖”，即把整个实验系统地分成若干部分，分别针对各个部分进行分析，最后预测程序设计过程中可能遇到的问题及解决方案。

二、实验设计

基于第一步的实验分析制定实验设计的整体方案，然在计算机上设计整体框架，接着依据最初得到的方案有序的设计该程序的各个分支。最后将分支分别填入主体框架的相应位置，检查设计是否有书写错误。没有则进行调试，有则修改。重复上述过程，直到没有书写错误。

三、调试程序

对第二步设计的程序进行编译链接，对多组具有代表性的数据进行测试，检查程序是否有逻辑错误和程序漏洞。若无，则进行下一步程序优化，否则，续修改调试，直至没有逻辑错误和漏洞。

四、优化程序

在前面设计的程序的基础上，查找是否有可以简化程序或是有缺陷的地方，亦或是否有可以添加的功能。有，则进行相应的修改，对整个程序进行优化升级，直至趋于完善。

五、处理数据

输入：

运行结果：

六、对实验进行归纳、总结，撰写实验报告。

实验记录：

一、集合初始化数据输入：

1、第一行输入m

2、第二行输入m个整数

3、第三行输入n

4、第四行输入n个整数

输入数据的含义：

1、m：集合A的元素个数

2、n：集合B的元素个数

3、m个整数：集合A中的元素

4、n个整数：集合B中的元素

二、求解输入：

使用者可以根据提示输入I、U、C、D、K、A、P、E。

其含义如下：

1、I：输出交集

2、U：输出并集

3、C：输出差集

4、D：输出对称差

5、K：输出笛卡尔乘积

6、A：输出所有集合运算结果

7、P：打印集合A和集合B

8、E：退出系统

一、实验过程中遇到的问题及其解决过程

实验过程遇到的问题很多，主要有一下问题。

首先是实验的分析，最初没有对实验原理理解透彻，在求差集的时候没考虑到A、B间相互求差集；于是在原有的基础上对程序添加缺少的部分。

其次是对整个程序的框架设计，最初设计是顺序求解并输出集合A、B的交、并、差、对称差及笛卡尔乘积。但这种设计太低级，不能根据使用者的意愿求解集合的运算；于是对原来的程序上“大动干戈”，把它的整体结构做调整，将原来混合不清、顺序死板的设计改成操作、打印分离的“动态”结构。

第三是对数据的处理不够完善，比如在最初设计的程序中，当集合中含有相同元素时，程序不能完善处理，结果中会有重复元素。于是在程序中添加一个删除相同元素的操作。

最后便是功能的完善问题了，相比最终程序，缺乏一些人性化的功能。于是在相应位置添加功能，使程序完善。

二、实验结束时的程序清单及运行结果

结果还是比较完善的，试运行数据如下：

输入：5

1 1 2 3 4

5

1 1 a b 5

A

输出：

两个集合的交集是：

1

两个集合的并集是：

1 2 3 4 5 a b c

两个集合的差集A-B是：

2 3 4

两个集合的差集B-A是：

 a b 5

两个集合的对称差集是：

2 3 4 5 a b

两个集合的笛卡尔乘积是：

A*B:

<1,1> <1,1> <1,a> <1,b> <1,5>

<1,1> <1,1> <1,a> <1,b> <1,5>

<2,1> <2,1> <2,a> <2,b> <2,5>

<3,1> <3,1> <3,a> <3,b> <3,5>

<4,1> <4,1> <4,a> <4,b> <4,5>

B*A:

<1,1> <1,1> <1,2> <1,3> <1,4>

<1,1> <1,1> <1,2> <1,3> <1,4>

<a,1> <a,1> <a,2> <a,3> <a,4>

<b,1> <b,1> <b,2> <b,3> <b,4>

<5,1> <5,1> <5,2> <5,3> <5,4>

三、实验总结

我选择的实验题目很简单，因此试验用时多，但通过实验的规划、各部分设计、以及整体的测试优化，不仅提高了我的程序设计水平，还让我对离散数学有了全新的认识，可谓是一举多得。之前我一直以为数学就是在书本上写写算算，玩弄数字游戏，压根儿没想过离散数学也能在程序设计上大显身手。

这次试验让我再次体会到了设计算法的重要性和对细节的把握，而算法，就是对数据的处理。那么就要求对所涉及的数学知识牢牢掌握，不能似是而非，不然设计的算法是残缺的。甚至漏洞百出，因而放弃之前的算法推倒重来。

本学期已学过数据结构，可谓程序设计的法宝，运用的好可以得到简便高效的方案，一直是我写代码的不二法宝。现在我才发现离散数学对计算机程序设计也非常重要。它不仅介绍了数据结构里面的一些内容，还涉及数字逻辑等方面的的知识，掌握好离散数学我们就能快速地想出高效的解决方案。

终于理解入学时学长（姐）们说的“数据结构、离散数学和数字逻辑，是你们计算机生涯的必修课，走得有多远全看你对它们的掌握”。

实验报告

           课程名称：  离散数学     

           实验题目：集合的运算  

           实验类型：   操作型       

           指导老师：    姜楠       

学院：计算机科学与工程学院

专业：网络工程           

班级：网络121班         

姓名：张山               

学号：2011083123          

日期：20##年12月22日