(完整word版)約瑟夫生死游戲課程設(shè)計(jì)(含源代碼可以運(yùn)行)(2)(word文檔良心出品)

1、湖南商學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)約瑟夫雙向生死游戲?qū)W生姓名梁子嫣140920043計(jì)算機(jī)工程與信息學(xué)院專(zhuān)業(yè)班級(jí)計(jì)科1402指導(dǎo)教師蔣偉進(jìn)教授2016年 6月26日目錄第一章需求分析1.1課程設(shè)計(jì)要求 1.2課程設(shè)計(jì)目標(biāo)與總體方案錯(cuò)誤！未定義書(shū)簽。1.3程序執(zhí)行的命令第二章算法描述2.1算法描述錯(cuò)誤！未定義書(shū)簽。2.2系統(tǒng)圖形說(shuō)明第三章系統(tǒng)的設(shè)計(jì)3.1創(chuàng)建雙向鏈表3.2約瑟夫算法3.4主函數(shù)第四章 程序的運(yùn)行結(jié)果圖附錄約瑟夫生死游戲章需求分析1.1項(xiàng)目簡(jiǎn)介約瑟夫雙向生死游戲是在約瑟夫生者死者游戲的基礎(chǔ)上，正向計(jì)數(shù)后反向計(jì) 數(shù)，然后再正向計(jì)數(shù)。具體描述如下：30個(gè)旅客同乘一條船，因?yàn)閲?yán)重超載, 加

2、上風(fēng)高浪大，危險(xiǎn)萬(wàn)分；因此船長(zhǎng)告訴乘客，只有將全船一半的旅客投入海中, 其余人才能幸免遇難。無(wú)奈，大家只得同意這種辦法，并議定30個(gè)人圍成一圈, 由第一個(gè)人開(kāi)始，順時(shí)針依次報(bào)數(shù)，數(shù)到第 9人，便把他投入大海中，然后從他的下一個(gè)人數(shù)起，逆時(shí)針數(shù)到第5人，將他投入大海，然后從他逆時(shí)針的下一個(gè)人數(shù)起，順時(shí)針數(shù)到第9人，再將他投入大海，如此循環(huán)，直到剩下 15個(gè)乘客為止。問(wèn)哪些位置是將被扔下大海的位置。1.2設(shè)計(jì)思路本游戲的數(shù)學(xué)建模如下：假設(shè)n個(gè)旅客排成一個(gè)環(huán)形，依次順序編號(hào)1,2,-,n。從某個(gè)指定的第1號(hào)開(kāi)始，沿環(huán)計(jì)數(shù)，數(shù)到第 m個(gè)人就讓其出列，然后從第 m+1個(gè)人反向計(jì)數(shù)到m-k+1個(gè)人，讓其出

3、列，然后從m-k個(gè)人開(kāi)始重新正向沿環(huán)計(jì)數(shù)，再數(shù)m個(gè)人后讓其出列，然后再反向數(shù) k個(gè)人后讓其出列。這個(gè)過(guò)程一 直進(jìn)行到剩下q個(gè)旅客為止。本游戲的要求用戶(hù)輸入的內(nèi)容包括:1. 旅客的個(gè)數(shù)，也就是n的值;2. 正向離開(kāi)旅客的間隔數(shù)，也就是 m的值;3. 反向離開(kāi)旅客的間隔數(shù)，也就是 k的值;4.所有旅客的序號(hào)作為一組數(shù)據(jù)要求存放在某種數(shù)據(jù)結(jié)構(gòu)中。本游戲要求輸出的內(nèi)容是包括1. 離開(kāi)旅客的序號(hào);2. 剩余旅客的序號(hào)；所以，根據(jù)上面的模型分析及輸入輸出參數(shù)分析，可以定義一種數(shù)據(jù)結(jié)構(gòu)后進(jìn)行 算法實(shí)現(xiàn)。第二章系統(tǒng)的功能2.1系統(tǒng)文字描述(1)創(chuàng)建含有n個(gè)結(jié)點(diǎn)的雙向循環(huán)鏈表;生著與死者的選擇：P指向鏈表的第一

4、個(gè)結(jié)點(diǎn)，初始i置為1；while(iv=n/2) /刪除一半的結(jié)點(diǎn)從P指向的結(jié)點(diǎn)沿鏈前進(jìn)m-1步； 刪除第m個(gè)結(jié)點(diǎn)(q所指向的結(jié)點(diǎn))； P指向q的下一個(gè)結(jié)點(diǎn)；輸出其位置q->data;i自增1；從P指向的結(jié)點(diǎn)沿鏈后退k-1步； 刪除第k個(gè)結(jié)點(diǎn)(q所指向的結(jié)點(diǎn))；P指向q的上一個(gè)結(jié)點(diǎn);輸出其位置q->data;i自增1；(3)輸出所有生者的位置。2.2系統(tǒng)圖形說(shuō)明第三章系統(tǒng)的設(shè)計(jì)3.1創(chuàng)建雙向循環(huán)鏈表;no de* createList(i nt num)no de* head = (no de*)malloc(sizeof( no de);head->value = 1;no

5、 de* p = head;for(i nt i = 1;i vnu m;i+)no de* p Next = (no de*)malloc(sizeof( no de);p Next->value = i+1;p->n ext = p Next;p Next->left = p;p = p Next;p->n ext = head;head->left = p;retu rn head;3.2生者與死者的選擇int deleteList (no de* head, int nu m1,i nt nu m2,i nt tota IPeop le,i nt aliv

6、e Pep ole)/num1 代表順時(shí)針數(shù)num2代表逆時(shí)針數(shù)no de* p = head;int peop leOfNow = tota IPeople;while( peop leOfNow>alive Pepole)/ 找到順時(shí)針要?jiǎng)h除節(jié)點(diǎn)的前一節(jié)點(diǎn) Pfor(i nt i =1; ivnumi - 1;i+)p = p->n ext;/ 刪除順時(shí)針時(shí)的節(jié)點(diǎn)no de* toBeDeleted = p->n ext;prin tf("deadma n = %dn ",toBeDeleted->value);no de* n extToDel

7、eted = toBeDeleted->n ext;p->n ext = n extToDeleted;n extToDeleted->left = p;free(toBeDeleted);peopi eOfNow-;if(peop leOfNow>alive Pep ole) /防止不需要再刪除節(jié)點(diǎn)了，所以要先判斷/找到逆時(shí)針時(shí)要?jiǎng)h除節(jié)點(diǎn)的前一節(jié)點(diǎn)no de* s = n extToDeleted;for(i nt i =1; ivnum2 -1;i+)s = s->left;/刪除逆時(shí)針時(shí)的節(jié)點(diǎn)no de* tobeDeleted = s->left;p

8、rin tf("deadma n = %dn ",tobeDeleted->value);node* leftToBeDeleted = tobeDeleted->left;s->left = leftToBeDeleted;leftToBeDeleted->n ext = s;free(tobeDeleted);peop leOfNow-;p = leftToBeDeleted;return 0;3.3主函數(shù)int main()no de* head = createList(30);deleteList( head, 9,5,30,15);ret

9、urn 0;g514101915242029254301221any key to continue第四章程序運(yùn)行結(jié)果i匚 *GMicrosoft Visual StudioXCommonMSDew9£EinTDebLjgyLifu.FJCEde adman deadman de adman deadnian ds adman deadnian deadman de adman deadnian ds adman deadnian deadman deadman de adman de Sidman Press附錄源代碼#i nclude "stdio.h" #i

10、 nclude "stdlib.h" struct nodeint value;no de* left;no de* n ext;Node;/創(chuàng)建雙向的循環(huán)鏈表 no de* createList(i nt num)no de* head = (no de*)malloc(sizeof( no de);head->value = 1;no de* p = head;for(i nt i = 1;i vnu m;i+)no de* p Next = (no de*)malloc(sizeof( no de);p Next->value = i+1;p->n

11、ext = p Next;p Next->left = p;p = p Next;p->n ext = head;head->left = p;retu rn head;int deleteList (no de* head, int nu m1,i nt nu m2,i nt tota IPeop le,i nt alive Pep ole)/num1 代表順時(shí)針數(shù)num2代表逆時(shí)針數(shù)no de* p = head;int peop leOfNow = tota IPeople;while( peop leOfNow>alive Pepole)/ 找到順時(shí)針要?jiǎng)h除節(jié)點(diǎn)

12、的前一節(jié)點(diǎn) Pfor(i nt i =1; ivnum1 - 1;i+)p = p->n ext;/ 刪除順時(shí)針時(shí)的節(jié)點(diǎn)no de* toBeDeleted = p->n ext;prin tf("deadma n = %dn ",toBeDeleted->value);no de* n extToDeleted = toBeDeleted->n ext;p->n ext = n extToDeleted;n extToDeleted->left = p;free(toBeDeleted);peopi eOfNow-;if(peop leOfNow>alive Pep ole) /防止不需要再刪除節(jié)點(diǎn)了，所以要先判斷/找到逆時(shí)針時(shí)要?jiǎng)h除節(jié)點(diǎn)的前一節(jié)點(diǎn)no de* s = n extToDeleted;for(i nt i =1; ivnum2 -1;i+)s = s->left;/刪除逆時(shí)針時(shí)的節(jié)點(diǎn)no de* tobeDeleted = s->left;prin tf("deadma n = %dn ",tobeDeleted->value);node* leftToBeDeleted = tobeDeleted->