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

實用文案（一）基本問題問題描述設(shè)有編號為 1,2,?,n的n（n＞0）個人圍成一個圈，每個人持有一個密碼 m。從第一個人開始報數(shù)，報到 m時停止報數(shù)，報 m的人出圈，再從他的下一個人起重新報數(shù)，報到m時停止報數(shù)，報 m的出圈，??，如此下去，直到所有人全部出圈為止。當(dāng)任意給定 n和m后，設(shè)計算法求 n個人出圈的次序。建立模型，確定存儲結(jié)構(gòu)。對任意 n個人，密碼為m，實現(xiàn)約瑟夫環(huán)問題。數(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)類型：structNode{intdata;Node*next;};其次，建立一個不帶頭結(jié)點的循環(huán)鏈表并由頭指針 first 指示算法設(shè)計標(biāo)準(zhǔn)文檔實用文案1、工作指針 first，r，s，p，q初始化2、輸入人數(shù)（n）和報數(shù)（m）3、循環(huán)n次，用尾插法創(chuàng)建鏈表Node*q;for(inti=1;i<=n;i++){Node*p;p=newNode;p->data=i;p->next=NULL;if(i==1)L=q=p;else{q->next=p;q=q->next;}}標(biāo)準(zhǔn)文檔實用文案q->next=L;if(L!=NULL){return(L);}4、輸入報數(shù)的起始人號數(shù) k;5、Node*q=newNode; 計數(shù)器初始化 i=1;6、循環(huán)n次刪除結(jié)點并報出位置（其中第一個人后移 k個）當(dāng)i<n 時移動指針 m-2次p=p->next;刪除p結(jié)點的后一結(jié)點 qq=p->next;p->next=q->next;*L=p->next;報出位置后 Deleteq;計數(shù)器i++;運行流程圖標(biāo)準(zhǔn)文檔實用文案開始輸入m和n創(chuàng)建鏈表Yk>n-1N移動指針p刪除p后一結(jié)點q指針p后移，k++輸出n結(jié)束代碼和相關(guān)解釋#include<iostream>usingnamespacestd;structNode// 循環(huán)節(jié)點的定義{intdata;// 編號Node*next;標(biāo)準(zhǔn)文檔實用文案};Node*CreateList(Node*L,int&n,int&m);// 建立約瑟夫環(huán)函數(shù)voidJoseph(Node*L,intn,intm);// 輸出每次出列號數(shù)函數(shù)Node*DeleteList(Node**L,inti,Node*q);// 尋找每次出列人的號數(shù)intLengthList(Node*L);// 計算環(huán)上所有人數(shù)函數(shù)voidmain()// 主函數(shù)在主函數(shù)中，完成人數(shù)（n）和報數(shù)（m）的輸入和工作指針的初始化{Node*L;L=NULL;// 初始化尾指針intn,m;cout<<" 請輸入人數(shù) N：";cin>>n;// 環(huán)的長度if(n<1){cout<<" 請輸入正整數(shù)!";}//人數(shù)異常處理else{cout<<" 請輸入所報數(shù) M：";cin>>m;標(biāo)準(zhǔn)文檔實用文案if(m<1){cout<<" 請輸入正整數(shù)!";}//號數(shù)異常處理else{L=CreateList(L,n,m);// 重新給尾指針賦值Joseph(L,n,m);}}system("pause");}Node*CreateList(Node*L,int&n,int&m)// 建立一個約瑟夫環(huán)（尾插法）{Node*q;for(inti=1;i<=n;i++){Node*p;p=newNode;p->data=i;p->next=NULL;標(biāo)準(zhǔn)文檔實用文案if(i==1)L=q=p;// 工作指針的初始化else{q->next=p;q=q->next;}}q->next=L;if(L!=NULL){return(L);}// 返回尾指針elsecout<<" 尾指針異常!"<<endl;// 尾指針異常處理}voidJoseph(Node*L,intn,intm)// 輸出每次出列的人{(lán)intk;cout<<" 請輸入第一個報數(shù)人： ";cin>>k;if(k<1||k>n){cout<<" 請輸入1-"<<n<<" 之間的數(shù)"<<endl;}標(biāo)準(zhǔn)文檔實用文案else{cout<<"\n 出列順序:\n";for(inti=1;i<n;i++){Node*q=newNode;if(i==1)q=DeleteList(&L,k+m-1,q);// 第一個出列人的號數(shù)elseq=DeleteList(&L,m,q);cout<<" 號數(shù)："<<q->data<<endl;deleteq;// 釋放出列人的存儲空間}cout<<" 最后一個出列號數(shù)是： "<<L->data<<endl;;// 輸出最后出列人的號數(shù)}}Node*DeleteList(Node**L,inti,Node*q)// 尋找每次出列的人{(lán)標(biāo)準(zhǔn)文檔實用文案if(i==1)i+=LengthList(*L);// 順序依次出列情況的處理方式Node*p;p=*L;intj=0;while(j<i-2){p=p->next;j++;}q=p->next;p->next=p->next->next;*L=p->next;return(q);}intLengthList(Node*L)// 計算環(huán)上的人數(shù){if(L){cout<<" 尾指針錯誤!"<<endl;}// 異常處理else{inti=1;Node*p=L->next;標(biāo)準(zhǔn)文檔實用文案while(p!=L){i++;p=p->next;}return(i);}}復(fù)雜度分析：for(inti=1;i<=n;i++){Node*p;p=newNode;p->number=i;p->next=NULL;if(i==1)L=q=p;else{q->next=p;q=q->next;標(biāo)準(zhǔn)文檔實用文案}時間復(fù)雜度：O（n）if(i==1)i+=LengthList(*L);Node*p;p=*L;intj=0;while(j<i-2){p=p->next;j++;}q=p->next;p->next=p->next->next;*L=p->next;return(q);時間復(fù)雜度：O（n2）算法的空間復(fù)雜度： O（n2）界面設(shè)計請輸入報數(shù)人數(shù) n請輸入所報數(shù) M請輸入第一個報數(shù)人——以下列出依次報數(shù)的結(jié)果標(biāo)準(zhǔn)文檔實用文案運行、測試與分析(二)采用順序存儲結(jié)構(gòu)如何實現(xiàn)約瑟夫環(huán)問題代碼和解釋#include<stdlib.h>#include<stdio.h>#include<malloc.h>#defineMaxSize50typedefcharElemType;標(biāo)準(zhǔn)文檔實用文案typedefstructSeqlist{//線性表順序存儲結(jié)構(gòu)定義ElemType*elem[MaxSize];// 存放順序表數(shù)據(jù)元素intlength;// 當(dāng)前長度}*JSeqlist;// 線性表存儲結(jié)構(gòu)類型名JSeqlistInt_SeqList(void){//順序表初始化JSeqlistL;L=(JSeqlist)malloc(sizeof(structSeqlist));if(L!=NULL)L->length=0;elseprintf(" 超出范圍??！");returnL;}ElemType*Locate_SeqList(JSeqlistL,intp){//查找線性表中下標(biāo)為 P的元素if(p>=0&&L->length)return(L->elem[p]);else{printf(" 順序表中不存在相關(guān)元素 ");returnNULL;標(biāo)準(zhǔn)文檔實用文案}}intInsert_SeqList(JSeqlistL,inti,ElemType*x){//在順序表中指定元素前插入 Xintj;if(L->length==MaxSize)//L.length 是最后一個元素的位置{printf(" 線性表已滿，無法進(jìn)行插入操作！ ?。?！\n");return0;}if(i<0||i>L->length){printf(" 插入位置不對，超出順序表長度 \n");return0;}if(i==0){L->elem[i]=x;L->length=L->length+1;return1;}for(j=L->length;j>=i;j--){L->elem[ j]=x;}L->length++;return1;標(biāo)準(zhǔn)文檔實用文案}intDelete_JSeqlist(JSeqlistL,inti){//在順序表中刪除第 i個元素intj;if(i<0||i>L->length-1){printf(" 刪除位置不對，超出順序表的長度啦 \n");return0;}for(j=i;j<L->length-1;j++)L->elem[j]=L->elem[j+1];L->length--;return1;}voidjosephus(JSeqlistL,intstart,intm){//josephus 問題求解的非常牛逼的函數(shù)ints,i;ElemType*w;s=start-1;for(i=L->length;i>0;i--){標(biāo)準(zhǔn)文檔實用文案s=(s+m-1)%i;w=Locate_SeqList(L,s);printf(" 出列人員為： %s\n",w);Delete_JSeqlist(L,s);}}intmain(void){JSeqlistJosephus;intn,m,i,k,s;Josephus=Int_SeqList();// 順序表初始化printf(" 約瑟夫環(huán)問題順序表求解 _愚人節(jié)特別版 \n\n");printf(" 請輸入本問題中總?cè)藬?shù) m=");scanf("%d",&n);printf(" 請輸入本問題開始人員的位置 S=");scanf("%d",&s);printf(" 請輸入本問題的計數(shù)值 m=");scanf("%d",&m);printf(" 請輸入本問題中這些人的名字 \n");for(i=0;i<n;i++){printf(" 第%d位置的人員的名字為 :",(i+1));標(biāo)準(zhǔn)文檔實用文案Josephus->elem[i]=(ElemType*)calloc(10,sizeof(char));scanf("%s",Josephus->elem[i]);k=Insert_SeqList(Josephus,i,Josephus->elem[i]);if(k==0)exit(1);}josephus(Josephus,s,m);free(Josephus);getchar();return0;}運行結(jié)果標(biāo)準(zhǔn)文檔實用文案(三)密碼不同#include<iostream.h>structCList{intpassword;intnumber;structCList*next;};typedefstructCListCNode;typedefCNode*CLink;CLinkCreateList(intlength){CLinkhead;CLinkbefore;CLinknew_node;inti;head=newCNode;if(head==NULL)returnNULL;cout<<"PleaseInputPassword1:"<<endl;cin>>head->password;head->number=1;標(biāo)準(zhǔn)文檔實用文案head->next=NULL;before=head;for(i=1;i<length;i++){new_node=newCNode;if(new_node==NULL)returnNULL;new_node->number=i+1;cout<<"PleaseInputPassword"<<new_node->number<<":"<<endl;cin>>new_node->password;new_node->next=NULL;before->next=new_node;before=new_node;}new_node->next=head;returnhead;}intmain(){標(biāo)準(zhǔn)文檔實用文案CLinkhead;CLinkptr,back,last;inti,j,m,n;cout<<"PleaseInputtheNumberofPersons:"<<endl;cin>>n;cout<<"Plea