c語言實現(xiàn)約瑟夫環(huán)問題.

1、(一)基本問題1 .問題描述設(shè)有編號為12月的n (n0)個人圍成一個圈，每個人持有一個密碼hi。從第一個 人開始報數(shù)，報到m時停止報數(shù)，報m的人出圈，再從他的下一個人起重新報數(shù)，報到m 時停止報數(shù)，報m的出圈，如此下去，直到所有人全部出圈為止。當(dāng)任意給定n和 m后，設(shè)計算法求n個人出圈的次序。建立模型，確定存儲結(jié)構(gòu)。對任意n個人，密碼為m, 實現(xiàn)約瑟夫環(huán)問題。2 .數(shù)據(jù)結(jié)構(gòu)設(shè)計首先，設(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)類型：struct Node(iiit da

2、ta;Node *next;；其次，建立一個不帶頭結(jié)點的循環(huán)鏈表并由頭指針加st指示3 .算法設(shè)計1、工作指針first, r, s, p, q初始化2、輸入人數(shù)(n)和報數(shù)(m)3、循環(huán)n次，用尾插法創(chuàng)建鏈表Node *q;fbr(int i=l;i data =i;p-next=NULL;L=q=p; elseq-next=p;q=q-next;)q-next=L;if(L!=NULL)ieturn(L);4、輸入報數(shù)的起始人號數(shù)k;5、Node *q = new Node;計數(shù)器初始化 i=l;6、循環(huán)n次刪除結(jié)點并報出位置(其中第一個人后移k個) 當(dāng)inext;刪除p結(jié)點的后一結(jié)點qq

3、=p-next;p-next=q-next;*L = p-next;報出位置后Delete q;計數(shù)器i+；運行流程圖代碼和相關(guān)解釋#iiicludeusing namespace std;stiuct Node 循環(huán)節(jié)點的定義(iiit data，/編號Node *next;；Node *CreateList(Node *L,int&m);建立約瑟夫環(huán)函數(shù)void Joseph(Noden,iiit m);輸出每次出列號數(shù)函數(shù)Node *DeleteList(Node i,Node *q)尋找每次出列人的號數(shù) int LengthList(Node *L);計算環(huán)上所有人數(shù)函數(shù)void ma

4、in。/ 主函數(shù)在主函數(shù)中，完成人數(shù)(n)和報數(shù)(m)的輸入和工作指針的初始化(Node *L;L=NULL; 初始化尾指針iiit n, m;coutw”請輸入人數(shù)N： ”；cinn;環(huán)的長度if(nl)coutvv”請輸入正整數(shù)! ”;人數(shù)異常處理else(coutvv請輸入所報數(shù)M：ciiim;if(nil)coutv “請輸入正整數(shù)! ”;號數(shù)異常處理else(L=CreateList(L,n,m);重新給尾指針賦值Joseph(L,n,m);)system(pause);)Node *CreateList(Node *L,int&m)建立一個約瑟夫環(huán)(尾插法)(Node *q;fbr

5、(int i=l ;idata=i;p-next=NULL;if(i= 1) L=q=p; 工作指針的初始化 else(q-next=p;q=q-next;)q-next=L;if(L!=NULL)retum(L); 返回尾指針else coutvv尾指針異常! endl;尾指針異常處理 )void Joseph(Node n,iiit m)輸出每次出列的人(iiit k;coutw”請輸入第一個報數(shù)人：；cink;if(kl|kn)coutv“請輸入之間的數(shù)Wendi;else ( coutHn 出列順序:n”；fbr(int i=l;idataendl;delete q;釋放出列人的存儲空

6、間)coutvv”最后一個出列號數(shù)是：”dataendl;輸出最后出列人的號數(shù))Node *DeleteList(Node i,Node *q) /尋找每次出列的人(if(i=l) i+=LengthList(*L);順序依次出列情況的處理方式Node *p;P=*L；iiit j=0;while(jnextJ-H-;q = p-next;p-next=p-next-next;*L = p-next;return(q);)int LengthList(Node *L)計算環(huán)上的人數(shù)(if(L)coutv尾指針錯誤!Wendi; 異常處理else(int i=l;Node *p=L-next;w

7、liile(p!=L)(i+;p=p-next;return(i);)復(fù)雜度分析：fbr(int i= 1 ;inmnbei-i;p-next=NULL; L=q=p;else(q-next=p; q=q-next;)時間好雜度：O (n)if(i=l) i+=LengtliList(*L);Node *p;P=*L； iiitj=O;while(jnextj-H-； q = p-next;p-next=p-next-next;*L = p-next;return(q);時間復(fù)雜度：O(*)算法的空間復(fù)雜度：O (n2)4 .界面設(shè)計請輸入報數(shù)人數(shù)n 請輸入所報數(shù)M 請輸入第一個報數(shù)人以下列出

8、依次報數(shù)的結(jié) 果5 .運行、測試與分析E -D:新簸件夾(2)Debug12,exe-Bw現(xiàn)命黜黜黜黜嘉請請請出號號號號號最請(二)采用順序存儲結(jié)構(gòu)如何實現(xiàn)約瑟夫環(huán)問題代碼和解釋include #iiiclude#iiicludedefine MaxSize 50typedef char Elemlype;typedef stnict Seqlist線性表順序存儲結(jié)構(gòu)定義ElemType *elemMaxSize存放順序表數(shù)據(jù)元素int length;當(dāng)前長度*JSeqlist; 線性表存儲結(jié)構(gòu)類型名JSeqlist Iiit_SeqList(void)順序表初始化JSeqlist L;L=(

9、JSeqlist)nialloc(sizeof(stnict Seqlist);if(L!=NULL)L-length=0;elsepnntf(超出范圍！ ”)；return L;ElemType *Locate_SeqList(JSeqlist L,int p)查找線性表中下標(biāo)為P的元素if(p=O&L-length)retuni(L-elemp);elseprintf(順序表中不存在相關(guān)元素)return NULL;)int Iiisert_SeqList(JSeqlist L,int i,ElemType *x)在順序表中指定元素前插入Xintj;if(L-length=MaxSize)

10、/L.lengtli 是最后一個元素的位置pnntf(線性表已滿，無法進(jìn)行插入操作！ ！return 0;)if(iL-length)pnntf(”插入位置不對，超出順序表長度也”)；return 0;)if(i=0)L-elemi=x;L-length=L-length+l;return 1;)fbr(j=L-lengthJ=iJ)L-elemj=x;L-length-H-;return 1;int Delete_JSeqlist( J Seqlist L,iiit i)在順序表中刪除第i個元素intj;if(iL-length-1)(pnntf(刪除位置不對，超出順序表的長度啦證”)；re

11、turn 0;)fbr(j=i Jlengtli-l J+)L-elemj =L-elemj+l ;L-length;return 1;void josephus(JSeqlist L,iiit start,int m)/josephus問題求解的非常牛逼的函數(shù)int s,i；ElemType *w;s=start-l;fbr(i=L-length;iO;i) (s=(s+m-l)%i;w=Locate_SeqList(L,s);printf(出列人員為：%snH,w);Delete_JSeqlist(L,s);)int main (void)(JSeqlist Josephus;int n,

12、m,i,k,s;Josephus=Int_SeqListO；順序表初始化printf(約瑟夫環(huán)問題順序表求解愚人節(jié)特別版nn);printf(請輸入本問題中總?cè)藬?shù)m=)； scanfC%d,&n);printf(請輸入本問題開始人員的位置S=);scanfC%d,&s);printf(請輸入本問題的計數(shù)值m=);scanf(%d,&m);piintf(請輸入本問題中這些人的名字n”)； fbr(i=O;ielemi=(ElemType *)calloc(l O,sizeof(char);scanf(%sJosephus-elemi);k=Iiiseil_SeqList(Josephus,i,J

13、oseplius-elemi);if(k=O)exit(l);)josephus(Josephus,s,m);fi.ee( Josephus);getchaiQ;return 0;)運行結(jié)果continue名名名名名名。afrs&afr曲霸莖曉翠日(三)密碼不同#include struct CList(int password;int number;struct CList *next;；typedef stnict CList CNode;typedef CNode *CLink;CLiiik CreateList(int lengtli) (CLink head;CLink before

14、;CLink new_node;inti;head=new CNode;if(head=NULL)return NULL;cout Please Input Password 1 endl;ciii head-password;head-numbei-l;head-next=NULL;befbre=head;fbr(i= 1 ;inumber = i+l;cout Please Input Password new_node-number endl; ciii new_node-password;new_node-next = NULL;befbre-next=new_node;befbre=

15、new_node;)new_node-next =head;return head;)int maiiiQ(CLink head;CLink ptr,back,last; intcout Please Input tlie Number of Persons: endl;cin n;cout Please Input tlie First Password M: endl;cin m;head=CreateList(n);pti-head;fbr(i=O;in;i-H-)(for(j=0jnext;)cout VV第vvi+l”個出列的編號為:“vvptr-numbeiWendl; m=ptr-password;if(pti-=head)last=head;while(last-next! =head) last=last-next;last-next=liead-next;delete ptr;pti-last-next;head