約瑟夫環(huán)程序設(shè)計報告書

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

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

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

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

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

6、。2、設(shè)計表示(函數(shù)說明)1、循環(huán)鏈表抽象數(shù)據(jù)類型定義struct Lnode /* 定義鏈表 */(int number;int password;struct Lnode *next;Lnode,*p,*q,*head;2、本程序包含一下幾個模塊(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è)計(主要算法)welcome精品4、用戶手冊（使用說明）正確的執(zhí)行完程序后，進(jìn)去程序顯示屏。首先按任意鍵繼續(xù)，然后輸入初始密碼，緊接著輸入測試人的數(shù)量n,其次依次輸入測試人的密碼，最后輸入報數(shù) 上限值m ,完成后將進(jìn)行結(jié)果的輸出。三、測試報告1、測試用例.測試數(shù)據(jù)：m的初值為20,n=7,7個人的密碼依次為3,1,7,2,4,7,4,首先m=6, 則正確的輸出是什么？2、測試結(jié)果welcome精品約瑟夫環(huán)程序設(shè)計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) 避第第第第第第第戴:&靛 正測入人人人人人人人日13、分析與探討無論是用鏈表實現(xiàn)還是用數(shù)組實現(xiàn)都有一個共同點：要模擬整個游戲過程，不僅程序?qū)懫饋肀容^煩，而且時間復(fù)雜度高達(dá)O(nm),當(dāng)n, m非常大(例如上百萬，上千萬)的時候，幾乎是沒有辦法在短時間內(nèi)出結(jié)果的。我們注意到原問題僅僅是要求出最后的勝利者的序號，而不是要讀者模擬整個過程。因此如果要追求效率，就要打破常規(guī)，實施一點數(shù)學(xué)策略。為了討論方便，先把問題稍微改變一下，并不影響原意：問題描述

9、：n個人(編號0(n-1),從0開始報數(shù)，報到m-1的退出welcome精品,剩下的人繼續(xù)從0開始報數(shù)。求勝利者的編號。我們知道第一個人（編號一定是（m-1）%n）出列之后，剩下的n-1個人組 成了一個新的約瑟夫環(huán)（以編號為k=m%n的人開始）：k k+1 k+2 . n-2, n-1,0, 1,2, . k-2并且從k開始報0。現(xiàn)在我們把他們的編號做一下轉(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）個人報數(shù)的子問題，假如我們知道這個子問題的解：例如x是最終的勝利者，那么根據(jù)上面這個表把這個x變回去不剛好就是n個人情況的解嗎？ ！ ！變回去的公式很簡單，相信大家都可以推 出來：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)個人報數(shù)

11、的問題的解？對，只要知道(n-2)個人的解就行 了。(n-2)個人的解呢？當(dāng)然是先求(n-3)的情況-這顯然就是一個倒推問 題！好了，思路出來了，下面寫遞推公式：令f表示i個人玩游戲報m退出最后勝利者的編號，最后的結(jié)果自然是 fn.遞推公式：f1=0;fi=(fi-1+m)%i; (i>1)有了這個公式，我們要做的就是從1-n順序算出f的數(shù)值，最后結(jié)果是 fn o我們輸出fn由于是逐級遞推，不需要保存每個，程序也是異常簡單： (注意編號是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 ;)時間復(fù)雜度為O(n),相對于模擬算法已經(jīng)有了很大的提高。算 n, m等 于一百萬，一千萬的情況不是問題了。可見，適當(dāng)?shù)剡\用數(shù)學(xué)策略，不僅可 以讓編程變得簡單，而且往往會成倍地提高算法執(zhí)行效率。參照上面提供的思路，我認(rèn)為可以類似的得到一個更易于明白的方法， 設(shè)有(1,2,3,，k-1 , k, k+1 ,

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

14、=0)fn=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)然，我們還可以用遞歸方法解決此問題：#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è)計的題目是：約瑟夫環(huán)，通過對該題目 的設(shè)計，我加深了對數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的理解，進(jìn)一步地理解和掌握 了課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，尤其是對單循環(huán)鏈表上基本運算的實 現(xiàn)，學(xué)會了如何把學(xué)到的知識用于解決實際問題，鍛煉了自己動手的能 力。通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，我感受最深的就是對于

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

17、累了經(jīng)驗，鍛煉了自己分析問題，解 決問題的能力，并學(xué)會了如何將所學(xué)的各課知識融會，組織起來進(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 個人int i; int m; /初始報數(shù)上限值int j, k, s, u;char ch;char mima100="007

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

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

21、;請再次輸入 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("請輸入第%d個人的密碼：",i); /*輸入每個人所持有的密碼值*/scanf("%d”,&(p->password);p->number=i;p->next=head; /*形成循環(huán)鏈表*/p=head;printf("請輸入數(shù)字 m:");scanf("%d",&m);printf("密碼是:")；for (j=1;j<=n;j+) /*輸出各人的編號*/(for(i=1;i<m;i+,p=p->next);welcome精品m=p->