約瑟夫環(huán)(Joseph)問題

約瑟夫環(huán)（Joseph）問題

姓名：學(xué)號：

系別：指導(dǎo)老師：目錄1.程序設(shè)計目標2.問題描述3.概要設(shè)計4.詳細設(shè)計5.測試報告6.總結(jié)1.程序設(shè)計目標約瑟夫(Joseph)環(huán)問題是數(shù)據(jù)結(jié)構(gòu)中的經(jīng)典問題，在學(xué)習(xí)線性表的時候常用到約瑟夫環(huán)問題，通過學(xué)習(xí)約瑟夫環(huán)問題能提高對線性表的理解和應(yīng)用能力。約瑟夫環(huán)問題可利用多種方法求解，本設(shè)計主要利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。同時，通過查找C語言相關(guān)知識，分析約瑟夫環(huán)問題與循環(huán)鏈表之間的聯(lián)系，然后形成算法的思想對約瑟夫環(huán)問題用C語言進行編譯實現(xiàn)。2.問題描述編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個人開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設(shè)計一個程序來求出出列順序。2.問題描述圖1Joseph環(huán)示意圖3.概要設(shè)計本設(shè)計實現(xiàn)約瑟夫環(huán)問題主要由三個模塊構(gòu)成：主模塊、鏈表的創(chuàng)建、輸出序列。圖2各模塊調(diào)用關(guān)系3.概要設(shè)計單向循環(huán)鏈表：將單鏈表尾節(jié)點的指針端由空指針改為指向頭節(jié)點，使整個單鏈表形成一個環(huán)。圖3所示為帶頭節(jié)點的循環(huán)單鏈表。

圖3循環(huán)單鏈表

4.詳細設(shè)計鏈表的創(chuàng)建主要用到CreateLinkList()函數(shù)，首先從主函數(shù)main()函數(shù)中讀取個人信息，包括人數(shù)、每個人持有的密碼以及第一個報數(shù)值，然后開始創(chuàng)建循環(huán)單鏈表來存儲每個人的密碼，創(chuàng)建完成后返回main()函數(shù)。

4.詳細設(shè)計圖4鏈表的生成

4.詳細設(shè)計輸出出對序列主要用到Joseph()函數(shù)，首先從創(chuàng)建好的循環(huán)鏈表中按初始密碼依次找出對應(yīng)出列序列，然后依次輸出每個人持有的密碼c，當所有密碼輸出后，刪除相應(yīng)的節(jié)點，并釋放所占有的存儲空間，返回主函數(shù)。

4.詳細設(shè)計圖5輸出序列的實現(xiàn)5.測試報告//尾插入法創(chuàng)建鏈表voidCreateLinkList(LinkList*&L,intn){ LinkList*s,*c; inti; L=(LinkList*)malloc(sizeof(LinkList));//創(chuàng)建頭節(jié)點

c=L; printf("請輸入第1個元素的密碼:"); scanf("%d",&(c->cipher)); c->data=1; for(i=2;i<=n;i++) { s=(LinkList*)malloc(sizeof(LinkList)); printf("請輸入第%d個元素的密碼:",i); scanf("%d",&(s->cipher)); s->data=i; c->next=s; c=s; } c->next=L;}5.測試報告voidJoseph(LinkList*&L,intm,intn)//出列{ LinkList*s,*c; inti=1; c=L; printf("輸出出對序列:"); while(n) { while(i!=m) { s=c; c=c->next; i++; } printf("%-3d",c->data); m=c->cipher; s->next=c->next; free(c); c=s->next; i=1; n--; } printf("\n");}5.測試報告圖6Joseph環(huán)編譯結(jié)果

6.總結(jié)通過本次的課程設(shè)計，我了解到約瑟夫環(huán)問題是由古羅馬著名的史學(xué)家Josephus提出的問題基礎(chǔ)上演變而來，所以也稱為Josephus問題。Jo