離散作業(yè)_河北工業(yè)大學(xué)

1、實(shí)驗(yàn)一 真值計(jì)算1、實(shí)驗(yàn)?zāi)康?熟悉五個(gè)常用聯(lián)結(jié)詞合取、析取、條件和雙條件的概念，掌握真值表技術(shù)。2、實(shí)驗(yàn)內(nèi)容與要求定義1設(shè)P表示一個(gè)命題，由命題聯(lián)結(jié)詞和命題P連接成P，稱P為P的否定式復(fù)合命題， P讀“非P”。稱為否定聯(lián)結(jié)詞。P是真，當(dāng)且僅當(dāng)P為假；P是假，當(dāng)且僅當(dāng)P為真。定義2設(shè)P和Q為兩個(gè)命題，由命題聯(lián)結(jié)詞將P和Q連接成PQ，稱PQ為命題P和Q的合取式復(fù)合命題，PQ讀做“P與Q”，或“P且Q”。稱為合取聯(lián)結(jié)詞。當(dāng)且僅當(dāng)P和Q的真值同為真，命題PQ的真值才為真；否則，PQ的真值為假。定義3設(shè)P和Q為兩個(gè)命題，由命題聯(lián)結(jié)詞把P和Q連接成PQ，稱PQ為命題P和Q的析取式復(fù)合命題，PQ讀做“P或Q

2、”。稱為析取聯(lián)結(jié)詞。當(dāng)且僅當(dāng)P和Q的真值同為假，PQ的真值為假；否則，PQ的真值為真。定義4設(shè)P和Q為兩個(gè)命題，由命題聯(lián)結(jié)詞把P和Q連接成PQ，稱PQ為命題P和Q的條件式復(fù)合命題，簡(jiǎn)稱條件命題。PQ讀做“P條件Q”或者“若P則Q”。稱為條件聯(lián)結(jié)詞。當(dāng)P的真值為真而Q的真值為假時(shí)，命題PQ的真值為假；否則，PQ的真值為真。定義5令P、Q是兩個(gè)命題，由命題聯(lián)結(jié)詞«把P和Q連接成P « Q，稱P « Q為命題P和Q的雙條件式復(fù)合命題，簡(jiǎn)稱雙條件命題，P « Q讀做“P當(dāng)且僅當(dāng)Q”，或“P等價(jià)Q”。稱«為雙條件聯(lián)結(jié)詞。當(dāng)P和Q的真值相同時(shí)，P 

3、1; Q的真值為真；否則，P « Q的真值為假。本實(shí)驗(yàn)要求從鍵盤(pán)輸入兩個(gè)命題P和Q的真值，求它們的合取、析取、條件和雙條件的真值。用C語(yǔ)言或MATLAB實(shí)現(xiàn)。3. 實(shí)驗(yàn)步驟： 在輸入P、Q真值后，會(huì)依次輸出合取、析取、條件、雙條件的真值。本實(shí)驗(yàn)源程序力求簡(jiǎn)潔易懂，所以在設(shè)計(jì)時(shí)應(yīng)用簡(jiǎn)單的語(yǔ)句并省去了許多繁雜的選擇，如1與T、0與F的置換等。但本實(shí)驗(yàn)在操作易于理解方面也有很大的體現(xiàn)。4.源程序：（1）方法一：#include<stdio.h>void main(void)printf("輸入P、Q的真值(1為T(mén)，0為F)：n");int P,Q;scanf

4、("%d",&P); /輸入P、Q的值scanf("%d",&Q); /求真值printf("合取：%dn",P&&Q);printf("析?。?dn",P|Q);printf("條件：%dn",!P|Q);printf("雙條件：%dn",P&&Q+!P&&!Q);（2）方法二：#include<iostream>using namespace std;int main()char P,Q;int

5、i;cout<<"請(qǐng)輸入兩個(gè)命題的真值(T/F):"<<endl;for(i=1;i<=4;i+)cin>>P;cin>>Q;if(P='T'&&Q='T')cout<<"合取為T(mén)，析取為T(mén)，條件為T(mén)，雙條件為T(mén)"<<endl;else if(P='T'&&Q='F')cout<<"合取為F，析取為T(mén)，條件為F，雙條件為F"<<endl;e

6、lse if(P='F'&&Q='T')cout<<"合取為F，析取為T(mén)，條件為T(mén)，雙條件為F"<<endl;else if(P='F'&&Q='F')cout<<"合取為F，析取為F，條件為T(mén)，雙條件為T(mén)"<<endl;5.實(shí)驗(yàn)結(jié)果：（1）方法一：（2）方法二：實(shí)驗(yàn)二 關(guān)系閉包計(jì)算1、實(shí)驗(yàn)?zāi)康?熟悉Warshall算法，掌握求關(guān)系的自反閉包、對(duì)稱閉包和傳遞閉包的方法。2、實(shí)驗(yàn)內(nèi)容與要求定義6 設(shè)R是A上的二元關(guān)

7、系，R的自反（對(duì)稱、傳遞）閉包是關(guān)系R1，則 R1是自反的（對(duì)稱的、傳遞的） RÍR1 對(duì)任何自反的（對(duì)稱的、傳遞的）關(guān)系R2，若RÍR2，則R1ÍR2。R的自反、對(duì)稱和傳遞閉包分別記為r(R)、s(R)和t(R)。定理1 令RÍA´A，則 r(R)=RIA s(R)=RR-1 t(R)=RR2R3Warshall算法：設(shè)R是n個(gè)元素集合上的二元關(guān)系，M是R的關(guān)系矩陣；(1) 置新矩陣A:=M(2) 置i:=1；(3) for j=1 to n do if Aj,i=1 then do for k=1 to n do Aj,k:=Aj,k+Ai

8、,k(4) i=i+1；(5) if i<=n then to (3)(6) (7)(8)(9)(10)(11)(12)(13)(14)(15)(16)(17)(18)(19)(20)(21)(22)(23)(24)else stop本實(shí)驗(yàn)要求從鍵盤(pán)輸入一個(gè)關(guān)系的關(guān)系矩陣，計(jì)算其自反閉包、對(duì)稱閉包和傳遞閉包，計(jì)算傳遞閉包時(shí)使用Warshall算法。用C語(yǔ)言或MATLAB實(shí)現(xiàn)。3.實(shí)驗(yàn)步驟： 輸入一個(gè)3*3維矩陣 由r(R)=RIA；s(R)=RR-1；t(R)=RR2R3列出的算法計(jì)算自反、對(duì)稱、傳遞閉包并輸出。 本實(shí)驗(yàn)源程序力求簡(jiǎn)潔易懂，所以在設(shè)計(jì)時(shí)應(yīng)用簡(jiǎn)單的語(yǔ)句并省去了許多繁雜的選擇

9、，且每步均有注釋，使程序更清晰。但本實(shí)驗(yàn)在操作易于理解方面也有很大的體現(xiàn)。4.源程序：/*熟悉Warshall算法，掌握求關(guān)系的自反閉包、對(duì)稱閉包和傳遞閉包的方法令R AXA，則 r(R)=RIA s(R)=RR-1 t(R)=RR2R3*/#include<stdio.h>void main(void)int i,j,k;int I33=1,0,0,0,1,0,0,0,1;int a33,b33,c33;printf("請(qǐng)輸入3x3的二維矩陣：n");for(i=0;i<3;i+) /輸入矩陣for(j=0;j<3;j+)scanf("%

10、d",&aij);printf("自反閉包：n");for(i=0;i<3;i+) /自反閉包for(j=0;j<3;j+)bij=aij|Iij;printf("%3d",bij);printf("n");printf("對(duì)稱閉包：n");for(i=0;i<3;i+) /對(duì)稱閉包for(j=0;j<3;j+)cij=aij|aji;printf("%3d",cij);printf("n");printf("傳遞閉包：n&

11、quot;);for(i=0;i<3;i+) /傳遞閉包for(j=0;j<3;j+)if(aji=1)for(k=0;k<3;k+)ajk=ajk|aik;for(i=0;i<3;i+) /傳遞閉包的輸出for(j=0;j<3;j+)printf("%3d",aij);printf("n");5.實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)三 計(jì)算兩結(jié)點(diǎn)間長(zhǎng)度為m的路的數(shù)目1、實(shí)驗(yàn)?zāi)康?熟悉鄰接矩陣和兩結(jié)點(diǎn)間長(zhǎng)度為m的路的數(shù)目的關(guān)系并編程計(jì)算。2、實(shí)驗(yàn)內(nèi)容與要求定義7 給定簡(jiǎn)單圖G=<V，E>，V=v1，v2，vn，V中的結(jié)點(diǎn)按下標(biāo)由小到大

12、編序，則n階方陣A=(aij)稱為圖G的鄰接矩陣。其中 i，j=1，2，n。定理2 設(shè)A為簡(jiǎn)單圖G的鄰接矩陣，則Am中的i行j列元素amij等于G中聯(lián)結(jié)vi到vj的長(zhǎng)度為m的鏈(或路)的數(shù)目。本實(shí)驗(yàn)要求從鍵盤(pán)輸入圖的鄰接矩陣和一正整數(shù)m，計(jì)算結(jié)點(diǎn)兩兩之間長(zhǎng)度為m的路的數(shù)目?？紤]有向圖和無(wú)向圖。用C語(yǔ)言或MATLAB實(shí)現(xiàn)。3.實(shí)驗(yàn)步驟： 本實(shí)驗(yàn)在編寫(xiě)源程序時(shí)，對(duì)實(shí)驗(yàn)要求進(jìn)行了兩種方式的闡釋：一種是輸入關(guān)系矩陣及其階數(shù)，然后依次列出路長(zhǎng)度為1n的關(guān)系矩陣；另一種是輸入關(guān)系矩陣及其階數(shù)，然后指定路長(zhǎng)度的關(guān)系矩陣。本實(shí)驗(yàn)源程序力求簡(jiǎn)潔易懂，所以在設(shè)計(jì)時(shí)應(yīng)用簡(jiǎn)單的語(yǔ)句并省去了許多繁雜的選擇，且每步均有注

13、釋，使程序更清晰。但本實(shí)驗(yàn)在操作易于理解方面也有很大的體現(xiàn)。4.程序：（1）方法一：#include<iostream>/計(jì)算兩結(jié)點(diǎn)間長(zhǎng)度為m的路的數(shù)目using namespace std;int main()int i,j,k;int m,n,t;int a100100,b100100;int c100100;int s;cout<<"請(qǐng)輸入關(guān)系矩陣階數(shù)："<<endl;cin>>m;n=m;cout<<"請(qǐng)輸入關(guān)系矩陣："<<endl;for(i=0;i<m;i+)for

14、(j=0;j<m;j+)cin>>aij;cout<<"/*/"<<endl;for(i=0;i<m;i+)for(j=0;j<m;j+)bij=aij;cout<<"長(zhǎng)度為1的路的矩陣："<<endl;for(i=0;i<m;i+) /輸出長(zhǎng)度為1的路for(j=0;j<m;j+)cout<<bij<<" "cout<<endl;for(t=0;t<n-1;t+) /求長(zhǎng)度為2n的路cout<&l

15、t;"長(zhǎng)度為"<<t+2<<"的路的矩陣："<<endl;for(i=0;i<m;i+)for(j=0;j<m;j+)s=0;for(k=0;k<m;k+)s+=aik*bkj;cij=s;for(i=0;i<m;i+)for(j=0;j<m;j+)bij=cij;for(i=0;i<m;i+) /輸出長(zhǎng)度為2n的路for(j=0;j<m;j+)cout<<bij<<" "cout<<endl;return 0;運(yùn)行結(jié)果：

16、（2）方法二#include<iostream>/計(jì)算兩結(jié)點(diǎn)間長(zhǎng)度為m的路的數(shù)目using namespace std;int main()int i,j,k;int m,n,t;int a100100,b100100;int c100100;int s;cout<<"請(qǐng)輸入關(guān)系矩陣階數(shù)："<<endl;cin>>m;cout<<"請(qǐng)輸入路的長(zhǎng)度："<<endl;cin>>n;cout<<"請(qǐng)輸入關(guān)系矩陣："<<endl;for

17、(i=0;i<m;i+)for(j=0;j<m;j+)cin>>aij;cout<<"/*/"<<endl;for(i=0;i<m;i+)for(j=0;j<m;j+)bij=aij;cout<<"長(zhǎng)度為"<<n<<"的路的矩陣："<<endl;for(t=0;t<n-1;t+) /求長(zhǎng)度為n的路for(i=0;i<m;i+)for(j=0;j<m;j+)s=0;for(k=0;k<m;k+)s+=aik

18、*bkj;cij=s;for(i=0;i<m;i+)for(j=0;j<m;j+)bij=cij;for(i=0;i<m;i+) /輸出長(zhǎng)度為n的路for(j=0;j<m;j+)cout<<bij<<" "cout<<endl;return 0;5.運(yùn)行結(jié)果：實(shí)驗(yàn)四 最優(yōu)樹(shù)的構(gòu)造1、實(shí)驗(yàn)?zāi)康?熟悉最優(yōu)樹(shù)的構(gòu)造算法，掌握最優(yōu)樹(shù)的構(gòu)造過(guò)程。2、實(shí)驗(yàn)內(nèi)容與要求定義8 在權(quán)分別為w1，w2，wt的加權(quán)二叉樹(shù)T中，若權(quán)是wi的葉結(jié)點(diǎn)，其級(jí)為L(zhǎng)(wi)，則 稱為加權(quán)二叉樹(shù)T的權(quán)，并記為w(T)。已知w1，w2，wt為權(quán)，T0為

19、加權(quán)二叉樹(shù)，其權(quán)為w(T0)，如果對(duì)任意加權(quán)二叉樹(shù)T，它的權(quán)是w(T)，均有w(T0)w(T)，則稱T0是最優(yōu)樹(shù)或Huffman樹(shù)。定理3 設(shè)T為加權(quán)w1，w2，wt且w1w2wt的最優(yōu)樹(shù)，則(1) 加權(quán)w1和w2的葉結(jié)點(diǎn)vw1和vw2是兄弟。(2) 以葉結(jié)點(diǎn)vw1和vw2為兒子的分枝結(jié)點(diǎn)，它是所有分枝結(jié)點(diǎn)的級(jí)最高者。定理4 設(shè)T為加權(quán)w1，w2，wt且w1w2wt的最優(yōu)樹(shù)，若將以加權(quán)w1和w2的葉結(jié)點(diǎn)為兒子的分枝結(jié)點(diǎn)改為加權(quán)w1+w2的葉結(jié)點(diǎn)而得到一棵新樹(shù)T1，則T1是最優(yōu)樹(shù)。根據(jù)上述兩個(gè)定理，求一棵有t個(gè)權(quán)的最優(yōu)樹(shù)，可簡(jiǎn)化為求一棵有t-1個(gè)權(quán)的最優(yōu)樹(shù)，而這又可簡(jiǎn)化為求一棵有t-2個(gè)權(quán)的最優(yōu)樹(shù)，依此類推。具體作法是：首先找出兩個(gè)最小的權(quán)值，設(shè)w1和w2。然后對(duì)t-1個(gè)權(quán)w1+w2，w3，wt求作一棵最優(yōu)樹(shù)，并且將這棵樹(shù)中的結(jié)w1+w2代之以w1 w2，依此類推。本實(shí)驗(yàn)要求從鍵盤(pán)輸入一組權(quán)值，構(gòu)造出對(duì)應(yīng)的最優(yōu)樹(shù)，列出構(gòu)造過(guò)程。用C語(yǔ)言或MATLAB實(shí)現(xiàn)。3.實(shí)驗(yàn)步驟： 本實(shí)驗(yàn)要求先輸入葉子節(jié)點(diǎn)的個(gè)數(shù)，然后輸入其權(quán)值，最后根據(jù)冒泡法排序并使最小的兩數(shù)相加，最后輸出最優(yōu)樹(shù)的構(gòu)造過(guò)程。本實(shí)驗(yàn)源程序力求簡(jiǎn)潔易懂，所以在設(shè)計(jì)時(shí)應(yīng)用簡(jiǎn)單的語(yǔ)句并省去了許多繁雜的選擇，且每步均有注釋，使程序更清晰。但本實(shí)驗(yàn)在操作易于理解方面也有很大的體現(xiàn)。4.程序：#include<iostream&g