離散數(shù)學(xué)實(shí)驗(yàn)指導(dǎo)書(shū)及其答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)一 命題邏輯公式化簡(jiǎn)【實(shí)驗(yàn)?zāi)康摹考由顚?duì)五個(gè)基本聯(lián)結(jié)詞（否定、合取、析取、條件、雙條件）的理解、掌握利用基本等價(jià)公式化簡(jiǎn)公式的方法?！緦?shí)驗(yàn)內(nèi)容】用化簡(jiǎn)命題邏輯公式的方法設(shè)計(jì)一個(gè)表決開(kāi)關(guān)電路。實(shí)驗(yàn)用例：用化簡(jiǎn)命題邏輯公式的方法設(shè)計(jì)一個(gè)5人表決開(kāi)關(guān)電路，要求3人以上（含3人）同意則表決通過(guò)（表決開(kāi)關(guān)亮）。【實(shí)驗(yàn)原理和方法】（1）寫(xiě)出5人表決開(kāi)關(guān)電路真值表，從真值表得出5人表決開(kāi)關(guān)電路的主合取公式（或主析取公式），將公式化簡(jiǎn)成盡可能含五個(gè)基本聯(lián)結(jié)詞最少的等價(jià)公式。（2）上面公式中的每一個(gè)聯(lián)結(jié)詞是一個(gè)開(kāi)關(guān)元件，將它們定義成C語(yǔ)言中的函數(shù)。（3）輸入5人表決值（0或1），調(diào)用

2、上面定義的函數(shù)，將5人表決開(kāi)關(guān)電路真值表的等價(jià)公式寫(xiě)成一個(gè)函數(shù)表達(dá)式。（4）輸出函數(shù)表達(dá)式的結(jié)果，如果是1，則表明表決通過(guò)，否則表決不通過(guò)。參考代碼：#include<stdio.h>int vote(int a,int b,int c,int d,int e)/五人中任取三人的不同的取法有10種。if( a&&b&&c | a&&b&&d | a&&b&&e | a&&c&&d | a&&c&&e | a&&

3、;d&&e | b&&c&&d | b&&c&&e | b&&d&&e | c&&d&&e)return 1;else return 0;void main()int a,b,c,d,e;printf("請(qǐng)輸入第五個(gè)人的表決值（0或1，空格分開(kāi)）：");scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);if(vote(a,b,c,d,e) printf(

4、"很好，表決通過(guò)！n");elseprintf("遺憾，表決沒(méi)有通過(guò)！n");/注：聯(lián)結(jié)詞不定義成函數(shù)，否則太繁實(shí)驗(yàn)二 命題邏輯推理【實(shí)驗(yàn)?zāi)康摹考由顚?duì)命題邏輯推理方法的理解?！緦?shí)驗(yàn)內(nèi)容】用命題邏輯推理的方法解決邏輯推理問(wèn)題。實(shí)驗(yàn)用例：根據(jù)下面的命題，試用邏輯推理方法確定誰(shuí)是作案者，寫(xiě)出推理過(guò)程。（1）營(yíng)業(yè)員A或B偷了手表； （2）若A作案，則作案不在營(yíng)業(yè)時(shí)間； （3）若B提供的證據(jù)正確，則貨柜末上鎖； （4）若B提供的證據(jù)不正確，則作案發(fā)生在營(yíng)業(yè)時(shí)間； （5）貨柜上了鎖。 【實(shí)驗(yàn)原理和方法】（1）符號(hào)化上面的命題，將它們作為條件，營(yíng)業(yè)員A偷了手表作為結(jié)論

5、，得一個(gè)復(fù)合命題。（2）將復(fù)合命題中要用到的聯(lián)結(jié)詞定義成C語(yǔ)言中的函數(shù)，用變量表示相應(yīng)的命題變?cè)?。將?fù)合命題寫(xiě)成一個(gè)函數(shù)表達(dá)式。（3）函數(shù)表達(dá)式中的變量賦初值1。如果函數(shù)表達(dá)式的值為1，則結(jié)論有效， A偷了手表，否則是B偷了手表。用命題題變?cè)硎荆篈:營(yíng)業(yè)員A偷了手表B:營(yíng)業(yè)員B偷了手表C:作案不在營(yíng)業(yè)時(shí)間D:B提供的證據(jù)正確E:貨柜末上鎖則上面的命題符號(hào)化為 (A|B) && (!A|C) && (!D|E) && (D|!C) && !E要求找到滿足上面式子的變?cè)狝，B的指派便是結(jié)果。C語(yǔ)言算法：int A,B,C,D,E;f

6、or(A=0;A<=1;A+)for(B=0;B<=1;B+)for(C=0;C<=1;C+)for(D=0;D<=1;D+)for(E=0;E<=1;E+)if(A|B) && (!A|C) && (!D|E) && (D|!C) && !E)printf("A=%d,B=%dn",A,B);/*實(shí)驗(yàn)結(jié)果是：A=0，B=1，即B偷了手表*/實(shí)驗(yàn)三 集合運(yùn)算【實(shí)驗(yàn)?zāi)康摹空莆沼糜?jì)算機(jī)求集合的交、并、差和補(bǔ)運(yùn)算的方法?！緦?shí)驗(yàn)內(nèi)容】編程實(shí)現(xiàn)集合的交、并、差和補(bǔ)運(yùn)算?！緦?shí)驗(yàn)原理和方法】（1

7、）用數(shù)組A，B，C，E表示集合。輸入數(shù)組A，B，E（全集），輸入數(shù)據(jù)時(shí)要求檢查數(shù)據(jù)是否重復(fù)（集合中的數(shù)據(jù)要求不重復(fù)），要求集合A，B是集合E的子集。以下每一個(gè)運(yùn)算都要求先將集合C置成空集。（2）二個(gè)集合的交運(yùn)算：把數(shù)組A中元素逐一與數(shù)組B中的元素進(jìn)行比較，將相同的元素放在數(shù)組C中，數(shù)組C便是集合A和集合B的交。C語(yǔ)言算法：for(i=0;i<m;i+)for(j=0;j<n;j+)if(ai=bj) ck+=ai;（3）二個(gè)集合的并運(yùn)算：把數(shù)組A中各個(gè)元素先保存在數(shù)組C中。將數(shù)組B中的元素逐一與數(shù)組B中的元素進(jìn)行比較，把不相同的元素添加到數(shù)組C中，數(shù)組C便是集合A和集合B的并。C語(yǔ)

8、言算法：for(i=0;i<m;i+)ci=ai;for(i=0;i<n;i+)for(j=0;j<m;j+)if(bi=cj) break;if(j=m) cm+k=bi;k+;（4）二個(gè)集合的差運(yùn)算：把數(shù)組A中各個(gè)元素先保存在數(shù)組C中。將數(shù)組B中的元素逐一與數(shù)組B中的元素進(jìn)行比較，把相同的元素從數(shù)組C中刪除，數(shù)組C便是集合A和集合B的差A(yù)-B。C語(yǔ)言算法：for(i=0;i<m;i+)ci=ai;for(i=0;i<n;i+)for(j=0;j<m;j+)if(bi=cj)for(k=j;k<m;k+)ck=ck+1;/*移位*/m-;break;

9、（5）集合的補(bǔ)運(yùn)算：將數(shù)組E中的元素逐一與數(shù)組A中的元素進(jìn)行比較，把不相同的元素保存到數(shù)組C中，數(shù)組C便是集合A關(guān)于集合E的補(bǔ)集。求補(bǔ)集是一種種特殊的集合差運(yùn)算。實(shí)驗(yàn)四 二元關(guān)系及其性質(zhì)【實(shí)驗(yàn)?zāi)康摹空莆斩P(guān)系在計(jì)算機(jī)上的表示方法，并掌握如果判定關(guān)系的性質(zhì)?！緦?shí)驗(yàn)內(nèi)容】 編程判斷一個(gè)二元關(guān)系是否為等價(jià)關(guān)系，如果是，求其商集。等價(jià)關(guān)系：集合A上的二元關(guān)系R同時(shí)具有自反性、對(duì)稱性和傳遞性，則稱R是A上的等價(jià)關(guān)系?！緦?shí)驗(yàn)原理和方法】（1）A上的二元關(guān)系用一個(gè)n×n關(guān)系矩陣R=表示，定義一個(gè)n×n數(shù)組rnn表示n×n矩陣關(guān)系。（2）若R對(duì)角線上的元素都是1，則R具有自反性

10、。C語(yǔ)言算法：int i,flag=1;for(i=0;i<N && flag ;i+)if(rii!=1) flag=0;如果flag=1， 則R是自反關(guān)系（3）若R是對(duì)稱矩陣，則R具有對(duì)稱性。對(duì)稱矩陣的判斷方法是：。C語(yǔ)言算法：int i,j,flag=1;for(i=0;i<N && flag ;i+)for(j=i+1;j<N && flag;j+) if(rij &&rji!=1) flag=0;如果flag=1， 則R是對(duì)稱關(guān)系（4）關(guān)系的傳遞性判斷方法：對(duì)任意i，j，k，若。C語(yǔ)言算法：int i,

11、j,k,flag=1;for(i=0;i<N && flag;i+)for(j=0;j<N && flag;j+)for(k=0;k<N && flag;k+)if(rij &&rjk && rik!=1) flag=0;如果flag=1， 則R是傳遞關(guān)系（5）求商集的方法：商集是由等價(jià)類組成的集合。已知R是等價(jià)關(guān)系，下面的算法是把等價(jià)類分行打印出來(lái)。C語(yǔ)言算法： int i,j,flag=1;int aN;for(i=0;i<N;i+)ai=i+1;/*i代表第i個(gè)元素*/for(i=0;

12、i<N;i+)if(ai)printf(" ");for(j=0;j<N;j+)if(rij && aj!=0) printf("%d ",aj);/*打印和第i個(gè)元素有關(guān)系的所有元素*/aj=0;printf("n");實(shí)驗(yàn)五 關(guān)系閉包運(yùn)算【實(shí)驗(yàn)?zāi)康摹空莆涨箨P(guān)系閉包的方法?！緦?shí)驗(yàn)內(nèi)容】編程求一個(gè)關(guān)系的閉包，要求傳遞閉包用warshall方法?！緦?shí)驗(yàn)原理和方法】設(shè)N元關(guān)元系用rNN表示，cNN表示各個(gè)閉包，函數(shù)initc(r)表示將cNN初始化為rNN。（1）自反閉包：。C語(yǔ)言算法： 將關(guān)系矩陣的對(duì)角線上所

13、有元素設(shè)為1。initc(r);/*將關(guān)系矩陣的對(duì)角線上所有元素設(shè)為1*/for(i=0;i<N;i+)cii=1;（2）對(duì)稱閉包：C語(yǔ)言算法： 在關(guān)系矩陣的基礎(chǔ)上，若。initc(r);for(i=0;i<N;i+)for(j=0;j<N;j+)if(cij) cji=1;/*將關(guān)系矩陣的對(duì)角線上所有元素設(shè)為1*/（3）傳遞閉包：，或用warshall方法。方法1：，下面求得的關(guān)系矩陣T=就是。int bNN;initc(r);/*用c裝好r*/for(m=1;m<N;m+) /*得r的m次方,用c裝好*/for(i=0;i<N;i+)for(j=0;j<

14、N;j+)bij=0;for(k=0;k<N;k+)bij+=cik*rkj;if(bij) bij=1;initc(b);/*把r的m次方b賦給c保存*/方法2：warshall方法initc(r);/*用c裝好r*/for(i=0;i<N;i+)for(j=0;j<N;j+)if(cji)for(k=0;k<N;k+)cjk=cjk+cik;if(cjk) cjk=1;實(shí)驗(yàn)六 歐拉圖判定和應(yīng)用【實(shí)驗(yàn)?zāi)康摹空莆张袛鄽W拉圖的方法?！緦?shí)驗(yàn)內(nèi)容】 判斷一個(gè)圖是不是，如果是，求出所有歐拉路【實(shí)驗(yàn)原理和方法】（1）用關(guān)系矩陣R=表示圖。（2）對(duì)無(wú)向圖而言，若所有結(jié)點(diǎn)的度都是偶數(shù)

15、，則該圖為歐拉圖。C語(yǔ)言算法：flag=1;for(i=1;i<=n && flag;i+)sum=0;for(j=1;j<=n;j+)if(rij) sum+;if(sum%2=0) flag=0;如果 flag 該無(wú)向圖是歐拉圖（3）對(duì)有向圖而言，若所有結(jié)點(diǎn)的入度等于出度，則該圖為歐拉圖。C語(yǔ)言算法：flag=1;for(i=1;i<=n && flag;i+)sum1=0;sum2=0;for(j=1;j<=n;j+)if(rij) sum1+;for(j=1;j<=n;j+)if(rji) sum2+;if(sum1%2=0

16、 | sum2%2=0) flag=0;如果 flag 該有向圖是歐拉圖（4）求出歐拉路的方法：歐拉路經(jīng)過(guò)每條邊一次且僅一次?？捎没厮莸姆椒ㄇ蟮盟袣W拉路。C語(yǔ)言算法：int count=0,cur=0,rNN; / rNN為圖的鄰接矩陣，cur為當(dāng)前結(jié)點(diǎn)編號(hào)，count為歐拉路的數(shù)量。int sequenceM;/ sequence保留訪問(wèn)點(diǎn)的序列，M為圖的邊數(shù)輸入圖信息;void try1(int k) /k表示邊的序號(hào)int i,pre=cur; /j保留前一個(gè)點(diǎn)的位置,pre為前一結(jié)點(diǎn)的編號(hào)for (i=0;i<N;i+) if (rcuri) /當(dāng)前第cur點(diǎn)到第i點(diǎn)連通 /刪

17、除當(dāng)前點(diǎn)與第i點(diǎn)的邊，記下第k次到達(dá)點(diǎn)i，把第i個(gè)點(diǎn)設(shè)為當(dāng)前點(diǎn)rcuri=0;cur=sequencek=i; if (k<M) try1(k+1); /試下一個(gè)點(diǎn)else prt1();/經(jīng)過(guò)了所有邊，打印一個(gè)解/上面條件不滿足，說(shuō)明當(dāng)前點(diǎn)的出度為0，回溯，試下一位置rprei=1;cur=pre; 實(shí)驗(yàn)七 最優(yōu)二叉樹(shù)的應(yīng)用【實(shí)驗(yàn)?zāi)康摹空莆涨笞顑?yōu)二叉樹(shù)的方法?！緦?shí)驗(yàn)內(nèi)容】最優(yōu)二叉樹(shù)在通信編碼中的應(yīng)用。要求輸入一組通信符號(hào)的使用頻率，求各通信符號(hào)對(duì)應(yīng)的前綴碼?！緦?shí)驗(yàn)原理和方法】（1）用一維數(shù)組fN存貯通信符號(hào)的使用頻率，用求最優(yōu)二叉樹(shù)的方法求得每個(gè)通信符號(hào)的前綴碼。（2）用鏈表保存最優(yōu)二

18、叉樹(shù)，輸出前綴碼時(shí)可用樹(shù)的遍歷方法。#include <stdio.h>#include <stdlib.h>#define N 13struct tree float num;struct tree *Lnode;struct tree *Rnode;* fpN;/保存結(jié)點(diǎn)char s2*N;/放前綴碼void inite_node(float f,int n)/生成葉子結(jié)點(diǎn)int i;struct tree *pt;for(i=0;i<n;i+)pt=(struct tree *)malloc(sizeof(struct tree);/生成葉子結(jié)點(diǎn)pt->

19、;num=fi;pt->Lnode=NULL;pt->Rnode=NULL;fpi=pt;void sort(struct tree * array,int n)/將第N-n個(gè)點(diǎn)插入到已排好序的序列中。int i;struct tree *temp;for(i=N-n;i<N-1;i+)if(arrayi->num>arrayi+1->num)temp=arrayi+1;arrayi+1=arrayi;arrayi=temp;struct tree * construct_tree(float f,int n)/建立樹(shù)int i;struct tree *p

20、t;for(i=1;i<N;i+)pt=(struct tree *)malloc(sizeof(struct tree);/生成非葉子結(jié)點(diǎn)pt->num=fpi-1->num+fpi->num;pt->Lnode=fpi-1;pt->Rnode=fpi;fpi=pt;/w1+w2sort(fp,N-i);return fpN-1;void preorder(struct tree *p,int k,char c) int j;if(p!=NULL) if(c='l') sk='0'else sk='1'if(

21、p->Lnode=NULL) /P指向葉子printf("%.2f: ",p->num);for(j=0;j<=k;j+)printf("%c",sj);putchar('n');preorder(p->Lnode,k+1,'l');preorder(p->Rnode,k+1,'r');void main()float fN=2,3,5,7,11,13,17,19,23,29,31,37,41;struct tree *head;inite_node(f,N); /初始化結(jié)點(diǎn)head=construct_tree(f,N);/生成最優(yōu)樹(shù)s0=0;preorder(head,0,'l');/遍歷樹(shù)實(shí)驗(yàn)八 群的判定【實(shí)驗(yàn)?zāi)康摹空莆杖旱呐卸ǚ椒ā！緦?shí)驗(yàn)內(nèi)容】輸入代數(shù)系統(tǒng)(A,*)的集合A和*運(yùn)算的運(yùn)算表，判斷(A，*)是否是群?！緦?shí)驗(yàn)原理和方法】（1）用一維數(shù)組an存貯集合A。（2）用二維數(shù)組opnn存貯運(yùn)算表。（3）根據(jù)群的定義，代數(shù)系統(tǒng)(A，*)若為群，除運(yùn)算表已表明運(yùn)算*封閉