离散数学上机实验报告.docx
《离散数学上机实验报告.docx》由会员分享，可在线阅读，更多相关《离散数学上机实验报告.docx（19页珍藏版）》请在冰点文库上搜索。
离散数学上机实验报告
离散数学上机实验报告
———————————————————————————————— 作者：
————————————————————————————————日期：
ﻩ
《离散数学》
实验报告
姓名:
学号:
班级：
ﻬ
实验一 连结词逻辑运算
一.实验目的
实现二元合取、析取、蕴涵和等价表达式的计算。
熟悉连接词逻辑运算规则,利用程序语言实现逻辑这几种逻辑运算。
二.实验内容
从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、蕴涵和等价四种运算的真值。
要求对输入内容进行分析，如果不符合0、1条件需要重新输入，程序有良好的输入输出界面。
三．实验环境
使用MiｃroｓoftVisual C+＋6.０为编程软件，采用称C/C＋+语言为编程语言实现。
四.实验过程
１.算法分析:
合取：
p，q都为1的时候为1,其他为0
析取：
p,q都为0的时候为０，其他为1
蕴含：
ｐ为1，q为0时为0,其他为１
等价:
p,q同真同假
2.程序代码：
#iｎclｕdｅ
inｔ maiｎ（）
{
ﻩinｔP,Ｑ,a，b，c，d，p,ｑ;
printf（"P的值"）;
for（P＝0;P<2；P++）
ﻩ{
ﻩfｏr（Q=0;Q＜２;Q++）
ﻩﻩprintf（"\ｔ%d＂,P）;
ﻩ}
printf（"\nQ的值"）;
ｆor（Ｐ=0;P<2;P++）
ﻩ{
ﻩﻩfｏr（Q=０;Q<２;Q＋+）
ﻩprintf（"＼t％ｄ",Q）;
ﻩ｝
printf（"\n非P的值"）;
for（P=0;P<２;P++）
{
ﻩｆor（Ｑ＝0;Q<2;Ｑ＋+）
ﻩ{
ﻩﻩｉf（Ｐ＝=０）／*判断非P的值*/
ﻩﻩﻩp=1;
ﻩﻩeｌsｅ
ﻩﻩp＝0；
ﻩﻩﻩｐｒintｆ（"＼t%d",p）；
ﻩ｝
ﻩ}
ﻩprintf（"\n 非Q的值＂）;
ﻩfor（Ｐ＝０;P＜2；P++）
ﻩ{
ﻩfor（Ｑ＝0；Q<2;Q++）
ﻩﻩ{
ﻩﻩif（Q==1）／*判断非Q的值*/
ﻩﻩﻩq＝０;
ﻩelse
ﻩﻩq=1;
ﻩpｒｉｎｔf（"\ｔ％ｄ",q）;
}
ﻩ}
ﻩprinｔf（"\n Ｐ与Q的值"）;
foｒ（Ｐ=0;P<2;P++）
ﻩ{
ﻩfｏr（Ｑ＝0;Q<２;Ｑ++）
ﻩ｛
ﻩﻩﻩif（Q=＝0||P==0）／*判断P与Q的值*/
ﻩa=0;
ﻩﻩeｌsｅ
ﻩﻩa=1;
ﻩｐrintf（"＼t%d",ａ）;
ﻩ｝
ﻩ｝
ﻩprintｆ（"\nＰ或Q的值"）;
ﻩfoｒ（P=０;P<２;P+＋）
ﻩ{
for（Q＝０;Q<2;Q++）
ﻩﻩ{
ﻩif（Q=＝1||P＝=1）／＊判断P或Ｑ的值*/
ﻩﻩﻩb=1;
ﻩelｓe
ﻩﻩb＝0；
ﻩprintf（"\t%ｄ",b）;
}
ﻩ}
ﻩprｉntf（"＼nＰ蕴含Ｑ的值＂）;
ﻩfｏr（P＝０;P<２;P++）
ﻩ{
ﻩｆor（Q=０;Q＜２;Q++）
ﻩﻩ｛
ﻩﻩif（P==1&&Q==0）/＊判断P蕴含Q的值*/
ﻩﻩc=0；
ﻩﻩelse
ﻩｃ＝1;
ｐｒintｆ（"\t%d＂,ｃ）;
｝
}
ｐrintｆ（＂\nP等价Q的值"）;
for（P＝0;P<2;P＋+）
ﻩ{
ﻩﻩｆｏr（Q=0;Q<2;Ｑ++）
ﻩ{
ﻩﻩｉｆ（P＝＝Q）/＊判断P等价Q的值*/
ﻩd=1;
ﻩﻩｅlｓｅ
ﻩﻩｄ=0;
ﻩﻩｐｒiｎtf（＂\ｔ%d",d）;
}
ﻩ｝
prｉntｆ（"\ｎ"）；
ｒetｕrｎ0；
}
3.实验数据及结果分析:
实验二关系的复合运算及逆运算
一．实验目的
熟悉关系的复合运算和逆运算，编程实现关系复合运算和逆运算算法。
二.实验内容
利用矩阵求解有限集上的复合关系和逆关系。
三.实验过程
1.算法分析:
复合运算就将两个用矩阵表示的关系进行复合，即在第一个矩阵中寻找值为１的元素坐标（i,j ）,在第二个矩阵第j行寻找值为1的元素，若有，且坐标为（j,k）,则产生的新的关系的矩阵中坐标为（i,k）的元素值为1。
逆运算就是将用矩阵中值为１的元素坐标（i,j）对调,产生新的关系的矩阵中坐标为（ｊ,i）的元素值为1。
2.程序代码:
//关系的复合运算
＃incluｄe
uｓｉngnamesｐacesｔｄ;
intmａｉn（）
{
intａ[1００][100］,b[10０］［10０],c[１０0]［100],i,j，k,ｎ;
ﻩcｏuｔ<<"请输入集合X中元素的个数:
"；
cin>＞n;
ｃouｔ<<＂请输入关系矩阵Mr的格式：
"<<ｅndl;
foｒ（ｉ=０;i＜ｎ；i++）
ﻩ{
ﻩﻩfｏr（j＝0;jﻩﻩﻩciｎ>＞a[i］［j］;
}
ﻩcoｕt<＜"请输入关系矩阵Ms的格式:
"<for（i=０;i＜n；i++）
ﻩ{
ﻩﻩfoｒ（j=０；ｊﻩcin>>b[ｉ］[j];
ﻩ}
ﻩfｏr（i=0;i<ｎ;ｉ＋+） //进行复合运算
ﻩ{
for（ｊ=0;j<ｎ;j++）
ﻩif（ａ[i］[j]==1）
ﻩfｏr（ｋ=０;ｋ<ｎ;k+＋）
ﻩﻩif（b[ｊ］[k]==1）
ﻩﻩﻩﻩc［ｉ][ｋ]=1；
}
foｒ（i=0;iﻩ{
ﻩfor（ｊ＝０;j＜ｎ;j++）
ﻩiｆ（ｃ［ｉ］[j]!
＝1）
ﻩｃ[i］[ｊ]=0；
}
ﻩcout<ｃout＜<＂关系矩阵Mr与Ms的复合运算结果是:
＂<ｆoｒ（ｉ=0；ｉ＜n;ｉ++）
ﻩ{
ﻩﻩｆor（ｊ=0;jﻩﻩｃout<＜c[i］［j］<<" ＂;
ﻩcout<}
ｒetｕｒｎ0;
｝
//关系的逆运算
＃ｉnclude
intｍain（）
｛
ｉnta[10０］［100],b[100][100］,ｎ，i,ｊ,index;
ﻩprｉntf（＂请输入集合X中元素的个数:
"）;
scａｎf（＂%d",&ｎ）;
priｎｔf（"请输入关系矩阵Ｍr的格式:
\n"）;
ﻩfor（i=0；i<ｎ;i＋＋）
{
fｏr（j=0;jﻩscanf（"%d＂,&ａ[ｉ][j］）;
ﻩ}
fｏｒ（i=０;i<ｎ;ｉ+＋）//进行逆运算
ﻩ{
foｒ（j=0；j<ｎ;j＋+）
ﻩif（ａ[ｉ][j］＝＝1）
ﻩﻩ{ﻩ
ﻩindｅx=i；
ﻩi＝ｊ;
ﻩﻩj=ｉnｄex;
ﻩﻩb[ｉ][ｊ]=１；
}
}
foｒ（i＝0;ｉ＜n;i++）
ﻩ{
ﻩfor（j=０；jﻩﻩif（b[i][j]!
=1）
ﻩﻩﻩb[ｉ][ｊ]=0;
｝ﻩ
ﻩｐrintｆ（"\n关系矩阵Mrc为:
\n"）；
for（i=0；i<ｎ;i+＋）
ﻩ{
fｏr（j=0;j<ｎ；j＋+）
ﻩﻩprinｔf（"％ｄ"，b[i]［j］）;
ﻩprintｆ（"\n"）；
｝
ﻩreturｎ 0;ﻩ
}
3．实验数据及结果分析:
实验三 关系的闭包运算
一.实验目的
熟悉关系的闭包运算，编程实现关系闭包运算算法。
二．实验内容
利用矩阵求解有限集上给定关系的自反、对称和传递闭包。
三.实验过程
1.算法分析：
在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系,其自反闭包只要将矩阵的主对角线全部置为1就可;对称闭包则加上关系的转置矩阵（逻辑加法）;传递闭包则直接根据t（Ｒ）=R+。
2．程序代码：
#ｉnｃｌude＜iostreaｍ>
ｕsingnａmespacｅsｔｄ;
vｏiｄ ｄｅlｉver（iｎtx[100][１０0],ｉntｙ[100][100],int n）;
int maｉｎ（）
{
ﻩｉnti,j，ｎ,R［100]［10０],r［100］[１00],ｓ［10０］[10０],t［100][100];
cｏｕt＜＜"请输入矩阵的阶:
";
cin＞>ｎ;
ﻩcouｔ＜＂<fｏr（i＝０;iﻩ｛
for（j＝0;j<ｎ;j+＋）
ﻩﻩﻩcｉn>>R［i][j];
}
ﻩｆor（i＝０;ｉ<ｎ;i＋+） ／／将R的关系矩阵赋值给ｒ,s,t
ﻩ{ﻩ
ﻩﻩfor（j=0；j<ｎ;j++）
ﻩ｛
ﻩﻩﻩr[i][ｊ]=R［i][j］;
ﻩﻩs[i]［j]=Ｒ[ｉ][ｊ];
ﻩt［i］[j]=R[i][ｊ];
ﻩ}
｝
ｆor（i=0;i{
iｆ（r［ｉ][i]==0）
ｒ[i]［i］=１；
}
ﻩcout<"<ﻩｆor（i=０;iﻩ｛
ﻩfｏr（j=0；jﻩﻩﻩcoｕt<＜r[i][j]＜<"＂;
cout<}
for（i=0；i＜n;i++） //对称闭包运算
ﻩ｛
ﻩｆor（j=０;j<ｉ;j+＋）
ﻩ{
iｆ（s[i]［j］==1||ｓ[j][ｉ］=＝1）
ﻩ{
ﻩﻩｓ[ｉ][j]=１;
ﻩﻩﻩs[ｊ][i］=1;
ﻩ}
ﻩ}
ﻩ}
couｔ<＜endｌ<<"对称闭包关系矩阵ｓ（Ｒ）：
＂<ﻩfｏr（ｉ=0;i{
ﻩﻩfor（j=0;j＜ｎ;j+＋）
ﻩﻩcoｕt<＜ｓ[i][j］<<"";
ﻩcout<＜ｅndｌ;
}
ﻩdelivｅr（t,R,n）; /／关于传递闭包的函数
ﻩreｔｕｒn 0;
}
ｖｏid ｄeliver（iｎtx[100][10０],iｎty[10０][1０0],intn）／／关于传递闭包的函数
{
ｉntｉ,j，k,m,z[100][100];
for（ｍ=０;m｛
ﻩﻩfor（ｉ=0;i＜n；i++）
ﻩﻩ{
ﻩﻩfor（j=０；jﻩ{
ﻩﻩﻩｉf（ｘ[i］[j]＝=1）
ﻩ{
ﻩfor（k=0;k＜n；k+＋）
ﻩﻩﻩif（y[j][k]＝=１） ／/进行复合运算
ﻩﻩﻩﻩz［i][k]＝1;
}
ﻩ}
ﻩ｝
ﻩfor（i=０;i{
ﻩfｏｒ（j＝0;jﻩﻩﻩif（z[i］［j]!
=1）
ﻩﻩﻩz[i][j]＝0;
ﻩﻩ}
ﻩﻩfoｒ（ｉ=０;i＜n；ｉ＋+）
ﻩﻩ{ﻩ
ﻩｆor（j=０;j＜n;j++）
｛
ﻩﻩｘ[ｉ][j]=x[i][j］+z[i］[j]; //进行传递闭包运算
ﻩﻩ｝
ﻩﻩ}
ﻩﻩfoｒ（i＝0;ｉ｛
for（j＝０；j＜ｎ;j++）
ﻩﻩif（x[i］［j]!
=0）
ﻩﻩx［i][j］=１；
}
ﻩ｝
cout<"<＜endｌ;
ﻩfor（ｉ＝0;ｉ＜n；ｉ++） ／/输出ｘ的关系矩阵
｛
ﻩｆor（j=0；j＜ｎ;ｊ＋+）
ﻩﻩﻩcout＜＜x［ｉ]［j］＜＜"＂;
ﻩﻩcouｔ<}
}
3.实验数据及结果分析：
ﻬ
实验四 图的矩阵表示
一．实验目的
熟悉图的矩阵表示方法——邻接矩阵、可达矩阵和关联矩阵。
二．实验内容
利用邻接矩阵得到的可达矩阵来求解图的连通性质。
三.实验过程
１.算法分析：
可达矩阵表示图中任意两个节点间的可达关系，而邻接矩阵表示图中任意两个节点的邻接关系。
求解邻接矩阵
可知任意两个节点之间是否存在互相连通的路,从而判断是否可达。
２.程序代码:
#incluｄe
usiｎｇ namespaｃestd；
ｖoidmain（）
{
ﻩint i,j,k,n,m,ａ[10０]［１０0］,b[1０0］[100］，c[100][１００]，ｄ[10０]［100];
cout＜<"请输入矩阵阶数:
＂;
cｉｎ>>ｎ;
cout<<"请输入邻接矩阵a：
"＜＜endｌ；
ﻩｆoｒ（ｉ=0；i｛
foｒ（ｊ=０;ｊ｛
ﻩﻩcｉｎ>>a[ｉ］[j];
ﻩﻩｂ[i]［ｊ］=a[i][j];
ﻩﻩ}
ﻩ}
for（i=0；i＜n；i＋+）/／矩阵ｄ为零矩阵
{
ﻩﻩｆｏｒ（j=0;j＜n;j+＋）
ﻩﻩd[ｉ］[j]=0；
ﻩ}
ﻩfor（m=０;ｍﻩ{
ｆor（i=0;ｉﻩﻩ{
ﻩﻩｆor（ｊ=0；jﻩｃ[i][j]=0;
}
ﻩﻩfor（ｋ=０;k<ｎ;k+＋）
ﻩﻩ{
ﻩfoｒ（i=0；iﻩﻩﻩfor（j=0;j＜n;ｊ++）
ﻩﻩﻩ{
ﻩﻩc[k]［i］=c[k][ｉ］+b[ｋ］[j］＊a［j］[ｉ];/／矩阵的乘法运算
ﻩﻩ}
ﻩﻩ}
ﻩfｏｒ（i=0;iﻩ{
ﻩﻩﻩfor（ｊ＝0;j＜n;j++）
ﻩ｛
ﻩb[ｉ][j]＝c[i］[j];
ﻩd［i]［j]=ｄ[i][j]＋ｂ[ｉ][j];
ﻩ}
ﻩﻩ｝
ｃoｕt<<"ｍ为"<"<＜ｅndｌ;
ﻩﻩfｏr（i=0;i＜ｎ;i++）
｛
ﻩｆor（ｊ=0;j<ｎ;j+＋）
ﻩﻩﻩcｏut＜ﻩcout<｝
｝
ﻩfor（ｉ=０;ｉ{
ﻩfoｒ（j=0;j＜n;j＋+）
ﻩﻩif（d[i]［j]!
＝0）
ﻩd[i］[j]＝1；
}
cｏut<<"可达矩阵d为:
"＜ﻩｆｏr（i=0;i{
ｆor（ｊ=0;jﻩﻩcout＜<ｄ[i］[j]<＜"＂；
ﻩcoｕt＜<ｅnｄl；
ﻩ}
}
ﻬ
3．实验数据及结果分析:
升级会员 