当前位置：文档之家 › 离散数学实验报告__四个实验!!!

离散数学实验报告__四个实验!!!

  • 格式：doc
  • 大小：489.50 KB
  • 文档页数：19

. word资料 《离散数学》

课程设计 学 院 计算机学院 学生姓名 学 号 指导教师 评阅意见

提交日期 2011 年 11 月 25 日 .

word资料 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。

实验一、 编程判断一个二元关系的性质（是否具有自

反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的容。因为事物之间总是可以根

据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。

二、数学原理：自反、对称、传递关系

设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R就是A×B的一个合于R={(x,y)∈A×B|xRy}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的(x)((x∈A)→(∈R))=1

对称关系：对任意的x,y∈A，如果∈R，那么∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的  (x)(y)((x∈A)∧ (y∈A)∧(∈R)→(∈R))=1

传递关系：对任意的x,y,z∈A，如果∈R且∈R，那么∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的 (x)(y)(z)[(x∈A)∧(y∈A)∧(z∈A)∧((∈R)∧(∈R)→(∈R))]=1

三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数

组的运算来实现二元关系的判断。 图示： . word资料 性质 关系矩阵特性 自反性 主对角线元素全为1 反自反性 主对角线元素全为0 对称性 对称矩阵 反对称性 非主对角线上的元素等于1且与之对称的元素等于0 传递性 矩阵（M*M）中1所在的位置，M中与之相对应位置鲜红都为1

四、实验环境：Windows 7 Ultimate DEV C++

五、实验语言：C 语言

六、程序源代码：

#include"stdio.h" #define N 4 main() { int i,j,k; int f,e,z; int M[N][N]; printf("判断R是否为自反关系、对称关系、是否可传递？\n"); printf("请输入一个4*4的矩阵。\n"); for(i=0;ifor(j=0;jscanf("%d",&M[i][j]); for(i=0;i{ for(j=0;jprintf("%4d",M[i][j]); printf("\n"); }

for(i=0;i{ if(M[i][i]==1)//判断自反性 { if(i=N-1 e=0;

else ; . word资料 } else if(M[i][i]==0)//判断反自反性 { if(i=N-1) e=1;

else ; } else { e=2; break; } }

for(i=0;i{ for(j=0;j

if(M[i][j]!=M[j][i])//判断对称性 { f=1; break; } }

for(i=0;i{ for(j=0;j

if(M[i][j]==1)//判断反对称性 { if(M[j][i]==0) { if(i==(N-1)&&j==N-1) f=0; else break; } } . word资料 } if(f!=0&&f!=1) { f=2;

}

for(i=0;ifor(j=0;jif(M[i][j]==1) continue; else for(k=0;kif(M[i][k]*M[k][i]==0) continue; else z=0;

if(e==0) printf("关系R是自反关系\n"); else if(e==1) printf("关系R是反自反关系\n"); else if(e==2) printf("关系R是反自反关系\n"); if(f==0) printf("关系R是反对称关系\n"); else if(f==1) printf("关系R不是对称关系\n"); else if(f==2) printf("关系R是对称关系\n"); if(z==0) printf("关系R是不可传递关系\n"); else printf("关系R是可传递关系\n");

system("PAUSE"); }

七、程序运行截图： . word资料 i、程序启动截图： ii、程序输入截图： iii、程序运行结果截图: .

word资料 八、实验总结：实验简洁高效地判断二元关系的性质。

实验二、编程求一个二元关系的自反闭包、对称闭包、

传递闭包 一、前言引语 一个二元关系可能具有某种性质，也可能不具有这种性质。现在讨论怎样使一个二元关系变成具有指定性质的新关系，并且还要满足最小性条件。

二、数学原理 自反闭包、对称闭包、传递闭包 设R是定义在A上的二元关系，若存在A上的关系R′满足： 1) R′是自反的(或对称的、或可传递的)， 2) R R′， 3) 对A上任何其它满足 1）和 2）的关系R〞，都有： R′ R〞。 则称R′为R的自反闭包(或对称闭包、或传递闭包)，分别记为r(R)、(s(R)和t(R))。

三、实验原理 Warshall算法的基本思想 对每个结点（从第一列开始），找出所有具有到此结点的有向边的结点（即该列中元素为1的所在行的结点），再将这些结点所在行同该结点所在行进行逻辑加后作为这些结点所在的新行（添加新的有向边）（反映了如果这些结点没有到其它结点的有向边，但有到该结点的有向边，再通过该结点间接到达其它结点，根据传递闭包的定义，这些结点就必然有一条有向边到达其它结点）。 . word资料 ▪ 设R是集合上的二元关系,Mr是R的关系矩阵 ▪ (1)置新矩阵A:=Mr ▪ (2)置(列) j:=1 ▪ (3) 对所有的i(1≤i≤n) 如A(i,j)=1,则对k=1,2,…,n A(i,k):=A(i,k)  A(j,k) ▪ (即将A的第i行与A的第j行进行逻辑加后送回A的第i行) ▪ (4)j:=j+1 ▪ (5)如j≤n转(3),否则停止。

四、实验环境：Windows 7 Ultimate DEV C++

五、实验编程语言： C语言

六、实验程序源代码 //source file: War.cpp #include void War(int m,int n) { int i,j,k;设置临时变量 int a = 0, b = 0;设置临时变量 int arr[10][10]; for(a = 0; a < m; ++a) { printf("请输入矩阵第%d行元素:",a); for(b = 0; b < n; ++b) { scanf("%d",&arr[a][b]); } printf("\n"); }

for(i = 0; i < m; i++) { for( j= 0; j < m; j++) { if(arr[j][i] == 1) { for(k = 0;k < n; k++) { arr[j][k]=arr[i][k] || arr[j][k]; } } }

合集下载

离散实验报告

离散实验报告

实验一真值计算一、实验目的熟悉联结词合取、析取、条件和双条件的概念，编程求其真值。

二、实验内容从键盘输入两个命题P和Q的真值，求它们的合取、析取、条件和双条件的真值。

用C语言实现。

三、程序源代码#include <iostream>#include <iomanip>using namespace std;void main(){bool p,q,h,x,d,s;cout<<"请输入p的真值";cin >> p ;cout<<"请输入q的真值";cin>>q;h=p && q;x=p || q;if (p=0)d=1;elsed=p && q;s=h;cout <<"p合取q的值为"<<h<<" ; "<<"p析取q的值为"<<x<<"\n";cout <<"p到q的条件值为"<<d<<" ; "<<"p到q的双条件值为"<<s<<"\n";}四、程序运行结果实验二关系闭包计算一、实验目的熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法。

二、实验内容从键盘输入一个关系的关系矩阵，计算其自反闭包、对称闭包和传递闭包，传递闭包要求使用两种算法，即R+和Warshall算法。

用C语言实现。

三、程序源代码#include <iostream>#include <iomanip>#include <cmath>using namespace std;bool M[10][10],N[10][10],be[10][10],M2[10][10];int x,y,i,j,z,u;bool zhi;void xianshi();void qingling();void zifan();void duichen();void cdr_1();void cd();void ss();void ssfan();void ss2();void cdw();void main(){cout<<"请输入元素个数(元素个数不得大于10）";cin>>x;cout<<"请输入关系矩阵中的0项或是1项，按0输入0项，按1输入1项：";cin>>y;for (i=1;i<=x;i++){for (j=1;j<=x;j++)M[i-1][j-1]=!(bool)y;}cout<<"请输入关系矩阵中的"<<(bool)y<<"项"<<"第一个数为行数，第二个数为列数,输入00结束";while (i!=0 && j!=0){cin>>i>>j;if (i==0 && j==0)break;M[i-1][j-1]=(bool)y;cout<<"M["<<i<<"]["<<j<<"]="<<M[i-1][j-1]<<"\n";}ssfan();xianshi();zifan();duichen();cdr_1();cdw();}void ss(){for (i=1;i<=x;i++){for (j=1;j<=x;j++)M[i-1][j-1]=N[i-1][j-1];}}void ssfan(){for (i=1;i<=x;i++){for (j=1;j<=x;j++)N[i-1][j-1]=M[i-1][j-1];}}void xianshi(){for (i=1;i<=x;i++){for (j=1;j<=x;j++)cout<<M[i-1][j-1]<<" ";cout<<"\n";}cout<<"\n";}void qingling(){for (i=1;i<=x;i++){for (j=1;j<=x;j++)M[i-1][j-1]=0;}}void zifan(){ss();cout<<"自反闭包的矩阵为："<<"\n";for (i=1;i<=x;i++){M[i-1][i-1]=1;}cout<<"\n";xianshi();}void duichen(){ss();cout<<"对称闭包的矩阵为："<<"\n";for (i=1;i<=x;i++){for (j=1;j<=x;j++)if (M[i-1][j-1]==true)M[j-1][i-1]=true;}cout<<"\n";xianshi();}void cd(){zhi=false;for (i=1;i<=x;i++){for (z=1;z<=x;z++){for (j=1;j<=x;j++){zhi=zhi || ( M[i-1][j-1] && N[j-1][z-1] );}M2[i-1][z-1]=zhi;zhi=false;}}}void ss2(){for (i=1;i<=x;i++){for (j=1;j<=x;j++)M[i-1][j-1]=M2[i-1][j-1];}}void cdr_1(){ss();cout<<"用R++的方法求传递闭包的矩阵为："<<"\n";for (u=1;u<=x;u++){for (i=1;i<=x;i++){zhi=false;for (j=1;j<=x;j++){zhi=be[i-1][j-1] || M[i-1][j-1];be[i-1][j-1]=zhi;zhi=false;}}cd();ss2();}for (i=1;i<=x;i++){for (j=1;j<=x;j++)cout<<be[i-1][j-1]<<" ";cout<<"\n";}cout<<"\n";}void cdw(){cout<<"用Warshall方法计算传递闭包的结果为；"<<"\n";ss();for (i=1;i<=x;i++){for (j=1;j<=x;j++){if ( M[j-1][i-1] == 1){for (z=1;z<=x;z++){M[j-1][z-1]=M[j-1][z-1] || M[i-1][z-1];}}}}xianshi();}四、运行结果1.输入2.输出实验三计算两结点间长度为m的路的数目一、实验目的熟悉邻接矩阵和两结点间长度为m的路的数目的关系并编程计算。

离散数学实验报告

离散数学实验报告

“离散数学”实验报告目录一、实验目的 (3)二、实验内容 (3)三、实验环境 (3)四、实验原理和实现过程（算法描述） (3)1、实验原理........................................................................................................2、实验过程.......................................................................................................五、实验数据及结果分析 (13)六、源程序清单 (24)源代码 (24)七、其他收获及体会 (45)一、实验目的实验一：熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。

实验二：掌握关系的概念与性质，基本的关系运算，关系的各种闭包的求法。

理解等价类的概念，掌握等价类的求解方法。

实验三：理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。

二、实验内容实验一：1. 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。

（A）2. 求任意一个命题公式的真值表（B，并根据真值表求主范式（C））实验二：1.求有限集上给定关系的自反、对称和传递闭包。

（有两种求解方法，只做一种为A，两种都做为B）2. 求有限集上等价关系的数目。

（有两种求解方法，只做一种为A，两种都做为B）3. 求解商集，输入集合和等价关系，求相应的商集。

（C）实验三：以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A）。

并计算任意两个结点间的距离（B）。

对不连通的图输出其各个连通支（C）。

三、实验环境C或C＋＋语言编程环境实现。

四、实验原理和实现过程（算法描述）实验一：1.实验原理（1）合取：二元命题联结词。

离散结构实验报告

离散结构实验报告

一、实验目的1. 理解离散结构的基本概念和特性。

2. 掌握常见离散结构的构建方法和应用。

3. 培养动手能力和团队协作精神。

二、实验原理离散结构是指由有限个元素组成的具有特定关系的集合。

常见的离散结构有图、树、序列等。

图是一种由顶点和边组成的集合，其中顶点表示实体，边表示实体之间的关系；树是一种特殊的图，具有层次结构，每个节点有且仅有一个父节点；序列是一种有序的元素集合，元素之间有先后顺序。

三、实验内容1. 图的构建与应用（1）构建一个无向图，包含5个顶点和5条边，表示5个城市之间的交通路线。

（2）利用邻接矩阵和邻接表表示该无向图。

（3）计算图中顶点的度、连通度和最小生成树。

2. 树的构建与应用（1）构建一个二叉树，包含5个节点，表示一个简单的组织结构。

（2）计算二叉树的高度、节点个数、叶子节点个数。

（3）判断二叉树是否为完全二叉树。

3. 序列的构建与应用（1）构建一个有序序列，包含10个整数。

（2）计算序列的逆序对个数。

（3）将序列进行排序，并分析排序算法的效率。

四、实验步骤1. 图的构建与应用（1）使用MATLAB或Python等编程语言，定义一个图类，包含顶点、边、邻接矩阵和邻接表等属性。

（2）添加顶点和边，构建无向图。

（3）使用图类中的方法计算顶点的度、连通度和最小生成树。

2. 树的构建与应用（1）使用MATLAB或Python等编程语言，定义一个树类，包含节点、父节点、左右子节点等属性。

（2）添加节点，构建二叉树。

（3）使用树类中的方法计算树的高度、节点个数、叶子节点个数，判断是否为完全二叉树。

3. 序列的构建与应用（1）使用MATLAB或Python等编程语言，定义一个序列类，包含元素、大小、逆序对个数等属性。

（2）添加元素，构建有序序列。

（3）使用序列类中的方法计算逆序对个数，并使用排序算法对序列进行排序。

五、实验结果与分析1. 图的构建与应用实验结果：构建了一个包含5个顶点和5条边的无向图，计算出了顶点的度、连通度和最小生成树。

离散数学计算机实验报告

离散数学计算机实验报告

离散实验报告实验一真值计算1、实验目的熟悉五个常用联结词合取、析取、条件和双条件的概念，掌握真值表技术。

2、实验内容与要求定义1 设P表示一个命题，由命题联结词┐和命题P连接成┐P，称┐P为P的否定式复合命题，┐P读“非P”。

称┐为否定联结词。

┐P是真，当且仅当P为假；┐P是假，当且仅当P为真。

定义2 设P和Q为两个命题，由命题联结词∧将P和Q连接成P∧Q，称P∧Q为命题P和Q的合取式复合命题，P∧Q读做“P与Q”，或“P且Q”。

称∧为合取联结词。

当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。

定义3 设P和Q为两个命题，由命题联结词∨把P和Q连接成P∨Q，称P∨Q为命题P和Q的析取式复合命题，P∨Q读做“P或Q”。

称∨为析取联结词。

当且仅当P和Q的真值同为假，P∨Q的真值为假；否则，P∨Q的真值为真。

定义4 设P和Q为两个命题，由命题联结词→把P和Q连接成P→Q，称P→Q为命题P和Q的条件式复合命题，简称条件命题。

P→Q读做“P条件Q”或者“若P则Q”。

称→为条件联结词。

当P的真值为真而Q的真值为假时，命题P→Q的真值为假；否则，P→Q 的真值为真。

定义5 令P、Q是两个命题，由命题联结词↔把P和Q连接成P ↔ Q，称P ↔ Q为命题P和Q的双条件式复合命题，简称双条件命题，P ↔Q读做“P当且仅当Q”，或“P等价Q”。

称↔为双条件联结词。

当P和Q的真值相同时，P ↔ Q的真值为真；否则，P ↔ Q 的真值为假。

本实验要求从键盘输入两个命题P和Q的真值，求它们的合取、析取、条件和双条件的真值。

用C语言或MATLAB实现。

3、实验报告要求列出实验目的、实验内容、实验步骤、源程序和实验结果。

源代码：#include <iostream.h>void main(){int p,q;cout<<"请分别输入P,Q的真值：";cin>>p>>q;if(p>1||p<0){cout<<"P的真值有误，请重新输入!"<<endl;}if(q>1||q<0){cout<<"Q的真值有误，请重新输入!"<<endl;}if(p==0&&q==0){cout<<"P∧Q=0"<<endl;cout<<"P∨Q=0"<<endl;cout<<"P→Q=1"<<endl;cout<<"P<->Q=1"<<endl;}if(p==0&&q==1){cout<<"P∧Q=0"<<endl;cout<<"P∨Q=1"<<endl;cout<<"P→Q=1"<<endl;cout<<"P<->Q=0"<<endl;}if(p==1&&q==0){cout<<"P∧Q=0"<<endl;cout<<"P∨Q=1"<<endl;cout<<"P→Q=0"<<endl;cout<<"P<->Q=0"<<endl;}if(p==1&&q==1){cout<<"P∧Q=1"<<endl;cout<<"P∨Q=1"<<endl;cout<<"P→Q=1"<<endl;cout<<"P<->Q=1"<<endl;}}运行结果：请分别输入P,Q的真值：0 1P∧Q=0P∨Q=1P→Q=1P<->Q=0Press any key to continue实验二关系闭包计算1、实验目的熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法。