約瑟夫生死游戲課程設(shè)計(jì)

1、<p>　　計(jì)算機(jī)學(xué)院信息管理與信息系統(tǒng)專業(yè)</p><p>　　《程序設(shè)計(jì)綜合課程設(shè)計(jì)》報(bào)告</p><p>　?。?010/2011學(xué)年 第一學(xué)期）</p><p>　　學(xué)生姓名： </p><p>　　學(xué)生班級(jí)： </p><p>　　學(xué)生學(xué)號(hào)： </

2、p><p>　　指導(dǎo)教師： </p><p>　　2011年　01　月　04　日</p><p><b>　　目錄</b></p><p>　　第一章 需求分析1</p><p>　　1.1課程設(shè)計(jì)目的1</p><p>　　1.2課程設(shè)計(jì)

3、要求1</p><p>　　1.3課程設(shè)計(jì)目標(biāo)與總體方案1</p><p>　　1.4程序執(zhí)行的命令1</p><p>　　第二章 系統(tǒng)的功能2</p><p>　　2.1系統(tǒng)功能說(shuō)明2</p><p>　　2.2 系統(tǒng)功能解析2</p><p>　　第三章 系統(tǒng)的設(shè)計(jì)3</

4、p><p>　　3.1Josphu鏈表的實(shí)現(xiàn)3</p><p><b>　　3.2循環(huán)鏈表3</b></p><p>　　3.3 對(duì)程序的各個(gè)部分的詳細(xì)介紹3</p><p>　　3.3.1利用類定義構(gòu)造成員函數(shù)以及成員3</p><p>　　3.3.2 定義成員函數(shù)4</p>

5、<p>　　3.3.3創(chuàng)建含有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表5</p><p>　　3.3.4 Josephu操作5</p><p>　　3.3.5主函數(shù)6</p><p>　　3.4程序的流程7</p><p>　　第四章 程序的運(yùn)行結(jié)果圖8</p><p>　　4.1開(kāi)始運(yùn)行程序8</p>

6、<p>　　4.2先鍵入?yún)⒓佑螒虻娜藬?shù)及報(bào)數(shù)間隔8</p><p>　　4.3按空格鍵運(yùn)行程序9</p><p><b>　　第五章 總結(jié)10</b></p><p><b>　　致謝11</b></p><p>　　附錄一 參考文獻(xiàn)12</p><p&g

7、t;　　附錄二 程序源代碼13</p><p><b>　　約瑟夫生死游戲</b></p><p><b>　　第一章 需求分析</b></p><p><b>　　1.1課程設(shè)計(jì)目的</b></p><p>　　課程設(shè)計(jì)目的是為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，獨(dú)立實(shí)踐的機(jī)會(huì)，將

8、課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合起來(lái)，鍛煉學(xué)生的分析解決實(shí)際問(wèn)題的能力。提高學(xué)生適應(yīng)實(shí)際，實(shí)踐編程的能力。通過(guò)實(shí)踐讓學(xué)生理論和實(shí)際操作相結(jié)合，更好的理解書面知識(shí)，并在鞏固的基礎(chǔ)上融會(huì)所學(xué)認(rèn)識(shí)。</p><p><b>　　1.2課程設(shè)計(jì)要求</b></p><p>　　約瑟夫生死游戲：30個(gè)人圍成一個(gè)圈由第一個(gè)人數(shù)起，依次報(bào)數(shù)，數(shù)到第九個(gè)人，便把他剔除，然后再?gòu)乃南?/p>

9、一個(gè)人數(shù)起，數(shù)到第九個(gè)人，再將他剔除剩下15個(gè)乘客為止，問(wèn)那些位置將是被扔下大海的位置。課程設(shè)計(jì)要求是將30個(gè)人改為n,報(bào)數(shù)（原為9），也改為任意正整數(shù)。根據(jù)得到的初始數(shù)據(jù)得到生者和死者的位置編號(hào)并輸出。</p><p>　　1.3課程設(shè)計(jì)目標(biāo)與總體方案</p><p>　　本實(shí)驗(yàn)設(shè)計(jì)的目標(biāo)是運(yùn)用循環(huán)鏈表來(lái)解決Josephu環(huán)問(wèn)題，其中運(yùn)用了許多鏈表中的基本操作使改程序能不只解決一個(gè)Jos

10、ephu的簡(jiǎn)單鏈表，其中的Josephu函數(shù)則是用于，運(yùn)用C++程序編寫程序，實(shí)現(xiàn)隊(duì)列的建立、插入和刪除基本功能，在程序設(shè)計(jì)成功的基礎(chǔ)上，進(jìn)一步深化理解隊(duì)列的作用和實(shí)現(xiàn)原理。</p><p>　　1.4程序執(zhí)行的命令</p><p>　　構(gòu)造鏈表、輸入數(shù)據(jù)、執(zhí)行報(bào)數(shù)輸出出列人的序號(hào)結(jié)束。</p><p><b>　　第二章 系統(tǒng)的功能</b>&

11、lt;/p><p>　　2.1系統(tǒng)功能說(shuō)明 </p><p>　　圖1 系統(tǒng)功能程序圖</p><p>　　2.2 系統(tǒng)功能解析</p><p>　　如上圖所示，本系統(tǒng)分為五個(gè)功能模塊分別為：構(gòu)建鏈表，確定n值，更新鏈表，輸入，輸出。下面就每個(gè)功能進(jìn)行詳細(xì)說(shuō)明：</p><p>　　（1）構(gòu)建約瑟夫鏈表：使整個(gè)游戲在鏈表中

12、運(yùn)行，使得結(jié)點(diǎn)在刪除時(shí)不需要移動(dòng)大量的結(jié)點(diǎn)；</p><p>　?。?）確定n的值：進(jìn)而使鏈具化體，從而可以構(gòu)建一個(gè)具體的鏈表；</p><p>　?。?）更新鏈表：對(duì)剔除結(jié)點(diǎn)后的鏈表進(jìn)行重新連接又，有構(gòu)成了一個(gè)新的鏈表，使得循環(huán)繼續(xù)進(jìn)行；</p><p>　?。?）輸入：輸入n的值進(jìn)行鏈表具體化，輸入間隔值m，使得間隔被確定，程序得以有效正確的進(jìn)行；</p&

13、gt;<p>　　（5）輸出：輸出要剔除的結(jié)點(diǎn)的數(shù)值。</p><p><b>　　第三章 系統(tǒng)的設(shè)計(jì)</b></p><p>　　3.1Josphu鏈表的實(shí)現(xiàn)</p><p>　　Josphu鏈表——鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)約瑟夫（Josephu）問(wèn)題：已知N個(gè)人圍坐在一張圓桌周圍（不妨以1，2，……，N對(duì)每一個(gè)人依次編號(hào)），現(xiàn)在先從序號(hào)

14、為K的人開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人出列，他的下一個(gè)人又從1開(kāi)始數(shù)，報(bào)數(shù)到m的人出列……直到所有人都出出列為止。給出出列的順序。</p><p><b>　　3.2循環(huán)鏈表</b></p><p>　　隊(duì)列的順序表示和實(shí)現(xiàn)和順序棧相似，在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外，尚需附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭

15、元素及隊(duì)列尾元素的位置。為了C語(yǔ)言中描述方便起見(jiàn)，在此我們約定，初始化建空隊(duì)列時(shí)，令front=rear=0,每當(dāng)插入新的隊(duì)列尾元素時(shí)，“尾指針增1”；每當(dāng)刪除隊(duì)列頭元素時(shí)，“頭指針增1”。因此，在非空隊(duì)列中，頭指針始終指向隊(duì)列頭元素，而尾指針始終指向隊(duì)列尾元素的下一個(gè)位置從上述分析可見(jiàn)，在C++中不能用動(dòng)態(tài)分配的一維數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列。如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列，則必須為它設(shè)定一個(gè)最大隊(duì)列長(zhǎng)度；若用戶無(wú)法預(yù)估所用隊(duì)列的最大長(zhǎng)度，

16、則宜采用鏈隊(duì)列。</p><p>　　3.3 對(duì)程序的各個(gè)部分的詳細(xì)介紹</p><p>　　編寫本實(shí)驗(yàn)設(shè)計(jì)程序采用C++進(jìn)行，在Visual c++ 6.0環(huán)境下運(yùn)行。</p><p>　　3.3.1利用類定義構(gòu)造成員函數(shù)以及成員</p><p>　　template<class T></p><p>　

17、　class List</p><p><b>　　{</b></p><p><b>　　public:</b></p><p><b>　　List()</b></p><p><b>　　{</b></p><p>　　fir

18、st=new LinkNode<T>;</p><p>　　first->link=first;</p><p><b>　　}</b></p><p><b>　　List(T x)</b></p><p><b>　　{</b></p>&l

19、t;p>　　first=new LinkNode<T>(x);</p><p>　　first->link=first;</p><p><b>　　}</b></p><p>　　List(List<T>&L);</p><p><b>　　~List(){}<

20、;/b></p><p>　　void Insert(int i,T x);</p><p>　　T getHead(){return first->data;}</p><p>　　LinkNode<T>* getfirst(){return first;}</p><p>　　void xiuf(LinkNode&

21、lt;T>* a){first=a;}</p><p>　　LinkNode<T>*Locate(int i);</p><p>　　protected:</p><p>　　LinkNode<T>*first;</p><p><b>　　};</b></p><p&g

22、t;　　3.3.2 定義成員函數(shù)</p><p>　　template<class T></p><p>　　List<T>::List(List<T>&L)</p><p><b>　　{</b></p><p><b>　　T value;</b>&l

23、t;/p><p>　　LinkNode<T>*srcptr=L.getHead();</p><p>　　LinkNode<T>*destptr=first=new LinkNode<T>;</p><p>　　destptr->data=srcptr->data;</p><p>　　while(

24、srcptr->link!=first)</p><p><b>　　{</b></p><p>　　value=srcptr->link->data;</p><p>　　destptr->link=new LinkNode<T>(value);</p><p>　　destptr=

25、destptr->link;</p><p>　　srcptr=srcptr->link;</p><p>　　last=srcptr;</p><p><b>　　}</b></p><p><b>　　};</b></p><p>　　template<

26、class T></p><p>　　LinkNode<T>* List<T>::Locate(int i)</p><p><b>　　{</b></p><p>　　if(i<0)return NULL;</p><p>　　LinkNode<T>* current=f

27、irst;</p><p><b>　　int k=1;</b></p><p>　　while(k<i)</p><p><b>　　{ </b></p><p>　　current=current->link;</p><p><b>　　k++;

28、</b></p><p>　　if(current==first)return NULL;</p><p><b>　　}</b></p><p>　　return current;</p><p><b>　　};</b></p><p>　　3.3.3創(chuàng)建含有

29、n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表</p><p>　　template<class T></p><p>　　void List<T>::Insert(int i,T x)</p><p><b>　　{</b></p><p>　　LinkNode<T>* current=Locate(i);&

30、lt;/p><p>　　if(current==NULL)return;</p><p>　　LinkNode<T>*newNode=new LinkNode<T>(x);</p><p>　　if(newNode==NULL)</p><p><b>　　{</b></p><p

31、>　　cout<<"存儲(chǔ)分配錯(cuò)誤!"<<endl;</p><p><b>　　exit(1);</b></p><p><b>　　}</b></p><p>　　newNode->link=current->link;</p><p>

32、;　　current->link=newNode;</p><p><b>　　};</b></p><p>　　3.3.4 Josephu操作</p><p>　　Josephu操作為本程序的重點(diǎn)，在本程序中我是利用了一個(gè)Josephu函數(shù)來(lái)解決該問(wèn)題的，該函數(shù)是通過(guò)不斷的循環(huán)、輸出、再循環(huán)、再輸出直到將Josephu鏈表中的一半元素被

33、輸出。函數(shù)如下：</p><p>　　template<class T></p><p>　　void Josephus(List<T>& Js,int n,int m)</p><p><b>　　{</b></p><p>　　LinkNode<T> *p=Js.Locat

34、e(1),*pre;</p><p><b>　　int i,j;</b></p><p>　　for(i=1;i<=n/2;i++)</p><p><b>　　{</b></p><p><b>　　if(m==1)</b></p><p>&

35、lt;b>　　{</b></p><p>　　cout<<"出列的人是:"<<p->data<<endl;</p><p>　　pre=p->link;</p><p>　　Js.xiuf(p->link);</p><p><b>　　de

36、lete p;</b></p><p><b>　　p=pre;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　

37、for(j=1;j<m;j++)</p><p><b>　　{</b></p><p><b>　　pre=p;</b></p><p>　　p=p->link;</p><p><b>　　}</b></p><p>　　cout<

38、<"出列的人是"<<p->data<<endl;</p><p>　　pre->link=p->link;</p><p>　　if(p==Js.getfirst())Js.xiuf(p->link);</p><p>　　//if(p=Js.getlast())Js.movelast(pre

39、);</p><p><b>　　delete p;</b></p><p>　　p=pre->link;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b>

40、</p><p><b>　　3.3.5主函數(shù)</b></p><p>　　void main()</p><p>　　{ List<int> clist(1);</p><p>　　int i,n,m;</p><p>　　cout<<"輸入游戲者的人數(shù)和報(bào)數(shù)間

41、隔："<<endl;</p><p>　　cin>>n>>m;</p><p>　　for(i=1;i<n;i++)</p><p><b>　　{</b></p><p>　　clist.Insert(i,i+1);</p><p><b

42、>　　}</b></p><p>　　Josephus(clist,n,m); </p><p><b>　　}</b></p><p><b>　　3.4程序的流程</b></p><p><b>　　3.4.1流程圖</b></p><

43、p><b>　　圖2 程序流程圖</b></p><p>　　3.4.2流程圖的說(shuō)明</p><p>　　開(kāi)始進(jìn)入程序，先確定n的值，然后，根據(jù)n得知建立鏈表，然后數(shù)數(shù)，確定輸出的位置，輸出數(shù)，更新鏈表，如果剩下的數(shù)小于等于n/2,則停止程序，否則繼續(xù)計(jì)數(shù)進(jìn)行循環(huán)直至結(jié)束程序。 </p><p>　　第四章 程序的運(yùn)行結(jié)果圖</p&

44、gt;<p>　　4.1開(kāi)始運(yùn)行程序 </p><p><b>　　程序的初始化</b></p><p><b>　　圖3 程序初始化</b></p><p>　　4.2先鍵入?yún)⒓佑螒虻娜藬?shù)及報(bào)數(shù)間隔</p><p>　　輸入人數(shù)和報(bào)數(shù)間隔30 9</p><p&g

45、t;　　圖4 確定n值及間隔值m</p><p>　　4.3按空格鍵運(yùn)行程序</p><p><b>　　運(yùn)行結(jié)果</b></p><p><b>　　圖4.3運(yùn)行結(jié)果</b></p><p><b>　　第五章 總結(jié)</b></p><p>　　通過(guò)本

46、次課程設(shè)計(jì)的鍛煉，使我對(duì)數(shù)據(jù)結(jié)構(gòu)又有了許多新的深刻認(rèn)識(shí)，更深的理解了數(shù)據(jù)結(jié)構(gòu)的難點(diǎn)，并且通過(guò)這次課程設(shè)計(jì)，我把以前認(rèn)為沒(méi)有實(shí)際用途的知識(shí)轉(zhuǎn)化為了實(shí)際問(wèn)題來(lái)解決，非常有意思，同時(shí)也覺(jué)得這種學(xué)習(xí)方法，更好的提高學(xué)習(xí)的效率，以下就是我做這次課程設(shè)計(jì)的主要體會(huì)：</p><p>　　一方面，在程序設(shè)計(jì)語(yǔ)言中，每一個(gè)數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲(chǔ)方式以及允許進(jìn)行的運(yùn)算。另一方面，在程序設(shè)

47、計(jì)過(guò)程中，當(dāng)需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時(shí)，總是借助編程語(yǔ)言所提供的數(shù)據(jù)類型來(lái)描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。</p><p>　　一個(gè)軟件系統(tǒng)框架應(yīng)建立在數(shù)據(jù)之上，而不是建立在操作之上。一個(gè)含抽象數(shù)據(jù)類型的軟件模塊應(yīng)包含定義、表示、實(shí)現(xiàn)三個(gè)部分。本實(shí)驗(yàn)設(shè)計(jì)就是建立在“定義、表示、實(shí)現(xiàn)”的基礎(chǔ)上完成的。同時(shí)，做好課程設(shè)計(jì)更能體現(xiàn)出同學(xué)的學(xué)習(xí)態(tài)度，對(duì)于新知識(shí)的渴望與追求，能夠反映出同學(xué)對(duì)自己負(fù)責(zé)任的決心，這點(diǎn)讓我感受頗深。 <

48、;/p><p><b>　　致謝</b></p><p>　　在此特別感謝xx老師的全力幫助與指導(dǎo)，通過(guò)這次課程設(shè)計(jì)，我對(duì)以前的知識(shí)不僅有了很好的復(fù)習(xí)，同時(shí)也把以前課本上的東西應(yīng)用在了實(shí)際上，對(duì)所學(xué)的知識(shí)有了很好的鞏固與實(shí)踐，當(dāng)然起初有很多問(wèn)題，很多疑惑，然而在老師們的細(xì)心指導(dǎo)下與幫助，我又學(xué)到了很多的知識(shí)動(dòng)的了很多道理許多事情不是逃避就可以沒(méi)事的，凡事都的去面對(duì)，另外還

49、要感謝xx老師上課的詳細(xì)講解為我的數(shù)據(jù)結(jié)構(gòu)打下結(jié)實(shí)的基礎(chǔ)。</p><p><b>　　附錄一 參考文獻(xiàn)</b></p><p>　　[1]譚浩強(qiáng).《C++程序設(shè)計(jì)》.北京:清華大學(xué)出版社 .2003年</p><p>　　[2]嚴(yán)蔚敏,吳偉民 .《數(shù)據(jù)結(jié)構(gòu)》.北京:清華大學(xué)出版社.2006年</p><p>　　[3]

50、嚴(yán)蔚敏,吳偉民,米寧.《數(shù)據(jù)結(jié)構(gòu)教程上機(jī)實(shí)驗(yàn)指導(dǎo)》.北京:清華大學(xué)出版社.2006年</p><p><b>　　附錄二 程序源代碼</b></p><p>　　#include<iostream></p><p>　　using namespace std;</p><p>　　template<cl

51、ass T></p><p>　　struct LinkNode</p><p><b>　　{</b></p><p><b>　　T data;</b></p><p>　　LinkNode<T>*link;</p><p>　　LinkNode( T

52、item)</p><p><b>　　{</b></p><p>　　data=item;</p><p>　　link=NULL;</p><p><b>　　}</b></p><p><b>　　};</b></p><p&g

53、t;　　template<class T></p><p>　　class List</p><p><b>　　{</b></p><p><b>　　public:</b></p><p><b>　　List()</b></p><p>

54、;<b>　　{</b></p><p>　　first=new LinkNode<T>;</p><p>　　first->link=first;</p><p><b>　　}</b></p><p><b>　　List(T x)</b></p&g

55、t;<p><b>　　{</b></p><p>　　first=new LinkNode<T>(x);</p><p>　　first->link=first;</p><p><b>　　}</b></p><p>　　List(List<T>&am

56、p;L);</p><p><b>　　~List(){}</b></p><p>　　void Insert(int i,T x);</p><p>　　T getHead(){return first->data;} LinkNode<T>* getfirst(){return first;}</p&

57、gt;<p>　　void xiuf(LinkNode<T>* a){first=a;}</p><p>　　LinkNode<T>*Locate(int i);</p><p>　　protected:</p><p>　　LinkNode<T>*first;</p><p><b&g

58、t;　　};</b></p><p>　　template<class T></p><p>　　List<T>::List(List<T>&L)</p><p><b>　　{</b></p><p><b>　　T value;</b>&l

59、t;/p><p>　　LinkNode<T>*srcptr=L.getHead();</p><p>　　LinkNode<T>*destptr=first=new LinkNode<T>;</p><p>　　destptr->data=srcptr->data;</p><p>　　while(

60、srcptr->link!=first)</p><p><b>　　{</b></p><p>　　value=srcptr->link->data;</p><p>　　destptr->link=new LinkNode<T>(value);</p><p>　　destptr=

61、destptr->link;</p><p>　　srcptr=srcptr->link;</p><p>　　last=srcptr;</p><p><b>　　}</b></p><p><b>　　};</b></p><p>　　template<

62、class T></p><p>　　LinkNode<T>* List<T>::Locate(int i)</p><p><b>　　{</b></p><p>　　if(i<0)return NULL;</p><p>　　LinkNode<T>* current=f

63、irst;</p><p><b>　　int k=1;</b></p><p>　　while(k<i)</p><p><b>　　{ </b></p><p>　　current=current->link;</p><p><b>　　k++;

64、</b></p><p>　　if(current==first)return NULL;</p><p><b>　　}</b></p><p>　　return current;</p><p><b>　　};</b></p><p>　　template&

65、lt;class T></p><p>　　void List<T>::Insert(int i,T x)</p><p><b>　　{</b></p><p>　　LinkNode<T>* current=Locate(i);</p><p>　　if(current==NULL)ret

66、urn;</p><p>　　LinkNode<T>*newNode=new LinkNode<T>(x);</p><p>　　if(newNode==NULL)</p><p><b>　　{</b></p><p>　　cout<<"存儲(chǔ)分配錯(cuò)誤!"<&

67、lt;endl;</p><p><b>　　exit(1);</b></p><p><b>　　}</b></p><p>　　newNode->link=current->link;</p><p>　　current->link=newNode;</p>&l

68、t;p><b>　　};</b></p><p>　　template<class T></p><p>　　void Josephus(List<T>& Js,int n,int m)</p><p><b>　　{</b></p><p>　　LinkNod

69、e<T> *p=Js.Locate(1),*pre;</p><p><b>　　int i,j;</b></p><p>　　for(i=1;i<=n/2;i++)</p><p><b>　　{</b></p><p><b>　　if(m==1)</b>

70、</p><p><b>　　{</b></p><p>　　cout<<"出列的人是:"<<p->data<<endl;</p><p>　　pre=p->link;</p><p>　　Js.xiuf(p->link);</p>

71、<p><b>　　delete p;</b></p><p><b>　　p=pre;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b>&

72、lt;/p><p>　　for(j=1;j<m;j++)</p><p><b>　　{</b></p><p><b>　　pre=p;</b></p><p>　　p=p->link;</p><p><b>　　}</b></p>

73、;<p>　　cout<<"出列的人是"<<p->data<<endl;</p><p>　　pre->link=p->link;</p><p>　　if(p==Js.getfirst())Js.xiuf(p->link);</p><p>　　//if(p=Js.get

74、last())Js.movelast(pre);</p><p><b>　　delete p;</b></p><p>　　p=pre->link;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>

75、<b>　　}</b></p><p>　　void main()</p><p><b>　　{ </b></p><p>　　List<int> clist(1);</p><p>　　int i,n,m;</p><p>　　cout<<&quo

76、t;輸入游戲者的人數(shù)和報(bào)數(shù)間隔："<<endl;</p><p>　　cin>>n>>m;</p><p>　　for(i=1;i<n;i++)</p><p>　　{ clist.Insert(i,i+1);</p><p><b>　　}</b></p>