- 1、本文档共6页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
四川大学实验报告利用Warshall
四川大学实验报告
利用Warshall算法求二元关系的可传递闭包
离散数学课程设计
学 院 软件学院指导老师 冯伟森学生姓名 赵帅
学 号 0843042021(08级)
提交日期 2009年12月25日
利用Warshall算法求二元关系的可传递闭包
学生:赵帅 指导老师:冯伟森
摘要
本实验主要是研究利用Warshall算法求二元关系的可传递闭,实验主要内容是研究当集合的阶数N较大时,求二元关系的可传递闭包的工作量时相当庞大的。幸运的时1962年S.Warshall提出了一个计算R+的有效方法,可在计算机上编程实现。采用C语言函数写出这个算法。程序中用temp[i][j]表示关系矩阵MR的第i行第j列元素,用||表示逻辑或计算。计算R+的函数名为Warshall,它的两个形式参数m和n分别表示关系矩阵M和矩阵的行数。函数的实现实际上是一个三重循环结构.
关键词
二元关系关系矩阵可传递闭包Warshall算法三重循环
引 言
离散数学是现代数学的一个重要分支,也是计算机科学技术,电子信息技术,生物技术等的核心基础课程.二元关系是离散数学中重要内容。世界上的事物都在一定范围内以某种方式互相联系,例如天体之间可以用的是同一星系来划分,人们之间可以用是否有共同的祖先来定血缘.类似的数学或者计算机科学中的研究对象也以各种不同形式互相联系着,例如整数之间以大小,整除或同余关系互相联系着,命题公式之间以是否具有相同的主合取范式相联系,程序中两个变量可以是否占有同一内存地址相联系。总之,事物之间总可以根据需要确定相应的关系.从数学的角度来看,这类联系就是某个集合中元素之间存在的关系。一个二元关系可能具有某种性质,也可能不具有这种性质。关系闭包就是使一个二元关系变成具有指定性质的关系,并且还要满足最小条件。
Warshall算法的基本思想
对每个结点(从第一列开始),找出所有具有到此结点的有向边的结点(即该列中元素为1的所在行的结点),再将这些结点所在行同该结点所在行进行逻辑加后作为这些结点所在的新行(添加新的有向边)(反映了如果这些结点没有到其它结点的有向边,但有到该结点的有向边,再通过该结点间接到达其它结点,根据传递闭包的定义,这些结点就必然有一条有向边到达其它结点。)
设R是集合上的二元关系,Mr是R的关系矩阵
(1)置新矩阵A:=Mr
(2)置(列) j:=1
(3)对所有的i(1≤i≤n)如A(i,j)=1,则对k=1,2,…,nA(i,k):=A(i,k) A(j,k)
(即将A的第i行与A的第j行进行逻辑加后送回A的第i行)
(4)j:=j+1
(5)如j≤n转(3),否则停止。
主要实验流程图
程序开始
程序开始
输入矩阵的行
数和列数
输入矩阵各元素
的值
输入是否
正确?
不正确
正
确
计算出可传递闭包关系
矩阵
打印可传递闭包的关系矩
阵
结束
实验源代码
//Warshall.cpp#includestdio.hvoidwarshall(intk,intn)
{
inti,j,t;inttemp[20][20];for(inta=0;ak;a++)
{
printf(请输入矩阵第%d行元素:,a);
for(intb=0;bn;b++)
{
scanf(%d,temp[a][b]);
}
}
for(i=0;ik;i++){for(j=0;jk;j++){
if(temp[j][i]==1)
{
for(t=0;tn;t++)
{
temp[j][t]=temp[i][t]||temp[j][t];
}
}
}
}
printf(可传递闭包关系矩阵是:\n);for(i=0;ik;i++)
{
for(j=0;jn;j++)
{
printf(%d,temp[i][j]);
}
printf(\n);
}
}
voidmain()
{
printf(利用Warshall算法求二元关系的可传递闭包\n);voidwarshall(int,int);
intk,n;
printf(请输入矩阵的行数i:);scanf(%d,k);
printf(请输入矩阵的列数j:);scanf(%d,n);warshall(k,n);
}
试验结果截图展示
1、启动程序
2、输入矩阵并得到结果
实验总结
Warshall算法给我们提供了一个求二元关系传递闭包的高效方法。综合现代计算机技术,利用Warshall算法我们可轻松的求出一个二元关系的可传递闭包。
指导老师评阅意见
指导老师(签字):
年 月 日
您可能关注的文档
最近下载
- 放紧线工作及安全注意事项.pptx
- 统编版道德与法治六年级上册期末试卷(含答案).docx VIP
- 部编版语文四年级上册第2单元习作《我的家人》课件.pptx VIP
- 2024年重庆市安全员-B证考试题库附答案.doc VIP
- 《汽车发动机再制造过程质量控制研究》16000字.doc
- 航空学院航空法规.ppt
- 隧道注浆堵水施工方案.pdf
- 统编版六年级上册道德与法治期末测试卷(含答案).doc VIP
- 必考点10等边三角形的性质与判定-【题型·技巧培优系列】2022-2023学年八年级数学上册精选专题(人教版)(原卷版+解析).docx VIP
- 2024新信息科技三年级第一单元:开启信息生活大单元整体教学设计.docx
文档评论(0)