c編程（丘志杰）實(shí)驗(yàn)報告格式

《c編程（丘志杰）實(shí)驗(yàn)報告格式》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、計算機(jī)專業(yè)類課程實(shí)驗(yàn)報告課程名稱：數(shù)據(jù)結(jié)構(gòu)學(xué)院專業(yè):計算機(jī)學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)生姓名：齊巍巍學(xué)號：2010060040013指導(dǎo)教師：周益民日期：2011年10月日電子科技大學(xué)計算機(jī)學(xué)院實(shí)驗(yàn)中心電孑科披丈學(xué)實(shí)驗(yàn)報告一、實(shí)驗(yàn)室名稱：A2-413-1二、實(shí)驗(yàn)項(xiàng)目名稱：線性表的應(yīng)用-瑟夫生死問題的求解三、實(shí)驗(yàn)原理：（以下正文文字：小四，楷體（楷體_GB2312）或宋體，行距：固定值20磅，段首空兩個字符。此為硬要求，不得違反。）利用線性鏈表，特別是循環(huán)鏈表來實(shí)現(xiàn)約瑟夫生死問題。約瑟夫生死問題的描述有三：【其一

2、】據(jù)說著名猶太歷史學(xué)家Josephus有過以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。然而Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲?！酒涠?7世紀(jì)的法國數(shù)學(xué)家加斯帕在《數(shù)目的

3、游戲問題》中講了這樣一個故事：15個教徒和15個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報數(shù)，每數(shù)到第九個人就將他扔入大海，如此循環(huán)進(jìn)行直到僅余15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒?！酒淙縉個人，編號0..N-1,從0開始報數(shù)，報到M-1的退出，通常取M

4、9人，便把他投入大海中，然后再從他的下一個人數(shù)起，數(shù)到第9人，再將他扔到大海中，如此循環(huán)地進(jìn)行，直到剩下最后一個乘客為止。約瑟夫問題并不難，但求解的方法很多。題目中30個人圍成一圈，因而啟發(fā)我們用一個循環(huán)的鏈來表示。可以使用結(jié)構(gòu)數(shù)組來構(gòu)成一個循環(huán)鏈。結(jié)構(gòu)中有兩個成員，其一為指向下一個人的指針，以構(gòu)成環(huán)形的鏈；其二為該人是否被扔下海的標(biāo)記，為1表示還在船上。從第一個人開始對還未扔下海的人進(jìn)行計數(shù)，每數(shù)到9時，將結(jié)構(gòu)中的標(biāo)記改為0,表示該人已被扔下海了。這樣循環(huán)計數(shù)直到有最后一個人為止。順序表算法原理：為了節(jié)

5、省空間復(fù)雜度，我們提出了這樣一種問題：能否采用線性表來實(shí)現(xiàn)？答案是肯定的。以動態(tài)數(shù)組元素代替循環(huán)鏈表節(jié)點(diǎn)的算法實(shí)現(xiàn)。考慮：動態(tài)數(shù)組的申請、使用、回收三原則。用30個元素數(shù)組來存放結(jié)果,初始化全為1,如果這個人被丟到海里了，就把對應(yīng)位置的元素置為0;用一個變量依次對數(shù)組里不為0的元素計數(shù)，數(shù)到9則把對應(yīng)位置的數(shù)組元素置0;循環(huán)控制可以用乘客數(shù)量來控制；初始為30,每有一個元素被置0,則乘客數(shù)量減1,直到1。低復(fù)雜度算法原理：無論是用鏈表實(shí)現(xiàn)還是用數(shù)組實(shí)現(xiàn)都有一個共同點(diǎn)：要模擬整個游戲過程，不僅程序?qū)懫饋肀容^

6、煩，而且時間復(fù)雜度高達(dá)O（MN）,當(dāng)N,M非常大（例如上百萬，上千萬）的時候，幾乎是沒有辦法在短時間內(nèi)出結(jié)果的。我們注意到原問題僅僅是要求出最后的勝利者的序號，而不是要讀者模擬整個過程。因此如果要追求效率，就要打破常規(guī)，實(shí)施一點(diǎn)數(shù)學(xué)策略。四、實(shí)驗(yàn)?zāi)康模和ㄟ^本次約瑟夫環(huán)的算法實(shí)驗(yàn)，可以有效鍛煉線性循環(huán)鏈表的初始化、遍歷、插入刪除操作，可以有效鍛煉順序表算法的取模置環(huán)方法，可以深刻討論利用數(shù)學(xué)方法在低時間復(fù)雜度求解問題時帶來的好處。本次實(shí)驗(yàn)重點(diǎn)考察數(shù)據(jù)結(jié)構(gòu)課程“線性表”一章的內(nèi)容。五、實(shí)驗(yàn)內(nèi)容：本次實(shí)驗(yàn)內(nèi)容包

7、含下面三個部分的內(nèi)容：第一，線性循環(huán)鏈表求解約瑟夫環(huán)。第二，順序表方案求解約瑟夫環(huán)。第三，第復(fù)雜度求解約瑟夫環(huán)。六、實(shí)驗(yàn)器材（設(shè)備、元器件）：（實(shí)驗(yàn)器材按照實(shí)際使用測試的，硬件平臺：計算機(jī)配置，CPU內(nèi)存等，軟件平臺：操作系統(tǒng)和開發(fā)環(huán)境，測試環(huán)境。越詳細(xì)越好。）硬件配置：電腦型號：戴爾InspironN4010筆記本處理器：英特爾Corei3M38O@2.53GHz雙核筆記本處理器安裝內(nèi)存：2.00GB（三星DDR31333MHz）主硬盤：西數(shù)WDCWD5000BEKT-75KA9T0（500GB/720

8、0轉(zhuǎn)/分）主板：戴爾0Y73YY軟件平臺：系統(tǒng)類型：Windows旗艦版32位開發(fā)環(huán)境：MicrosoftVisualStudio2008測試環(huán)境：MicrosoftVisualStudio2008七、實(shí)驗(yàn)步驟：循環(huán)鏈表解決方案偽代碼：1.首先定義鏈表節(jié)點(diǎn)。數(shù)據(jù)域用整數(shù)表示人員編號。2.然后將節(jié)點(diǎn)組成為30個節(jié)點(diǎn)的單循環(huán)鏈表。刪除計數(shù)器置0。3.從指定位置開始計數(shù)，移動計數(shù)器置1,移動指針到下一個節(jié)點(diǎn)，移動計數(shù)器加1。計數(shù)器置