死隊問題(五種算法實現(xiàn)的約瑟夫環(huán))

1、敢死隊問題2011年12月30日 目錄摘 要31課題背景的介紹31.1 課題背景31.2 目的32需求分析42.1 數(shù)據(jù)需求分析42.2 功能需求分析43系統(tǒng)總體設(shè)計53.1 系統(tǒng)模塊劃分53.2 系統(tǒng)模塊結(jié)構(gòu)圖54系統(tǒng)詳細設(shè)計64.1 系統(tǒng)操作界面64.2 各模塊功能實現(xiàn)64.2.1順序存儲64.2.2單循環(huán)鏈表84.2.3 數(shù)組94.2.4 循環(huán)隊列104.2.5 遞歸114.2.6 主函數(shù)125總結(jié)156參考文獻167附錄167.1人員分工167.2 代碼16摘 要敢死隊問題是根據(jù)著名的“約瑟夫環(huán)”演變而來的敢死隊問題的處理與計算來設(shè)計的一個系統(tǒng)。整個系統(tǒng)從符合操作簡便、界面友好、靈活、

2、實用、安全的要求出發(fā)，完成敢死隊問題的全過程，包括五種數(shù)據(jù)結(jié)構(gòu)算法（順序表、單循環(huán)鏈表、數(shù)組、循環(huán)隊列、遞歸）、數(shù)據(jù)的處理與計算、數(shù)據(jù)的分析、結(jié)果的輸出。本課程主要介紹了本課題的開發(fā)背景，所要完成的功能和開發(fā)的過程。重點說明了系統(tǒng)的設(shè)計思路、總體設(shè)計、各個功能模塊的設(shè)計與實現(xiàn)方法。關(guān)鍵詞：敢死隊問題，C語言，數(shù)據(jù)結(jié)構(gòu)，順序存儲結(jié)構(gòu)，單鏈表存儲結(jié)構(gòu)，數(shù)組，隊列，遞歸1 課題背景的介紹1.1 課題背景有M個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(shù)數(shù)的辦法來決定哪個戰(zhàn)士去執(zhí)行任務(wù)。如果前一個戰(zhàn)士沒完成任務(wù)，則要再派一個戰(zhàn)士上去。現(xiàn)給每個戰(zhàn)士編一個號，大家圍坐成一圈，隨便從某一個戰(zhàn)士開

3、始計數(shù)，當(dāng)數(shù)到5時，對應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參加下一輪計數(shù)。如果此戰(zhàn)士沒完成任務(wù)，再從下一個戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。排長是不愿意去的，假設(shè)排長為1號，請你設(shè)計一程序，求出從第幾號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務(wù)。要求：至少采用兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實現(xiàn)。1.2 目的本課題運用C語言進行開發(fā)，C語言能夠簡單的進行編譯一些程序，來實現(xiàn)對一些問題的解決。它雖然比較簡單的處理一些問題，但卻有更高的效率。它能夠被大多數(shù)用戶所接受，因為它能夠呈現(xiàn)出清晰的界面，是人們能夠很好的理解。能在一些方面給人們更好的服務(wù)，成為人們的

4、好幫手。經(jīng)過這一個學(xué)期對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，我們都學(xué)到了不少東西，可能有些學(xué)的還不夠理想，但無論如何這些知識都為我們的下一步學(xué)習(xí)打下了堅實的基礎(chǔ)。通過做這么個課程設(shè)計將理論聯(lián)系實際，使我更好的理解課本上的知識，發(fā)現(xiàn)不足之處，然后更好的學(xué)習(xí)，使我的編程能力有進一步的提高。2 需求分析本程序輸入隊伍人數(shù)n為任意的，最終輸出記數(shù)的初始位置，首先輸入一個報數(shù)上限m，當(dāng)達到報數(shù)上限時，那名士兵出列執(zhí)行任務(wù)，從下個人開始記數(shù)，再次循環(huán)，直到只剩一人，得到其在隊伍中的位置，通過數(shù)學(xué)思想求得題目要求即隊長為首的情況下 需要記數(shù)初始位置。2.1 數(shù)據(jù)需求分析由于約瑟夫環(huán)模擬的是人的報數(shù)操作，固本系統(tǒng)的主要處理的數(shù)據(jù)

5、是正整數(shù)。正整數(shù)信息包括:隊伍的人數(shù)，報數(shù)的數(shù)值，報數(shù)開始的位置。本程序任務(wù)是通過輸入任意隊伍人數(shù)n和報數(shù)上限m，輸出使排長最后一個執(zhí)行任務(wù)而開始記數(shù)的初始位置。首先輸入隊伍人數(shù)n，然后輸入報數(shù)上限m(m<=n),從1號開始報數(shù)，當(dāng)達到報數(shù)上限時，那名士兵出列執(zhí)行任務(wù)，從下個人開始記數(shù)，再次循環(huán)，直到只剩一人，得到其在隊伍中的位置，記下該位置視為排長位置，則1號即可視為最先報數(shù)的人，通過數(shù)學(xué)計算即可獲得所求(z=n-k+2)。2.2 功能需求分析本系統(tǒng)主要實現(xiàn)對學(xué)生成績信息進行管理，需要實現(xiàn)以下幾個方面的管理功能：（1）創(chuàng)建存儲結(jié)構(gòu)：創(chuàng)建順序表，創(chuàng)建單循環(huán)鏈表，創(chuàng)建數(shù)組，創(chuàng)建循環(huán)隊列。（

6、2）數(shù)據(jù)的輸入：把隊伍的人數(shù)，報數(shù)的數(shù)值輸入。（3）數(shù)據(jù)的處理；對隊伍的人數(shù)，報數(shù)的數(shù)值進行計算。（4）結(jié)果的輸出：把報數(shù)開始的位置輸出。3 系統(tǒng)總體設(shè)計3.1 系統(tǒng)模塊劃分本系統(tǒng)主要是對敢死隊問題的處理，包括了創(chuàng)建存儲結(jié)構(gòu)、數(shù)據(jù)的輸入、數(shù)據(jù)的處理、結(jié)果的輸出等功能。整個系統(tǒng)分為以下幾個模塊。1、操作界面模塊 本模塊提供操作界面的信息輸出模式。2、順序存儲結(jié)構(gòu)模塊 本模塊用于通過運用順序結(jié)構(gòu)模塊來計算結(jié)果。3、單鏈表存儲結(jié)構(gòu)模塊 本模塊用于通過運用單鏈表結(jié)構(gòu)模塊來計算結(jié)果。4、數(shù)組模塊 本模塊用于通過運用數(shù)組結(jié)構(gòu)模塊來計算結(jié)果。5、循環(huán)隊列模塊 本模塊用于通過運用循環(huán)隊列模塊來計算結(jié)果6、遞歸

7、實現(xiàn)模塊 本模塊通過遞歸思想來實現(xiàn)計算結(jié)果3.2 系統(tǒng)模塊結(jié)構(gòu)圖根據(jù)系統(tǒng)功能設(shè)計，對應(yīng)的系統(tǒng)模塊結(jié)構(gòu)圖如圖所示敢死隊問題功能模塊順序表存儲循環(huán)隊列遞歸單循環(huán)鏈表數(shù)組實現(xiàn)數(shù)據(jù)處理數(shù)據(jù)處理數(shù)據(jù)處理數(shù)據(jù)處理數(shù)據(jù)處理退出4 系統(tǒng)詳細設(shè)計4.1 系統(tǒng)操作界面由于敢死隊問題處理的是數(shù)字的調(diào)度問題，固不需要一些復(fù)雜的功能，因此根據(jù)實際需求設(shè)計了如下比較簡潔的界面供用戶使用。該界面簡單明了，根據(jù)界面上的提示信息，用戶能很快的使用該系統(tǒng)。4.2 各模塊功能實現(xiàn)4.2.1順序存儲(1)算法思想將有n個人的隊列存入順序表中，然后從順序表的第一個元素開始按間隔人數(shù)m讀取數(shù)據(jù)，當(dāng)報數(shù)報到m的時候出隊，同時將該位置上的值

8、置為0，以該位置的下一個(值為非0)位置為起始位置，以此循環(huán)報數(shù)直到剩下最后一個數(shù)為止，假設(shè)最后這個數(shù)為k。通過數(shù)學(xué)運算z=n-k+2，得到第一個報數(shù)的人的編號。注意：在報數(shù)的過程中如果出現(xiàn)位置上的值為0的情況，則跳過該位置，繼續(xù)往下報數(shù)，直到有m個非0的數(shù)為止。(2)代碼實現(xiàn)#include <stdio.h>#include <math.h>#include <stdlib.h>const int max=100;int arraymax,num,Templete;/Templete保存遞歸算法的返回值/以下數(shù)組操作都是從下標(biāo)0開始，真正的數(shù)據(jù)編號是從1

9、開始#pragma region "用順序表實現(xiàn)"typedef struct CirCleNodeint datamax;int last;/順序表的大小*CNode;CNode CreateCirCleNode(int n)/往順序表中讀入數(shù)據(jù)CNode cn;cn=new CirCleNode;int i;for(i=0;i<n;i+)cn->datai=i+1;cn->last=n;return cn;int PushCirCleNode(CNode cn,int m)/順序表出隊int count=0,i=0,num=0,j=0,Tempmax;

10、while(count<cn->last)while(num<m && count<cn->last)i=i%cn->last+1;/約瑟夫環(huán)的每輪起始位置if(cn->datai-1)/非0的時候讓計數(shù)器自加num+;count+;Tempj+=cn->datai-1;cn->datai-1=0;/出隊的時候置為0num=0;/計數(shù)器清零 /*for(j=0;j<cn->last;j+)printf("-%d",Tempj);*/return Tempcn->last-1;#pragm

11、a endregion "順序表執(zhí)行"4.2.2單循環(huán)鏈表(1)算法思想創(chuàng)建不帶頭結(jié)點的單循環(huán)鏈表，創(chuàng)建完鏈表之后返回鏈表的第一個結(jié)點指針。從第一個結(jié)點開始按照以m為間隔，找到要出隊的結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點，將前驅(qū)結(jié)點的下一個結(jié)點指針指向其后繼結(jié)點，同時刪除該結(jié)點，以此循環(huán)下去直到該循環(huán)鏈表只剩下最后一個結(jié)點為止。(2)代碼實現(xiàn)#pragma region "單循環(huán)鏈表實現(xiàn)"typedef struct nodeint data;struct node *next;*Node;Node CreteNode(int n)/創(chuàng)建不帶頭結(jié)點單鏈表Node p

12、,q,t;int i;t=p=new node;p->data=1;for(i=2;i<=n;i+)q=new node;/申請新的結(jié)點插入鏈表q->data=i;p->next=q;p=q;/printf("-%d",p->data); p->next=t;return t;int DeleteNode(Node nd,int m)/出隊Node t;int i;while(nd->next!=nd)for(i=1;i<m-1;i+)/找到要刪除結(jié)點的前一個結(jié)點nd=nd->next;t=nd->next;/pr

13、intf("->%d",t->data);nd->next=t->next; delete t;nd=nd->next;/將結(jié)點指向被刪除結(jié)點后一個結(jié)點return nd->data;#pragma endregion "單循環(huán)鏈表"4.2.3 數(shù)組(1)算法思想用數(shù)組實現(xiàn)敢死隊問題的關(guān)鍵在于用數(shù)組的下標(biāo)構(gòu)造一個虛假循環(huán)，從第一節(jié)點開始，以人數(shù)m為間隔，找到要刪除結(jié)點的下標(biāo)k，將k以后的所有隊員依次往前移動一個位置。以此循環(huán)下去直到數(shù)組中只剩下一個數(shù)為止。(2)代碼實現(xiàn)#pragma region "數(shù)組實現(xiàn)

14、敢死隊問題"int Array(int n,int m)int i,temp,j;int k=0;/假設(shè)從第一個開始報數(shù)int Jspmax;for(i=0;i<n;i+)Jspi=i+1;for(i=n;i>=1;i-)k=(k+m-1)%i;/用數(shù)組的下標(biāo)構(gòu)造一個虛假循環(huán) temp=Jspk;/temp保存要出隊的值for(j=k;j<i;j+)/將k以后的數(shù)組往前移Jspj=Jspj+1;/printf("-%d",temp); return temp;#pragma endregion "數(shù)組列實現(xiàn)"4.2.4 循環(huán)隊

15、列(1)算法思想隊列操作的最主要思想是先進先出，并且每次操作都是從隊首刪除，隊尾進隊。創(chuàng)建循環(huán)隊列，從結(jié)點的第一個結(jié)點開始按照m人數(shù)間隔查找到要出隊的結(jié)點，并且修改頭結(jié)點的指針使其指向該結(jié)點，同時將該結(jié)點上的數(shù)據(jù)值修改為0。依次循環(huán)下去查找余下的非零結(jié)點，直到剩下一個非零結(jié)點為止。注意：1、隊列的隊首指的是隊中第一個元素的前一個結(jié)點，因此在查找之前，先將頭結(jié)點的指針指向第一個結(jié)點。2、在報數(shù)的過程中如果出現(xiàn)位置上的值為0的情況，則跳過該位置，繼續(xù)往下報數(shù)，直到有m個非0的數(shù)為止。(2)代碼實現(xiàn)/隊列操作是先進先出，且每次刪除隊首，隊尾進#pragma region "循環(huán)隊列實現(xiàn)&q

16、uot;typedef struct Sequeint datamax;int front;int rear; *SequeNode;/置空隊void Iniqueue(SequeNode p)p->front=0;p->rear=0;int AddQueue(SequeNode p,int n)/入隊if(p->rear+1)%n=p->front)return 0;elsefor(int i=1;i<=n;i+)p->rear=(p->rear+1)%n;p->datap->rear=i;/printf("-%d",

17、p->datap->rear);return 1; int outQueue(SequeNode p,int n,int m)int temp=0,k=0,Tempmax;if(p->rear=(p->front+1)%n)return 0;elsep->front=(p->front+1)%n;for(int i=0;i<n;i+)while(temp<m)/找到被刪除結(jié)點的后一結(jié)點p->front=(p->front+1)%n;if(p->front=0)/當(dāng)頭結(jié)點的下標(biāo)是0時改變其下標(biāo)p->front=n;if(p-

18、>datap->front-1!=0)/非零結(jié)點時讓temp+temp+;Tempi=p->datap->front-1;p->datap->front-1=0;/把找到的那個結(jié)點置零/printf("-%d",Tempi);temp=0;return Tempn-1;#pragma endregion "循環(huán)隊列"4.2.5 遞歸(1)算法思想?yún)⒄諗?shù)組實現(xiàn)。(2)代碼實現(xiàn)#pragma region"遞歸實現(xiàn)敢死隊問題"/Templete保存最后的返回值,results保存下標(biāo)void Creat

19、eArray(int n)int i;for(i=0;i<n;i+)arrayi=i+1;int SearchArray(int n,int m)/思路參照數(shù)組int results;if(n>num)return 0;elseif(n=1)results=0;results=(SearchArray(n+1,m)+m-1)%n;Templete=arrayresults;for(int j=results;j<n;j+)arrayj=arrayj+1;return Templete,results;#pragma endregion"遞歸結(jié)束"4.2.6

20、 主函數(shù)(1)核心算法運用數(shù)學(xué)思想求得敢死隊的最初報數(shù)位置。假設(shè)總?cè)藬?shù)為n，報數(shù)間隔為m，最后一個出隊人的標(biāo)號為k，第一個出隊人的下標(biāo)為t，則t=n-k+2。(1)代碼實現(xiàn):int main()int push,flag;/num總?cè)藬?shù),以push出隊int result=0,temp=0;/result最后出隊的人的編號SequeNode SNode=new Seque;printf("*敢死隊問題*n");printf("*n");printf("請輸入總?cè)藬?shù):");scanf("%d",&num);p

21、rintf("*n");printf("請輸入間隔人數(shù):");scanf("%d",&push);if(num<1 | push<1)printf("輸入錯誤請重新輸入:n");exit(1);if(num=1)printf("要使排長安全則應(yīng)該從第%d號開始.n",num);exit(1);printf("*n");printf("根據(jù)菜單提示選擇相應(yīng)的算法n");printf("*n");printf("

22、;1、順序表 2、鏈表 3、數(shù)組 4、隊列 5、遞歸 6、退出n");while(scanf("%d",&flag)if(flag=6)break;switch(flag)case 1:CNode cnode;cnode=CreateCirCleNode(num); result=PushCirCleNode(cnode,push);break;case 2:Node LNode; LNode=CreteNode(num); result=DeleteNode(LNode,push);break;case 3:result=Array(num,push);

23、break;case 4: Iniqueue(SNode);AddQueue(SNode,num);result=outQueue(SNode,num,push);break;case 5:CreateArray(num); SearchArray(1,push);result=Templete;break;default :result=0;printf("<<請根據(jù)菜單提示操作>>n");break;if(result!=0)temp=(num-result+2)%num;/運用數(shù)學(xué)思想求出第一個開始位置if(temp=0)printf(&quo

24、t;要使排長安全則應(yīng)該從第%d號開始報數(shù).n",num);elseprintf("要使排長安全則應(yīng)該從第%d號開始報數(shù).n", temp);printf("*n");return 0;(2)函數(shù)執(zhí)行結(jié)果測試數(shù)據(jù)1：測試數(shù)據(jù)2：5 總結(jié)本課程設(shè)計敢死隊問題處理系統(tǒng)，從開發(fā)到實現(xiàn)再到最后的測試結(jié)果來看，基本上實現(xiàn)了敢死隊的五大算法功能模塊：順序存儲、單循環(huán)鏈表、數(shù)組、循環(huán)隊列、遞歸。并達到操作過程中的直觀，方便，使用。系統(tǒng)采用模塊化的程序設(shè)計，便于系統(tǒng)功能的組合和修改。另外通過本次的課程設(shè)計使我對數(shù)據(jù)結(jié)構(gòu)與算法這門課程有了進一步的認識，通過系統(tǒng)中的

25、發(fā)現(xiàn)的問題，再到解決問題這個階段，讓我體會到了編程的樂趣。經(jīng)過這一個學(xué)期對數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)，我們都學(xué)到了不少東西，可能有些學(xué)的還不夠理想，但無論如何這些知識都為我們的下一步學(xué)習(xí)打下了堅實的基礎(chǔ)。通過做這么個課程設(shè)計將理論聯(lián)系實際，使我更好的理解課本上的知識，發(fā)現(xiàn)不足之處，然后更好的學(xué)習(xí)，使我的編程能力有進一步的提高。6 參考文獻c語言-譚浩強數(shù)據(jù)結(jié)構(gòu)與算法-寧正元7. 代碼#include <stdio.h>#include <math.h>#include <stdlib.h>const int max=100;int arraymax,num,Tem

26、plete,push;/Templete保存遞歸算法的返回值/以下數(shù)組操作都是從下標(biāo)0開始，真正的數(shù)據(jù)編號是從1開始#pragma region "用順序表實現(xiàn)"typedef struct CirCleNodeint datamax;int last;/順序表的大小*CNode;CNode CreateCirCleNode(int n)/往順序表中讀入數(shù)據(jù)CNode cn;cn=new CirCleNode;int i;for(i=0;i<n;i+)cn->datai=i+1;cn->last=n;return cn;int PushCirCleNode

27、(CNode cn,int m)/順序表出隊int count=0,i=0,num=0,j=0,Tempmax;while(count<cn->last)while(num<m && count<cn->last)i=i%cn->last+1;/約瑟夫環(huán)的每輪起始位置if(cn->datai-1)/非0的時候讓計數(shù)器自加num+;count+;Tempj+=cn->datai-1;cn->datai-1=0;/出隊的時候置為0num=0;/計數(shù)器清零 /*for(j=0;j<cn->last;j+)printf(

28、"-%d",Tempj);*/return Tempcn->last-1;#pragma endregion "順序表執(zhí)行"#pragma region "單循環(huán)鏈表實現(xiàn)"typedef struct nodeint data;struct node *next;*Node;Node CreteNode(int n)/創(chuàng)建不帶頭結(jié)點單鏈表Node p,q,t;int i;t=p=new node;p->data=1;for(i=2;i<=n;i+)q=new node;/申請新的結(jié)點插入鏈表q->data=i;

29、p->next=q;p=q;/printf("-%d",p->data); p->next=t;return t;int DeleteNode(Node nd,int m)/出隊Node t;int i;while(nd->next!=nd)for(i=1;i<m-1;i+)/找到要刪除結(jié)點的前一個結(jié)點nd=nd->next;t=nd->next;/printf("->%d",t->data);nd->next=t->next; delete t;nd=nd->next;/將結(jié)點指向

30、被刪除結(jié)點后一個結(jié)點return nd->data;#pragma endregion "單循環(huán)鏈表"#pragma region "數(shù)組實現(xiàn)敢死隊問題"int Array(int n,int m)int i,temp,j;int k=0;/假設(shè)從第一個開始報數(shù)int Jspmax;for(i=0;i<n;i+)Jspi=i+1;for(i=n;i>=1;i-)k=(k+m-1)%i;/用數(shù)組的下標(biāo)構(gòu)造一個虛假循環(huán) temp=Jspk;/temp保存要出隊的值for(j=k;j<i;j+)/將k以后的數(shù)組往前移Jspj=Jspj+

31、1;/printf("-%d",temp); return temp;#pragma endregion "數(shù)組列實現(xiàn)"/隊列操作是先進先出，且每次刪除隊首，隊尾進#pragma region "循環(huán)隊列實現(xiàn)"typedef struct Sequeint datamax;int front;int rear; *SequeNode;/置空隊void Iniqueue(SequeNode p)p->front=0;p->rear=0;int AddQueue(SequeNode p,int n)/入隊if(p->re

32、ar+1)%n=p->front)return 0;elsefor(int i=1;i<=n;i+)p->rear=(p->rear+1)%n;p->datap->rear=i;/printf("-%d",p->datap->rear);return 1; int outQueue(SequeNode p,int n,int m)int temp=0,k=0,Tempmax;if(p->rear=(p->front+1)%n)return 0;elsep->front=(p->front+1)%n;fo

33、r(int i=0;i<n;i+)while(temp<m)/找到被刪除結(jié)點的后一結(jié)點p->front=(p->front+1)%n;if(p->front=0)/當(dāng)頭結(jié)點的下標(biāo)是0時改變其下標(biāo)p->front=n;if(p->datap->front-1!=0)/非零結(jié)點時讓temp+temp+;Tempi=p->datap->front-1;p->datap->front-1=0;/把找到的那個結(jié)點置零/printf("-%d",Tempi);temp=0;return Tempn-1;#pragm

34、a endregion "循環(huán)隊列"#pragma region"遞歸實現(xiàn)敢死隊問題"/Templete保存最后的返回值,results保存下標(biāo)void CreateArray(int n)int i;for(i=0;i<n;i+)arrayi=i+1;int SearchArray(int n,int m)/思路參照數(shù)組int results;if(n>num)return 0;elseif(n=1)results=0;results=(SearchArray(n+1,m)+m-1)%n;Templete=arrayresults;for(

35、int j=results;j<n;j+)arrayj=arrayj+1;return Templete,results;#pragma endregion"遞歸結(jié)束"void function()printf("*n");printf("請輸入總?cè)藬?shù):");scanf("%d",&num);printf("*n");printf("請輸入間隔人數(shù):");scanf("%d",&push);if(num<1 | push<1)printf("輸入錯誤請重新輸入:n");exit(1);if(num=1)printf("要使排長安全則應(yīng)該從第%d號開始.n",num);exit(1);printf("*n");int main()int flag;/num總?cè)藬?shù),以push出隊int result=0,temp=0;/result最后出隊