離散數(shù)學(xué)實(shí)驗(yàn)指導(dǎo)書(shū)_第1頁(yè)
離散數(shù)學(xué)實(shí)驗(yàn)指導(dǎo)書(shū)_第2頁(yè)
離散數(shù)學(xué)實(shí)驗(yàn)指導(dǎo)書(shū)_第3頁(yè)
離散數(shù)學(xué)實(shí)驗(yàn)指導(dǎo)書(shū)_第4頁(yè)
離散數(shù)學(xué)實(shí)驗(yàn)指導(dǎo)書(shū)_第5頁(yè)
已閱讀5頁(yè),還剩3頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

《離散數(shù)學(xué)》試驗(yàn)指導(dǎo)一試驗(yàn)課任務(wù)、性質(zhì)與目本試驗(yàn)課程是信息專業(yè)學(xué)生一門專業(yè)基礎(chǔ)課程,經(jīng)過(guò)試驗(yàn),幫助學(xué)生愈加好地掌握計(jì)算機(jī)科學(xué)技術(shù)常見(jiàn)離散數(shù)學(xué)中概念、性質(zhì)和運(yùn)算;經(jīng)過(guò)試驗(yàn)提升學(xué)生編寫(xiě)試驗(yàn)匯報(bào)、總結(jié)試驗(yàn)結(jié)果能力;使學(xué)生含有程序設(shè)計(jì)思想,能夠獨(dú)立完成簡(jiǎn)單算法設(shè)計(jì)和分析。二試驗(yàn)?zāi)繕?biāo)1.掌握離散數(shù)學(xué)中包含相關(guān)概念。2.培養(yǎng)學(xué)生邏輯思維能力和算法設(shè)計(jì)思想。3.熟練掌握C/C++語(yǔ)言程序設(shè)計(jì)基礎(chǔ)方法和多種調(diào)試手段。4.熟練掌握包含數(shù)組、鏈表以及鄰接表或鄰接矩陣等數(shù)據(jù)結(jié)構(gòu)建立和利用。5.經(jīng)過(guò)試驗(yàn)掌握遞歸程序設(shè)計(jì)基礎(chǔ)方法。6.掌握?qǐng)D存放和遍歷方法。三試驗(yàn)要求試驗(yàn)前,復(fù)習(xí)《離散數(shù)學(xué)》課程中相關(guān)內(nèi)容。上機(jī)前編好程序,上機(jī)時(shí)調(diào)試。編程要獨(dú)立完成,程序應(yīng)加合適注釋。完成試驗(yàn)匯報(bào)。四試驗(yàn)匯報(bào)要求“離散數(shù)學(xué)”試驗(yàn)匯報(bào)專業(yè)班級(jí)學(xué)號(hào)姓名日期封面:如右圖文字用小4號(hào)或4號(hào);程序和注釋用5號(hào)以班為單位交.試驗(yàn)匯報(bào)文件名:080x姓名學(xué)號(hào)(試驗(yàn)xA/B/C)試驗(yàn)匯報(bào)上交時(shí)間:做完試驗(yàn)后一到兩周內(nèi),在課間拷貝到教室機(jī)器指定目錄中。試驗(yàn)一一試驗(yàn)內(nèi)容(二選一) 1.從鍵盤輸入兩個(gè)命題變?cè)狿和Q真值,求它們合取、析取、條件和雙條件真值。(A) 2.求任意一個(gè)命題公式真值表(B,并依據(jù)真值表求主范式(C))注意:題目類型分為A,B,C三類,其中A為基礎(chǔ)題,完成A類題目可達(dá)成設(shè)計(jì)基礎(chǔ)要求,其她均為加分題,并按字母次序分?jǐn)?shù)增加越高。二試驗(yàn)?zāi)?熟悉掌握命題邏輯中聯(lián)接詞、真值表、主范式等,深入能用它們來(lái)處理實(shí)際問(wèn)題。三試驗(yàn)環(huán)境C或C++語(yǔ)言編程環(huán)境實(shí)現(xiàn)。四試驗(yàn)說(shuō)明 1.邏輯聯(lián)接詞運(yùn)算本試驗(yàn)要求大家利用C/C++語(yǔ)言,實(shí)現(xiàn)二元合取、析取、條件和雙條件表示式計(jì)算。充足利用聯(lián)接詞和邏輯運(yùn)算符之間相同性實(shí)現(xiàn)程序功效。 2.求任意一個(gè)命題公式真值表本試驗(yàn)要求大家利用C/C++語(yǔ)言,實(shí)現(xiàn)任意輸入公式真值表計(jì)算。通常我們將公式中命題變?cè)旁谡嬷当碜筮?將公式結(jié)果放在真值表右邊。命題變?cè)捎脭?shù)值變量表示,適宜公式表示及求真值表轉(zhuǎn)化為邏輯運(yùn)算結(jié)果;可用一維數(shù)表示合式公式中所出現(xiàn)n個(gè)命題變?cè)?同時(shí)它也是一個(gè)二進(jìn)制加法器模擬器,每當(dāng)在這個(gè)模擬器中產(chǎn)生一個(gè)二進(jìn)制數(shù)時(shí),就相當(dāng)于給各個(gè)命題變?cè)a(chǎn)生了一組真值指派。算法邏輯以下:(1)將二進(jìn)制加法模擬器賦初值0(2)計(jì)算模擬器中所對(duì)應(yīng)一組真值指派下合式公式真值。(3)輸出真值表中對(duì)應(yīng)于模擬器所給出一組真值指派及這組真值指派所對(duì)應(yīng)一行真值。(4)產(chǎn)生下一個(gè)二進(jìn)制數(shù)值,若該數(shù)值等于2n-1,則結(jié)束,不然轉(zhuǎn)(2)。注意,在進(jìn)行表示式求值時(shí)候,可先將帶括號(hào)中綴表示式利用棧結(jié)構(gòu)轉(zhuǎn)換為不帶括號(hào)后綴表示式(逆波蘭式),然后進(jìn)行計(jì)算。具體方法請(qǐng)參考數(shù)據(jù)結(jié)構(gòu)中相關(guān)“棧”知識(shí)。五試驗(yàn)要求在試驗(yàn)匯報(bào)中要寫(xiě)下列內(nèi)容:1.試驗(yàn)?zāi)?2.試驗(yàn)內(nèi)容;3.試驗(yàn)環(huán)境;4.試驗(yàn)原理和實(shí)現(xiàn)過(guò)程(算法描述);5.試驗(yàn)數(shù)據(jù)及結(jié)果分析;6.源程序清單;7.其她收獲和體會(huì)。注意:程序需含有基礎(chǔ)容錯(cuò)控制,在輸入錯(cuò)誤時(shí)有處理手段;程序界面友好,需要輸入地方有輸入說(shuō)明,說(shuō)明輸入內(nèi)容和格式要求等;試驗(yàn)原理和實(shí)現(xiàn)過(guò)程應(yīng)該具體分析問(wèn)題,給出處理思緒,描述算法思想,不能用源程序替換算法;測(cè)試數(shù)據(jù)應(yīng)全方面,包含非法輸入處理結(jié)果等都應(yīng)包含在內(nèi)

試驗(yàn)二一試驗(yàn)內(nèi)容(三選一)1.求有限集上給定關(guān)系自反、對(duì)稱和傳輸閉包。(有兩種求解方法,只做一個(gè)為A,兩種都做為B)2.求有限集上等價(jià)關(guān)系數(shù)目。(有兩種求解方法,只做一個(gè)為A,兩種都做為B)3.求解商集,輸入集合和等價(jià)關(guān)系,求對(duì)應(yīng)商集。(C)注意:題目類型分為A,B,C三類,其中A為基礎(chǔ)題,完成A類題目可達(dá)成設(shè)計(jì)基礎(chǔ)要求,其她均為加分題,并按字母次序分?jǐn)?shù)增加越高。二試驗(yàn)?zāi)空莆贞P(guān)系概念與性質(zhì),基礎(chǔ)關(guān)系運(yùn)算,關(guān)系多種閉包求法。了解等價(jià)類概念,掌握等價(jià)類求解方法。三試驗(yàn)環(huán)境C或C++語(yǔ)言編程環(huán)境實(shí)現(xiàn)。四試驗(yàn)說(shuō)明1.求有限集上等價(jià)關(guān)系數(shù)目。集合上等價(jià)關(guān)系與該集合劃分之間存在一一對(duì)應(yīng)關(guān)系。一個(gè)等價(jià)關(guān)系對(duì)應(yīng)一個(gè)劃分,一個(gè)劃分也對(duì)應(yīng)一個(gè)等價(jià)關(guān)系。我們把n個(gè)元素集合劃分成k塊方法數(shù)叫第二類Stirling數(shù),表示為S(n,k)。比如有甲、乙、丙、丁四人,若全部些人分成1組,只有全部些人在同一組這個(gè)方法,所以S(4,1)=1;若全部些人分成4組,只能夠人人獨(dú)立一組,所以S(4,4)=1;若分成2組,能夠是甲乙一組、丙丁一組,或甲丙一組、乙丁一組,或甲丁一組、乙丙一組,或其中三人同一組另一人獨(dú)立一組,即是:{A,B},{C,D}{A,C},{B,D}{A,D},{B,C}{A},{B,C,D}{B},{A,C,D}{C},{A,B,D}{D},{A,B,C}所以S(4,2)=7。給定S(n,n)=S(n,1)=1,有遞歸關(guān)系S(n,k)=S(n?1,k?1)+kS(n?1,k)上面遞推式能夠用組合證實(shí):首先,假如將元素1單獨(dú)拿出來(lái)劃分成1個(gè)集合,那么方法數(shù)是S(n-1,k-1);其次,假如元素1所在集合不止一個(gè)元素,那么能夠先將剩下n-1個(gè)元素劃分好了以后再選一個(gè)集合把1放進(jìn)去,方法數(shù)是k*S(n-1,k);有加法原理得證。第二類Stirling數(shù)可用遞推和遞歸兩種方法求解。集合上全部等價(jià)類個(gè)數(shù)即為k從1到n,全部S(n,k)之和。 2.求有限集上給定關(guān)系自反、對(duì)稱和傳輸閉包。關(guān)系采取關(guān)系矩陣形式表示會(huì)比較輕易處理。自反閉包和對(duì)稱閉包求法比較簡(jiǎn)單,傳輸閉包有兩種方法求解。一個(gè)直接經(jīng)過(guò)定義,另一個(gè)稱為Warshall算法。Warshall算法:設(shè)R關(guān)系矩陣為M(1)令矩陣A=M(2)置i=1(3)對(duì)全部j,若A[j,i]=1,則對(duì)于k=1,2,…,n,令A(yù)[j,k]=A[j,k]+A[i,k](4)i=i+l.(5)若i≤n,則轉(zhuǎn)到(3),不然結(jié)束。3.求解商集,輸入集合和等價(jià)關(guān)系,求對(duì)應(yīng)商集商集即等價(jià)類組成集合,要求商集,首先需要判定輸入關(guān)系是否為等價(jià)關(guān)系,不然沒(méi)有商集。確定集合A={a1,a2,a3,…,an}相關(guān)R等價(jià)類算法以下:(1)令A(yù)中每一個(gè)元素自成一個(gè)子集,如A1={a1},A2={a2},…,An={an}(2)對(duì)R中每個(gè)二元組<x,y>,判定x和y所屬子集。假設(shè)x屬于Ai,y屬于Aj,若Ai<>Aj,則將Ai并入Aj,并置Ai為空;或?qū)j并入Ai,并置Aj為空。通常將元素少集合合并到元素多集合。(3)A1,A2,…,An中全部非空子集組成集合即為所求商集。要實(shí)現(xiàn)集合并運(yùn)算,采取并查集(union-findsets)是一個(gè)不錯(cuò)方法。并查集是一個(gè)樹(shù)型數(shù)據(jù)結(jié)構(gòu),多棵樹(shù)組成一個(gè)森林,每棵樹(shù)組成一個(gè)集合,樹(shù)中每個(gè)節(jié)點(diǎn)就是該集合元素,找一個(gè)代表元素作為該樹(shù)(集合)祖先。并查集可用于快速實(shí)現(xiàn)處理部分不相交集合(DisjointSets)并。通常見(jiàn)途就是用來(lái)維護(hù)某種等價(jià)類。并查集支持以下三種操作:(1)Make_Set(x)把每一個(gè)元素初始化為一個(gè)集合初始化后每一個(gè)元素父親節(jié)點(diǎn)是它本身,每一個(gè)元素祖先節(jié)點(diǎn)也是它本身。(2)Find_Set(x)查找一個(gè)元素所在集合查找一個(gè)元素所在集合,只要找到這個(gè)元素所在集合祖先即可。判定兩個(gè)元素是否屬于同一集合,只要看她們所在集合祖先是否相同即可。(3)Union(x,y)合并x,y所在兩個(gè)集合合并兩個(gè)不相交集合操作很簡(jiǎn)單:首先設(shè)置一個(gè)數(shù)組Father[x],表示x"父親"編號(hào)。那么,合并兩個(gè)不相交集合方法就是,找到其中一個(gè)集合祖先,將另外一個(gè)集合祖先指向它。相關(guān)并查集具體操作實(shí)現(xiàn)請(qǐng)參考相關(guān)資料。五試驗(yàn)要求在試驗(yàn)匯報(bào)中要寫(xiě)下列內(nèi)容:1.試驗(yàn)?zāi)?2.試驗(yàn)內(nèi)容;3.試驗(yàn)環(huán)境;4.試驗(yàn)原理和實(shí)現(xiàn)過(guò)程(

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論