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

1、實(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)用上面定義的函數(shù)，將5人表決開(kāi)

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

3、&d|b&&c&&e|b&&d&&e|c&&d&&e）return1;elsereturn0;voidmain（）inta,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（"很好，表決通過(guò)！n"）;elseprintf（"遺憾，表決

4、沒(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é)論，得一個(gè)復(fù)合命題。(2)將復(fù)合命題中要用到的聯(lián)結(jié)詞定義成C語(yǔ)言中的函數(shù)，用變量表示相應(yīng)的命題變?cè)?。將?fù)

5、合命題寫(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ǔ)言算法：intA,B,C,D,E;for(A=0;A<=1;A+)for(B=0;B<=1;B+)for(C=0;C<=1;C+)for(

6、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)用數(shù)組A,B,C,E表示集合。輸入數(shù)組A,B,E(全集)，輸入數(shù)據(jù)時(shí)要求檢查數(shù)據(jù)是否重復(fù)(集合中的數(shù)據(jù)要求不重復(fù))，要求集合A，B是集合

7、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ǔ)言算法：for(i=0;i<m;i+)ci=ai;for(i=0;i<n;i+)for(j=0;j<m;j+)if(bi=

8、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;(5)集合的補(bǔ)運(yùn)算：將數(shù)組E中的元素逐一與數(shù)組A中的元素進(jìn)行比較，把不相同的元素保存到數(shù)組C中，數(shù)組C便是集合A關(guān)于集合E的補(bǔ)集。求補(bǔ)集是一種

9、種特殊的集合差運(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è)nXn關(guān)系矩陣R=(j)nn表示，定義一個(gè)nxn數(shù)組rnn表示nxn矩陣關(guān)系。(2)若R對(duì)角線上的元素都是1，則R具有自反性。C語(yǔ)言算法：inti,flag=1;for(i=0;i<N&&flag;i+)if(rii!=1)flag=0;如果flag=1,則R是自反

10、關(guān)系(3)若R是對(duì)稱矩陣，則R具有對(duì)稱性。對(duì)稱矩陣的判斷方法是：%R,有rjiR。C語(yǔ)言算法：inti,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,若"1且rjk1有限1。C語(yǔ)言算法：inti,j,k,flag=1;for(i=0;i<N&&flag;i+)for(j=0;j<N&&flag;j+)f

11、or(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ǔ)言算法：inti,j,flag=1;intaN;for(i=0;i<N;i+)ai=i+1;/*i代表第i個(gè)元素*/for(i=0;i<N;i+)if(ai)printf("");for(j=0;j<N;j+)if(rij&&aj!=0)*/printf(&quo

12、t;%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)自反閉包：r(R)RIA。C語(yǔ)言算法：將關(guān)系矩陣的對(duì)角線上所有元素設(shè)為1。initc(r);/*將關(guān)系矩陣的對(duì)角線上所有元素設(shè)為1*/for(i=0;i<N;i+)cii=1;(2)對(duì)稱閉包：s(R)RRC語(yǔ)言算法：在關(guān)系矩陣的基礎(chǔ)上

13、，若rj1,令rji1。initc(r);for(i=0;i<N;i+)for(j=0;j<N;j+)if(cij)cji=1;/*將關(guān)系矩陣的對(duì)角線上所有元素設(shè)為1*/(3)傳遞閉包：t(R)RR2Rn，或用warshall方法。方法1：t(R)RR2Rn，下面求得的關(guān)系矩陣T=(bij)nn就是t(R)。intbNN;initc(r);/*用c裝好r*/for(m=1;m<N;m+)/*得r的m次方，用c裝好*/for(i=0;i<N;i+)for(j=0;j<N;j+)bij=0;for(k=0;k<N;k+)bij+=cik*rkj;if(bij)b

14、ij=1;initc(b);/*把r的m次方b賦名Cc保存*/方法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=(j)nn表示圖。(2)對(duì)無(wú)向圖而言，若所有結(jié)點(diǎn)的度都是偶數(shù)，則該圖為歐拉圖。C語(yǔ)言算法：flag=1;for(i=1;i<=n&&f

15、lag;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|sum2%2=0)flag=0;如果flag該有向圖是歐拉圖(4)求出歐拉路的方法：歐拉路經(jīng)過(guò)每條邊一次且僅一次。

16、可用回溯的方法求得所有歐拉路。C語(yǔ)言算法：intcount=0,cur=0,rNN;/rNN為圖的鄰接矩陣，cur為當(dāng)前結(jié)點(diǎn)編號(hào)，count為歐拉路的數(shù)量。intsequenceM;/sequence保留訪問(wèn)點(diǎn)的序列，M為圖的邊數(shù)輸入圖信息;void try1(int k) /k表示邊的序號(hào)inti,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)連通/刪除當(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);

17、/試下一個(gè)點(diǎn)elseprt1();/經(jīng)過(guò)了所有邊，打印一個(gè)解/上面條件不滿足，說(shuō)明當(dāng)前點(diǎn)的出度為0，回溯，試下一位置rprei=1;cur=pre;最優(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)二叉樹(shù)，輸出前綴碼時(shí)可用樹(shù)的遍歷方法。#include<stdio.h>#include<stdlib.h>#defineN13structtree

18、floatnum;structtree*Lnode;structtree*Rnode;*fpN;/保存結(jié)點(diǎn)chars2*N;/放前綴碼voidinite_node(floatf,intn)/生成葉子結(jié)點(diǎn)inti;structtree*pt;for(i=0;i<n;i+)pt=(structtree*)malloc(sizeof(structtree);/生成葉子結(jié)點(diǎn)pt->num=fi;pt->Lnode=NULL;pt->Rnode=NULL;fpi=pt;voidsort(structtree*array,intn)/將第N-n個(gè)點(diǎn)插入到已排好序的序列中。inti;

19、structtree*temp;for(i=N-n;i<N-1;i+)if(arrayi->num>arrayi+1->num)temp=arrayi+1;arrayi+1=arrayi;arrayi=temp;structtree*construct_tree(floatf,intn)/建立樹(shù)inti;structtree*pt;for(i=1;i<N;i+)pt=(structtree*)malloc(sizeof(structtree);/生成非葉子結(jié)點(diǎn)pt->num=fpi-1->num+fpi->num;pt->Lnode=fpi

20、-1;pt->Rnode=fpi;fpi=pt;/w1+w2sort(fp,N-i);returnfpN-1;voidpreorder(structtree*p,intk,charc)intj;if(p!=NULL)if(c='l')sk='0'elsesk='1'if(p->Lnode=NULL)/P指向葉子printf("%.2f:",p->num);for(j=0;j<=k;j+)printf("%c",sj);putchar('n');preorder(p-&

21、gt;Lnode,k+1,'l');preorder(p->Rnode,k+1,'r');voidmain()floatfN=2,3,5,7,11,13,17,19,23,29,31,37,41;structtree*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)