約瑟夫環(huán)程序設(shè)計(jì)報(bào)告書

1、精品附件4:課程設(shè)計(jì)報(bào)告書數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告約瑟夫（Joseph ） 環(huán)組別 第七組組長(zhǎng)組成員成績(jī)指導(dǎo)教師計(jì)算機(jī)科學(xué)與技術(shù)系welcome精品2014年6月11日摘要約瑟夫環(huán)問(wèn)題是典型的線性表的應(yīng)用實(shí)例，其開發(fā)主要包括后臺(tái)數(shù)據(jù)庫(kù)的建立 和維護(hù)以及前端應(yīng)用程序的開發(fā)兩個(gè)方面。 對(duì)于前者要求建立起數(shù)據(jù)一致性和完 整性強(qiáng)、數(shù)據(jù)安全性好的庫(kù)。而對(duì)于后者則要求應(yīng)用程序功能完備，易使用等特 點(diǎn)。經(jīng)過(guò)分析，我們使用 MICROSOFT公司的Microsoft Visual C+6.0 開發(fā)工 具，利用其提供的各種面向?qū)ο蟮拈_發(fā)工具， 尤其是數(shù)據(jù)窗口這一能方便而簡(jiǎn)潔 操作數(shù)據(jù)庫(kù)的智能化對(duì)象，首先在短時(shí)間內(nèi)建

2、立系統(tǒng)原型，然后，對(duì)初始原型系 統(tǒng)進(jìn)行需求迭代，不斷修正和改進(jìn)，直到形成用戶滿意的可行系統(tǒng)。關(guān)鍵詞：?jiǎn)窝h(huán)鏈表；c語(yǔ)言；約瑟夫環(huán)；序言數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素之間的邏輯關(guān)系的一門課程， 以及數(shù)據(jù)元素及其關(guān)系 在計(jì)算機(jī)中的存儲(chǔ)表示和對(duì)這些數(shù)據(jù)所施加的運(yùn)算。 該課程設(shè)計(jì)的目的是通過(guò)課 程設(shè)計(jì)的綜合訓(xùn)練，培養(yǎng)分析和編程等實(shí)際動(dòng)手能力，系統(tǒng)掌握數(shù)據(jù)結(jié)構(gòu)這門課 程的主要內(nèi)容。本次課程設(shè)計(jì)的內(nèi)容是用單循環(huán)鏈表模擬約瑟夫環(huán)問(wèn)題，循環(huán)鏈表是一種首尾 相接鏈表，其特點(diǎn)是無(wú)須增加存儲(chǔ)容量，僅對(duì)表的鏈接方式稍作改變，使表處理 更加靈活，約瑟夫環(huán)問(wèn)題就是用單循環(huán)鏈表處理的一個(gè)實(shí)際應(yīng)用。通過(guò)這個(gè)設(shè)計(jì)實(shí)例，了解單鏈表和單循

3、環(huán)鏈表的相同與不同之處， 進(jìn)一步加深對(duì)鏈表結(jié)構(gòu)類型 及鏈表操作的理解。通過(guò)該課程設(shè)計(jì)，能運(yùn)用所學(xué)知識(shí)，能上機(jī)解決一些實(shí)際問(wèn)題，了解并初步掌welcome精品握設(shè)計(jì)、實(shí)現(xiàn)較大程序的完整過(guò)程，包括系統(tǒng)分析、編碼設(shè)計(jì)、系統(tǒng)集成、以及 調(diào)試分析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計(jì)、實(shí)現(xiàn)以及操作方法，為進(jìn)一步的應(yīng) 用開發(fā)打好基礎(chǔ)。章節(jié)安排摘要、序言1一、問(wèn)題描述1、課程設(shè)計(jì)目的42、課程設(shè)計(jì)任務(wù)4二、設(shè)計(jì)過(guò)程1、設(shè)計(jì)思想（數(shù)據(jù)結(jié)構(gòu)）42、設(shè)計(jì)表示（函數(shù)說(shuō)明）53、詳細(xì)設(shè)計(jì)（主要算法）64、用戶手冊(cè)（使用說(shuō)明）6三、測(cè)試報(bào)告1、測(cè)試用例6welcome精品2、測(cè)試結(jié)果63、分析探討7四、總結(jié)10五、附錄（源程序

4、）10六、參考文獻(xiàn) 16welcome精品章節(jié)安排：一、問(wèn)題描述1、課程設(shè)計(jì)目的1 .掌握單向循環(huán)鏈表的建立。2 .掌握單向循環(huán)鏈表的操作。2、課程設(shè)計(jì)任務(wù)編號(hào)是1,2,的,nn個(gè)人按照順時(shí)針?lè)较驀蝗?，每個(gè)人只有一個(gè)密碼（正 整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值 m,從第一個(gè)仍開始順時(shí)針?lè)较蜃?1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列,將他的密碼作為新的m值, 從他在順時(shí)針?lè)较虻南乱粋€(gè)人開始重新從 1報(bào)數(shù)，如此下去，直到所有人全部出列 為止。請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序求出出列順序。1 .利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序輸出各個(gè)人的編號(hào)。2 .輸入數(shù)據(jù)：建立輸入函數(shù)處理輸入

5、的數(shù)據(jù)，輸入m的初值n,輸入每個(gè)人的密碼, 建立單向循環(huán)鏈表。3 .輸出形式：建立一個(gè)輸出函數(shù)，將正確的出列順序輸出。二、設(shè)計(jì)過(guò)程1、設(shè)計(jì)思想（數(shù)據(jù)結(jié)構(gòu)）首先，設(shè)計(jì)實(shí)現(xiàn) 瑟夫環(huán)問(wèn)題的存儲(chǔ)結(jié)構(gòu)。由于約瑟夫環(huán)本身具有循環(huán)性質(zhì)，考 慮采用循環(huán)鏈表，為了統(tǒng)一對(duì)表中任意節(jié)點(diǎn)的操作，循環(huán)鏈表不帶頭結(jié)點(diǎn)。循環(huán)鏈表的結(jié)點(diǎn)定義為如下結(jié)構(gòu)類型：welcome精品struct Lnode /*定義鏈表 */(int number;int password;struct Lnode *next;Lnode,*p,*q,*head;其次，建立一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表并由頭指針first指示。最后，設(shè)計(jì)約瑟夫環(huán)問(wèn)題的算法

6、。2、設(shè)計(jì)表示(函數(shù)說(shuō)明)1、循環(huán)鏈表抽象數(shù)據(jù)類型定義struct Lnode /* 定義鏈表 */(int number;int password;struct Lnode *next;Lnode,*p,*q,*head;2、本程序包含一下幾個(gè)模塊(1)創(chuàng)建單鏈表for(i=1;i<=n;i+) /*建立單鏈表 */welcome精品(if(i=1)(head=p=(structLnode*)malloc(sizeof(struct Lnode);)else(q=(struct Lnode*)malloc(sizeof(struct Lnode);p->next=q;p=q;)(

7、3)形成循環(huán)鏈表p->next=head; /*形成循環(huán)鏈表*/(4)主函數(shù)模塊int main ()3、詳細(xì)設(shè)計(jì)(主要算法)welcome精品4、用戶手冊(cè)（使用說(shuō)明）正確的執(zhí)行完程序后，進(jìn)去程序顯示屏。首先按任意鍵繼續(xù)，然后輸入初始密碼，緊接著輸入測(cè)試人的數(shù)量n,其次依次輸入測(cè)試人的密碼，最后輸入報(bào)數(shù) 上限值m ,完成后將進(jìn)行結(jié)果的輸出。三、測(cè)試報(bào)告1、測(cè)試用例.測(cè)試數(shù)據(jù)：m的初值為20,n=7,7個(gè)人的密碼依次為3,1,7,2,4,7,4,首先m=6, 則正確的輸出是什么？2、測(cè)試結(jié)果welcome精品約瑟夫環(huán)程序設(shè)計(jì)f H7須告奉勖邦德的榮譚r?碼前密為人3 1 7 Z 4 7 4

8、 7倒珥酗碼酗耐酗ni密密密密密密密3 hJhu.hJ.hyhHJ.hHJ.hdJ- AAAAAA61:m 4/N 人12 3 4567字 7) 避第第第第第第第戴:&靛 正測(cè)入人人人人人人人日13、分析與探討無(wú)論是用鏈表實(shí)現(xiàn)還是用數(shù)組實(shí)現(xiàn)都有一個(gè)共同點(diǎn)：要模擬整個(gè)游戲過(guò)程，不僅程序?qū)懫饋?lái)比較煩，而且時(shí)間復(fù)雜度高達(dá)O(nm),當(dāng)n, m非常大(例如上百萬(wàn)，上千萬(wàn))的時(shí)候，幾乎是沒有辦法在短時(shí)間內(nèi)出結(jié)果的。我們注意到原問(wèn)題僅僅是要求出最后的勝利者的序號(hào)，而不是要讀者模擬整個(gè)過(guò)程。因此如果要追求效率，就要打破常規(guī)，實(shí)施一點(diǎn)數(shù)學(xué)策略。為了討論方便，先把問(wèn)題稍微改變一下，并不影響原意：?jiǎn)栴}描述

9、：n個(gè)人(編號(hào)0(n-1),從0開始報(bào)數(shù)，報(bào)到m-1的退出welcome精品,剩下的人繼續(xù)從0開始報(bào)數(shù)。求勝利者的編號(hào)。我們知道第一個(gè)人（編號(hào)一定是（m-1）%n）出列之后，剩下的n-1個(gè)人組 成了一個(gè)新的約瑟夫環(huán)（以編號(hào)為k=m%n的人開始）：k k+1 k+2 . n-2, n-1,0, 1,2, . k-2并且從k開始報(bào)0?，F(xiàn)在我們把他們的編號(hào)做一下轉(zhuǎn)換：k -> 0k+1 -> 1k+2 -> 2.k-3 -> n-3k-2 -> n-2序列 1 : 0, 1,2, 3 n-2, n-1序列 2: 0, 1,2, 3 k-2, k,，n-2, n-1序列

10、3 : k, k+1, k+2, k+3,，n-2, n-1, 1,2,3,k-2,序列 4: 0, 1,2, 3 ，5, 6, 7, 8,，n-3, n-2變換后就完完全全成為了（n-1）個(gè)人報(bào)數(shù)的子問(wèn)題，假如我們知道這個(gè)子問(wèn)題的解：例如x是最終的勝利者，那么根據(jù)上面這個(gè)表把這個(gè)x變回去不剛好就是n個(gè)人情況的解嗎？ ！ ！變回去的公式很簡(jiǎn)單，相信大家都可以推 出來(lái)：k=m%n;welcome精品x' = x+k = x+ m%n ; 而 x+ m%n 可能大于 nx'= (x+ m%n)%n = (x+m)%n得至U x ' =(x+m)%n如何知道(n-1)個(gè)人報(bào)數(shù)

11、的問(wèn)題的解？對(duì)，只要知道(n-2)個(gè)人的解就行 了。(n-2)個(gè)人的解呢？當(dāng)然是先求(n-3)的情況-這顯然就是一個(gè)倒推問(wèn) 題！好了，思路出來(lái)了，下面寫遞推公式：令f表示i個(gè)人玩游戲報(bào)m退出最后勝利者的編號(hào)，最后的結(jié)果自然是 fn.遞推公式：f1=0;fi=(fi-1+m)%i; (i>1)有了這個(gè)公式，我們要做的就是從1-n順序算出f的數(shù)值，最后結(jié)果是 fn o我們輸出fn由于是逐級(jí)遞推，不需要保存每個(gè)，程序也是異常簡(jiǎn)單： (注意編號(hào)是0 - n-1)#include <stdio.h>int main(void)int n, m, i, s=0;printf ("

12、;N M =");scanf("%d%d", &n, &m);for (i=2; i<=n; i+)s=(s+m)%i;welcome精品printf ("The winner is %dn", s);return 0 ;)時(shí)間復(fù)雜度為O(n),相對(duì)于模擬算法已經(jīng)有了很大的提高。算 n, m等 于一百萬(wàn)，一千萬(wàn)的情況不是問(wèn)題了?？梢?，適當(dāng)?shù)剡\(yùn)用數(shù)學(xué)策略，不僅可 以讓編程變得簡(jiǎn)單，而且往往會(huì)成倍地提高算法執(zhí)行效率。參照上面提供的思路，我認(rèn)為可以類似的得到一個(gè)更易于明白的方法， 設(shè)有(1,2,3,，k-1 , k, k+1 ,

13、，n) n個(gè)數(shù)，當(dāng)k出列時(shí)，那么 有k+1 ->1k+2 ->2n ->n-k1 ->n-k+1 . .k-1 ->n-1由上面一組式子可以推出，若知道新產(chǎn)生的 n-1個(gè)數(shù)中某個(gè)數(shù)x,那么 很顯然可以推出x在原數(shù)列里的位置，即x ' = (x+k ) %n,由此，我們可以 得到一個(gè)遞推公式f1=1welcome精品fn=(fn-1+k)%n(n>1 )如果你認(rèn)為上式可以推出約瑟夫環(huán)問(wèn)題的解，很不幸，你錯(cuò)了，上面的遞推公式中，在某種情況下，fn-1+k 會(huì)整除n,如n=2 , k=3 ,這時(shí)我們修要對(duì)上式進(jìn)行修正，fn=(fn-1+k)%n;if(fn

14、=0)fn=n;問(wèn)題得解。程序代碼如下：#include<stdio.h>int main()int n,k,s=1;scanf("%d%d”,&n,&k);for(int i=2;i<=n;i+=1)s=(s+k)%i;if(s=0)s=i;printf("ans=%dn",s);return 0;當(dāng)然，我們還可以用遞歸方法解決此問(wèn)題：#include<stdio.h>int main()welcome精品(int jos(int n,int k);int n,k,s;scanf("%d%d",&

15、amp;n,&k);s=jos(n,k);printf("ans=%dn",s);return 0;)int jos(int n,int k)(int x;if(n=1)x=1;else x=(jos(n-1,k)+k)%n;if(x=0)x=n;return x;四、總結(jié)我的這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的題目是：約瑟夫環(huán)，通過(guò)對(duì)該題目 的設(shè)計(jì)，我加深了對(duì)數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的理解，進(jìn)一步地理解和掌握 了課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，尤其是對(duì)單循環(huán)鏈表上基本運(yùn)算的實(shí) 現(xiàn)，學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題，鍛煉了自己動(dòng)手的能 力。通過(guò)這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我感受最深的就是對(duì)于

16、循環(huán)鏈表welcome精品的使用，可以說(shuō)對(duì)循環(huán)鏈表有了比以前更進(jìn)一步的認(rèn)識(shí)，以前只是一知半解的，如果只給個(gè)題目自己根本不能把程序完整地編寫出來(lái)，所以這次課程設(shè)計(jì)最大的收獲就在于對(duì)循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個(gè)循環(huán)鏈表，刪除鏈表中的一個(gè)結(jié)點(diǎn)， 增加一個(gè)結(jié)點(diǎn)等。在調(diào)試程序的時(shí)候我也有所體會(huì)，雖然約瑟夫環(huán)問(wèn)題不是很難，但調(diào)試的時(shí)候還是會(huì)出現(xiàn)很多錯(cuò)誤，因此我們不能認(rèn)為容易就不認(rèn)真對(duì)待。在以后的學(xué)習(xí)中，要能不斷發(fā)現(xiàn)問(wèn)題，提出問(wèn) 題，解決問(wèn)題，從不足之處出發(fā)，在不斷學(xué)習(xí)中提高自己。 兩周的 課程設(shè)計(jì)很短暫，但其間的內(nèi)容是很充實(shí)的，在其中我學(xué)習(xí)到了很多 平時(shí)書本中無(wú)法學(xué)到的東西，積

17、累了經(jīng)驗(yàn)，鍛煉了自己分析問(wèn)題，解 決問(wèn)題的能力，并學(xué)會(huì)了如何將所學(xué)的各課知識(shí)融會(huì)，組織起來(lái)進(jìn)行 學(xué)習(xí)，總而言之這兩周中我學(xué)到很多，受益匪淺。五、附錄（源程序）#include<stdio.h>#include<stdlib.h>#include<windows.h>#include "string.h"struct Lnode /* 定義鏈表 */welcome精品(int number;int password;struct Lnode *next;Lnode,*p,*q,*head;int main(void)(system(&quo

18、t;color 0a");system("titleO。邦德的榮耀。");printf(" n");printf(" ，n");printf("”n");printf("n");welcome精品printf（" ，n"）;printf（" 方printf（" "n"）;int n; /n 個(gè)人int i; int m; /初始報(bào)數(shù)上限值int j, k, s, u;char ch;char mima100="007

19、"char input100;printf（" 約瑟夫環(huán)程序設(shè)計(jì)nn"）;printf（"007傾 情 奉 獻(xiàn)nn"）;printf（"O 。邦德的榮耀邦德的榮耀nn"）;printf（"密碼為 007n"）;/system（"pause"）;welcome精品for(k=0,s=3;k<=2;k+,s-)(printf("請(qǐng)輸入密碼：n");gets(input);if(strcmp(mima,input)=0)/ 比較字符串 mima 和 input 的大

20、小，此時(shí)相等(printf("密碼正確!n");break;else(printf("密碼錯(cuò)誤，你還有d次機(jī)會(huì)n”,s-1);while(s=1)(return 0;welcome精品for(u=0;u+)/ 套上for循環(huán)以判斷是否繼續(xù)進(jìn)行(printf("輸入測(cè)試人的數(shù)量n:"); /*輸入測(cè)試人的數(shù)量*/scanf("%d",&n);loop:if(n<=0) /*檢驗(yàn)n是否滿足要求，如不滿足重新輸入n值*/(printf("n n 是錯(cuò)的!n'n");printf("

21、;請(qǐng)?jiān)俅屋斎?n:");scanf("%d",&n);goto loop;for(i=1;i<=n;i+) /* 建立單鏈表 */(if(i=1)(head=p=(struct Lnode*)malloc(sizeof(structLnode);welcome精品else(q=(struct Lnode*)malloc(sizeof(struct Lnode);p->next=q;p=q;printf("請(qǐng)輸入第%d個(gè)人的密碼：",i); /*輸入每個(gè)人所持有的密碼值*/scanf("%d”,&(p->password);p->number=i;p->next=head; /*形成循環(huán)鏈表*/p=head;printf("請(qǐng)輸入數(shù)字 m:");scanf("%d",&m);printf("密碼是:")；for (j=1;j<=n;j+) /*輸出各人的編號(hào)*/(for(i=1;i<m;i+,p=p->next);welcome精品m=p->