离
散
数
学
实
验
报
告
姓名: 学号: 班级:
离散数学实验报告
实验一 真值计算
实验内容:
从键盘输入两个命题P和Q的真值,求它们的合取、析取、条件和双条件的真值。用C语言实现。
实验源程序和运行结果如下:
#include "iostream.h"
void main()
{
char p,q,t;
int p1,q1;
cout<<"输入p,q的真值(F或T)"<<endl;
cin>>p>>q;
if(p=='F')
p1=0;
else
p1=1;
if(q=='F')
q1=0;
else
q1=1;
//下面进行为运算
if(p1|q1)
t='T';
else
t='F';
cout<<"p析取q为"<<t<<endl;
if(p1&q1)
t='T';
else
t='F';
cout<<"p和取q为"<<t<<endl;
if((!p1)|q1)
t='T';
else
t='F';
cout<<"p条件q为"<<t<<endl;
if(p1==q1)
t='T';
else
t='F';
cout<<"p双条件q为"<<t<<endl;
}
实验二 关系闭包计算
实验内容:
从键盘输入一个关系的关系矩阵,计算其自反闭包、对称闭包和传递闭包,传递闭包要求使用两种算法,即R+和Warshall算法。用C语言实现。
实验源程序运行结果如下:
#include<stdio.h>
int he(int,int);
void main()
{
int
a[100][100],b[100][100],c[100][100],d[100][100],I[100][100],i,j,k,n,m,p,q,t;
printf("请输入关系矩阵的阶数\n"); scanf("%d",&n); printf("请输入此关系矩阵\n"); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); printf("选择1计算自反闭包...\n选择2计算对称闭包...\n选择3用R+计算传递闭包...\n选择4用washall计算传递闭包...\n计算结束后选择0退出\n");
scanf("%d",&t); switch(t) { case 1: { for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(i==j)
I[i][j]=1; else I[i][j]=0; } } for(i=0;i<n;i++) } { for(j=0;j<n;j++) b[i][j]=he(a[i][j],I[i][j]),printf("%4d",b[i][j]); printf("\n"); };break; case 2: { for(i=0;i<n;i++) { } for(j=0;j<n;j++) b[j][i]=a[i][j]; printf("对称闭包矩阵为\n"); for(i=0;i<n;i++) { for(j=0;j<n;j++) c[i][j]=he(a[i][j],b[i][j]),printf("%4d",c[i][j]); printf("\n"); } };break; case 3: {
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ } { c[i][j]=a[i][j]; d[i][j]=a[i][j]; b[i][j]=0; } for(m=0;m<n;m++) { for(i=0;i<n;i++) for(k=0;k<n;k++) { } for(j=0;j<n;j++) { } b[i][k]=b[i][k]||(c[i][j]*a[j][k]); for(p=0;p<n;p++) { } for(p=0;p<n;p++) { } for(q=0;q<n;q++) { } d[p][q]=d[p][q]||b[p][q]; b[p][q]=0; for(q=0;q<n;q++) c[p][q]=b[p][q];
}
printf("矩阵的传递闭包为\n"); for(i=0;i<n;i++) { } for(j=0;j<n;j++) { } printf("\n"); printf("%4d",d[i][j]);
};break;
case 4: { for(j=0;j<n;j++) { for(k=0;k<n;k++) { } if(a[k][j]==1) { } for(i=0;i<n;i++) a[k][i]=a[k][i]||a[j][i]; } printf("传递闭包为\n"); for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%4d",a[i][j]); printf("\n");
} } };break; default:printf("Error\n"); }
int he(int a,int b) {
}
int c; if(a==0&&b==0) c=0; else c=1; return c;
实验三 计算两结点间长度为m的路的数目
实验内容:
从键盘输入图的邻接矩阵和一正整数m,计算结点两两之间长度为m的路的数目。考虑有向图和无向图。用C语言实现。
实现可达性矩阵。
实验源程序和运行结果如下:
#include<stdio.h>
void main()
{
int a[100][100],b[100][100],c[100][100],d[100][100],i,j,k,t,p,q,n,m; printf("请输入关系矩阵的阶数\n"); scanf("%d",&n); printf("请输入路的长度\n"); scanf("%d",&m); printf("请输入此关系矩阵\n"); for(i=0;i<n;i++) { } for(t=0;t<m-1;t++) { for(j=0;j<n;j++) { } scanf("%d",&a[i][j]); c[i][j]=a[i][j]; d[i][j]=a[i][j]; b[i][j]=0; for(i=0;i<n;i++) { for(j=0;j<n;j++)
} { } for(k=0;k<n;k++) b[i][j]+=c[i][k]*a[k][j]; for(p=0;p<n;p++) { } } for(k=0,i=0;i<n;i++) { } for(j=0;j<n;j++) k+=c[i][j]; for(q=0;q<n;q++) { } c[p][q]=b[p][q]; b[p][q]=0; printf("结点两两之间长度为%d的路的数目为%d\n",m,k); for(t=0;t<n;t++) { for(i=0;i<n;i++) { for(j=0;j<n;j++) { } for(k=0;k<n;k++) b[i][j]+=c[i][k]*a[k][j];
} for(p=0;p<n;p++) {
}
for(q=0;q<n;q++) { c[p][q]=b[p][q]; b[p][q]=0; d[p][q]+=c[p][q]; } } printf("该关系矩阵的可达型矩阵为\n"); for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(d[i][j]>=1) d[i][j]=1; else d[i][j]=0; printf("%4d",d[i][j]); } printf("\n"); } }
实验四 最优树的构造
实验内容:
从键盘输入一组权值,构造出对应的最优树,列出构造过程。用C语言实现。
实验源程序和运行结果如下:
#include<stdio.h>
void main()
{
int a[100][100],d[100][100]={0};
int i,j,k,min,m,n,p; int b[100][100]={0}; int c[100][100]; printf("请输入邻接矩阵的阶数:");
scanf("%d",&p);
for(i=0;i<p;i++) {printf("请输入带权值矩阵的第%d行,用空格隔开:",i+1);
for(j=0;j<p;j++)
} for(i=0;i<p;i++) for(j=0;j<p;j++) c[i][j]=a[i][j]; scanf("%d",&a[i][j]); for(k=0;k<p*p;k++)
{ min=100;
for(i=0;i<p;i++) for(j=0;j<p;j++) {if(a[i][j]==0)
continue;
else if(a[i][j]<min) {min=a[i][j];
} m=i,n=j; } a[m][n]=a[n][m]=0; if(b[m][n]==1||b[n][m]==1) continue;
d[m][n]=d[n][m]=1;
for(i=0;i<p;i++)
for(j=0;j<p;j++) b[i][j]=d[i][j];
for(i=0;i<p;i++)
for(j=0;j<p;j++) } if(b[j][i]==1) for(k=0;k<p;k++) b[j][k]=b[j][k]||b[i][k];
for(i=0;i<p;i++)
for(j=0;j<p;j++) if(d[i][j]==1) d[i][j]=c[i][j]; printf("最小生成树的邻接矩阵为(带权值):\n"); for(i=0;i<p;i++)
}
{for(j=0;j<p;j++) {printf("%d ",d[i][j]); } printf("\n"); }
离散数学实验报告
(实验ABC)
目录
第一章 实验概述... 2
1.1 实验目的... 2
1.2 实验内容... 2
1.3 实验环境... 2
第二章 实验原理和实现过程... 3
2.1 实验原理... 3
2.1.1建立图的邻接矩阵,判断图是否连通... 3
2.1.2 计算任意两个结点间的距离... 3
2.1.3对不连通的图输出其各个连通支... 4
2.2 实验过程(算法描述)... 4
2.2.1 程序整体思路... 4
2.2.2具体算法流程... 4
第三章 实验数据及结果分析... 6
3.1建立图的邻接矩阵并判断图是否连通的功能测试及结果分析... 6
3.1.1输入无向图的边... 6
3.1.2建立图的连接矩阵... 7
3.2 其他功能的功能测试和结果分析... 8
3.2.1计算节点间的距离... 8
3.2.2判断图的连通性... 8
3.2.3输出图的连通支... 9
3.2.4退出系统... 9
第四章 实验收获和心得体会... 10
4.1 实验收获... 10
4.2 心得体会... 11
第五章 实验源程序清单... 12
5.1 程序代码... 12
以偶对的形式输入一个无向简单图的边,建立该图的邻接矩阵,判断图是否连通(A),并计算任意两个结点间的距离(B),对不连通的图输出其各个连通支(C)。
注意:题目类型分为A,B,C三类,其中A为基本题,完成A类题目可达到设计的基本要求,其他均为加分题,并按字母顺序分数增加越高。
基本要求如下:程序需具有基本的容错控制,在输入错误时有处理手段;程序界面友好,需要输入的地方有输入说明,说明输入的内容和格式要求等;实验原理和实现过程应该详细分析问题,给出解决思路,描述算法思想,不能用源程序代替算法;测试数据应全面,包括非法输入的处理结果等都应包含在内。
C或C++语言编程环境实现。
根据图的矩阵表示法建立邻接矩阵A,并利用矩阵的乘法和加法求出可达矩阵,从而判断图的连通性。
连通图的定义:在一个无向图 G 中,若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径),则称vi和vj是连通的。如果 G 是有向图,那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。
判断连通图的实现:在图中,从任意点出发在剩余的点中,找到所有相邻点循环,直到没有点可以加入为止,如果有剩余的点就是不连通的,否则就是连通的。或者也可用WallShell算法,由图的邻接矩阵判断图是否连通。
图中两点i,j间的距离通过检验Al中使得aij为1的最小的l值求出。
图的连通支的求法则可采用图的遍历算法,图的遍历有深度优先和广度优先两种方法,其中深度优先算法又分为递归和非递归两种。
在无向图中,如果任何两点可达,则称图G是连通的,如果G的子图G’是连通的,没有包含G’的更大的子图G’’是连通的,则称G’是G的连通支。
当有判断出关系不是连通的之后,将需要求出分支模块
实现方法如下:先定义一个二维数组用来存放相应的分块,先选定一个点,并将它放在数组中,然后判断,如果后面的和他是联通的便将它也放在同一个数组中,否则将其存入其他的数组中,后面以此类推,在输出相应的数组,便可判断出连通分支。
本程序的一大特色就是开发者灵活使用了C语言中的数组概念来进行开发,用数组来模拟矩阵的运算,通过相应的算法实现了全部的功能。
在main(){系统界面显示;用do…while循环语句和switch语句实现功能1,2,3……的选择,并调用相关的子程序;用start、goto start实现控制流的转移;}
liantongzhi(){求连通支,此子函数通过一个for循环控制遍历每个结点,并调用函数DFS()求每个结点的连通支;}
DFS(int a){通过实参与形参,将结点数据代入函数;定义顺序栈变量;通过for循环初始化;为a置已访问标志,已经访问了的元素为1;定义顺序栈的第一个元素;通过while循环实现结点遍历,栈不为空时执行循环;栈顶元素赋值;通过for循环寻找v的下个未访问的邻接点;通过if条件句,若x,i是边和节点i未被访问过,处理结点的访问,并进行访问标志,进栈等操作;通过if条件句,若v已访问到的出点,则将其退栈;}
shuru(){输入结点关系;通过for循环先将矩阵所有元素赋值0;再通过另一for循环,根据输入结点的关系,将矩阵中相应的元素赋值,有关系则为1;}
linjiejuzhen(){输出邻接矩阵;通过for循环,依次按格式输出邻接矩阵的元素;}
julijuzhen(){根据A的n次方矩阵及其中元素,判断并显示两结点间的距离;调用子函数linjiejuzhen(),以确定并显示距离为1的两结点;通过for循环显示距离为1的结点对;再通过一系列的for循环,计算A的n次方矩阵并显示结果,根据其中的元素,判断并显示结点间的距离;详细算法请见附录相关部分的注释;}
kedajuzhen(){求可达矩阵;通过一系列for循环,根据公式,计算可达矩阵;通过for循环,将矩阵中不为0的一切值赋为1以生成可达矩阵并显示;通过for循环和if条件句的组合,根据可达矩阵的元素特点,判断图的连通性,若可达矩阵矩阵中有0,则跳出循环,显示不可连接;根据判断结果显示内容,不可连通或可连通;}
这就是集合的输入界面。
当选择“4”时,程序会根据可达矩阵判断图的连通性。
当选择“6”时,程序会退出系统。
在刚开始编写程序的时候,为了实现最基本的输入和输出功能,我却花了大量的时间在那上面。原因在后来查阅的很多资料后才知道的,像scanf函数之类的小函数,其实是还有很多需要注意的地方的。
之后,在编写数组和指针的过程中,花了很大的一部分时间去研发算法,开发程序,在理论上反复证明没有问题之后,再在计算机上进行操作,编写代码,进行调试,反复了很久,才慢慢的实现了全部的功能,真的是来之不易。
离散数学实验报告姓名学号班级离散数学实验报告实验一真值计算实验内容从键盘输入两个命题P和Q的真值求它们的合取析取条件和双条件的真值…
离散数学实验报告姓名学号班级实验一连结词逻辑运算一实验目的实现二元合取析取蕴涵和等价表达式的计算熟悉连接词逻辑运算规则利用程序语言…
离散数学课程设计学院计算机学院学生姓名学号指导教师评阅意见提交日期20xx年11月25日引言离散数学是现代数学的一个重要分支也是计…
离散数学实验报告题目专业学号姓名指导教师提交日期实验一五种连结词的逻辑运算一实验目的用C语言实现两个命题变元的合取析取蕴涵和等价表…
浙江万里学院实验报告课程名称离散数学实验名称数理逻辑实验专业班级计算机111姓名李俊学号20xx014620实验日期20xx10专…
离散数学实验报告题目专业学号姓名指导教师提交日期实验一五种连结词的逻辑运算一实验目的用C语言实现两个命题变元的合取析取蕴涵和等价表…
离散数学应用实践实验报告课序号03学号姓名任课教师陈瑜评阅成绩评阅意见提交报告时间20xx年1月3日课程名称离散数学运用实践学生姓…
离散数学实验报告目录第一章实验概述311实验目的312实验内容313实验环境3第二章实验原理和实现过程421实验原理4211逻辑连…
离散数学实验报告目录第一章实验概述311实验目的312实验内容313实验环境3第二章实验原理和实现过程421实验原理4211逻辑连…
实验一命题逻辑推理1实验用例根据下面的命题试用逻辑推理方法确定谁是作案者写出推理过程1营业员A或B偷了手表2若A作案则作案不在营业…
离散数学课程设计学院计算机学院学生姓名学号指导教师评阅意见提交日期20xx年11月25日引言离散数学是现代数学的一个重要分支也是计…