約瑟夫生死游戲課程設計

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：19 大?。?09.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩18頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　計算機學院信息管理與信息系統(tǒng)專業(yè)　　《程序設計綜合課程設計》報告　?。?010/2011學年第一學期）　　學生姓名： 　　學生班級： 　　學生學號： </

2、p>　　指導教師： 　　2011年　01　月　04　日　　目錄　　第一章需求分析1　　1.1課程設計目的1　　1.2課程設計

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

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

5、　　3.3.3創(chuàng)建含有n個結點的單循環(huán)鏈表5　　3.3.4 Josephu操作5　　3.3.5主函數(shù)6　　3.4程序的流程7　　第四章程序的運行結果圖8　　4.1開始運行程序8

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

7、t;　　附錄二程序源代碼13　　約瑟夫生死游戲　　第一章需求分析　　1.1課程設計目的　　課程設計目的是為學生提供了一個既動手又動腦，獨立實踐的機會，將

8、課本上的理論知識和實際有機的結合起來，鍛煉學生的分析解決實際問題的能力。提高學生適應實際，實踐編程的能力。通過實踐讓學生理論和實際操作相結合，更好的理解書面知識，并在鞏固的基礎上融會所學認識。　　1.2課程設計要求　　約瑟夫生死游戲：30個人圍成一個圈由第一個人數(shù)起，依次報數(shù)，數(shù)到第九個人，便把他剔除，然后再從他的下

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

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

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

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

13、gt;　　（5）輸出：輸出要剔除的結點的數(shù)值。　　第三章系統(tǒng)的設計　　3.1Josphu鏈表的實現(xiàn)　　Josphu鏈表——鏈式表示和實現(xiàn)約瑟夫（Josephu）問題：已知N個人圍坐在一張圓桌周圍（不妨以1，2，……，N對每一個人依次編號），現(xiàn)在先從序號

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

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

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

17、　class List　　{　　public:　　List()　　{　　fir

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

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

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

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

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

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

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

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

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

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

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

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

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

31、>　　cout<<"存儲分配錯誤!"<<endl;　　exit(1);　　}　　newNode->link=current->link;

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

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

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

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

36、lete p;　　p=pre;　　}　　else　　{

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

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

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

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

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

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

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

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

45、t;　　圖4 確定n值及間隔值m　　4.3按空格鍵運行程序　　運行結果　　圖4.3運行結果　　第五章總結　　通過本

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

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

48、;/p>　　致謝　　在此特別感謝xx老師的全力幫助與指導，通過這次課程設計，我對以前的知識不僅有了很好的復習，同時也把以前課本上的東西應用在了實際上，對所學的知識有了很好的鞏固與實踐，當然起初有很多問題，很多疑惑，然而在老師們的細心指導下與幫助，我又學到了很多的知識動的了很多道理許多事情不是逃避就可以沒事的，凡事都的去面對，另外還

49、要感謝xx老師上課的詳細講解為我的數(shù)據(jù)結構打下結實的基礎。　　附錄一參考文獻　　[1]譚浩強.《C++程序設計》.北京:清華大學出版社 .2003年　　[2]嚴蔚敏,吳偉民 .《數(shù)據(jù)結構》.北京:清華大學出版社.2006年　　[3]

50、嚴蔚敏,吳偉民,米寧.《數(shù)據(jù)結構教程上機實驗指導》.北京:清華大學出版社.2006年　　附錄二程序源代碼　　#include<iostream>　　using namespace std;　　template<cl

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

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

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

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

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

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

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

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

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

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

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

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

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

64、　　if(current==first)return NULL;　　}　　return current;　　};　　template&

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

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

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

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

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

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

71、　　delete p;　　p=pre;　　}　　else　　{&

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

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

約瑟夫生死游戲課程設計

文檔簡介

溫馨提示

最新文檔

評論

約瑟夫生死游戲課程設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載