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

1、(一)基本問題1問題描述設(shè)有編號為1,2,小的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)問題。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 Nodeint data;No

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

3、t;刪除p結(jié)點的后一結(jié)點qq=p-n ext;p_n ext=q _n ext;*L = p_n ext;報出位置后Delete q;計數(shù)器i+;運行流程圖代碼和相關(guān)解釋#in cludeusing n amespace std;struct Node/循環(huán)節(jié)點的定義int data;/ 編號Node *n ext;；Node *CreateList(Node *L,i nt &n,int &m);建立約瑟夫環(huán)函數(shù)void Joseph(Node *L,int n,int m); 輸出每次出列號數(shù)函數(shù)Node *DeleteList(Node *L,i nt i,Node *q);尋找每次出列

4、人的號數(shù)int LengthList(Node *L); 計算環(huán)上所有人數(shù)函數(shù)void main() 主函數(shù)在主函數(shù)中，完成人數(shù)(n)和報數(shù)(m)的輸入和工作指針的初始化Node *L;L=NULL;初始化尾指針int n, m;coutn;環(huán)的長度if(* 1)cout請輸入正整數(shù)!;/人數(shù)異常處理elsecout請輸入所報數(shù) M :;cinm;if(m1)cout請輸入正整數(shù)!;/號數(shù)異常處理elseL=CreateList(L,n,m);重新給尾指針賦值Joseph(L ,n, m);system(pause);Node *CreateList(Node *L,i nt &n ,i nt

5、 & m)建立一個約瑟夫環(huán)(尾插法)Node *q;for(i nt i=1;idata=i;p- next=NULL;if(i=1) L=q=p; 工作指針的初始化elseq_n ext=p;q=q_n ext;q_n ext=L;if(L!=NULL)return(L);返回尾指針else cout尾指針異常!endl;尾指針異常處理void Joseph(Node *L,int n,int m) 輸出每次出列的人int k;cout k;if(kn)cout請輸入 1-*之間的數(shù)endl;elsecoutn 出列順序:n;for(i nt i=1;i n;i+)Node *q = new

6、 Node;if(i=1) q=DeleteList (&L,k+m-1,q);第一個出列人的號數(shù)else q=DeleteList(&L,m,q);cout號數(shù)：dataendl;delete q;/釋放出列人的存儲空間cout最后一個出列號數(shù)是：dataendl;輸出最后出列人的號數(shù)Node *DeleteList(Node *L,i nt i,Node *q) /尋找每次出列的人if(i=1) i+=Le ngthList(*L);順序依次出列情況的處理方式Node *p;P=*L;int j=0;while(jn ext;j+;q = p_n ext;p-n ext=p-n ext-

7、n ext;*L = p_n ext;return(q); int LengthList(Node *L)/ 計算環(huán)上的人數(shù)if(L)cout尾指針錯誤!n ext;while(p!=L)p=p-n ext;return(i);復(fù)雜度分析:for(i nt i=1;inu mber=i; p- next=NULL; if(i=1) L=q=p; elseq_n ext=p; q=q_n ext;時間復(fù)雜度：O (n)if(i=1) i+=Le ngthList(*L);Node *p;p=*L;int j=0;while(jn ext;j+;q = p_n ext;p-n ext=p-n ex

8、t-n ext;*L = p_n ext;return(q);時間復(fù)雜度：O (n2)算法的空間復(fù)雜度：O (n2)4界面設(shè)計請輸入報數(shù)人數(shù)n 請輸入所報數(shù)M 請輸入第一個報數(shù)人以下列出依次報數(shù)的結(jié) 果5.運行、測試與分析I啟 P：新建文彳核Debug12.exe-是蛛-列繼= 岀鯉24 631順一任列馥馥縱縱馥后按岀號號號號呂呂樂請-(二)采用順序存儲結(jié)構(gòu)如何實現(xiàn)約瑟夫環(huán)問題代碼和解釋#in elude #in clude#in clude#define MaxSize 50typedef char ElemType;typedef struct Seqlist/線性表順序存儲結(jié)構(gòu)定義Ele

9、mType *elemMaxSize;存放順序表數(shù)據(jù)元素int length;/當(dāng)前長度*JSeqlist;線性表存儲結(jié)構(gòu)類型名JSeqlist In t_SeqList(void)/順序表初始化JSeqlist L;L=(JSeqlist)malloc(sizeof(struct Seqlist);if(L!=NULL)L-le ngth=O;elseprintf(超出范圍！ ！ ”)；return L;ElemType *Locate_SeqList(JSeqlist L,i nt p)/查找線性表中下標(biāo)為P的元素if(p=0&L-le ngth)return(L-elemp);elsep

10、rintf(順序表中不存在相關(guān)元素”)；return NULL;int In sert_SeqList(JSeqlist L,i nt i,ElemType *x)/在順序表中指定元素前插入Xint j;if(L-le ngth=MaxSize)/L.le ngth是最后一個元素的位置printf(線性表已滿，無法進行插入操作！ n);return 0;if(iL-le ngth)printf(插入位置不對，超出順序表長度n);return 0;if(i=0)L-elemi=x;L-le ngth=L-le ngth+1;return 1;for(j=L-le ngth;j=i;j_)L-el

11、emj=x;L-le ngth+;return 1;int Delete_JSeqlist(JSeqlist L,i nt i)/在順序表中刪除第i個元素int j;if(iL-le ngth-1)printf(刪除位置不對，超出順序表的長度啦 n);return 0;for(j=i;jle ngth-1;j+)L-elemj=L-elemj+1;L-le ngth-;return 1;void josephus(JSeqlist L,i nt start,i nt m)/josephus問題求解的非常牛逼的函數(shù)int s,i;ElemType *w;s=start-1;for(i=L-le

12、ngth;iO;i-)s=(s+m-1)%i;w=Locate_SeqList(L,s);printf(出列人員為：%sn,w);Delete_JSeqlist(L,s);int mai n (void)JSeqlist Josephus;int n,m,i,k,s;Josephus=I nt_SeqList(); 順序表初始化printf(約瑟夫環(huán)問題順序表求解_愚人節(jié)特別版nn);printf(請輸入本問題中總?cè)藬?shù)m=);scan f(%d,&n);printf(請輸入本問題開始人員的位置S=);scan f(%d, &s);printf(請輸入本問題的計數(shù)值m=);scan f(%d,&

13、m);printf(請輸入本問題中這些人的名字n);for(i=0;ielemi=(ElemType *)calloc(10,sizeof(char);sca nf(%s,Josephus-elemi);k=ln sert_SeqList(Josephus,i,Josephus-elemi); if(k=0)exit(1);josephus(Josephus,s,m);free(Josephus);getchar();return 0;運行結(jié)果序表求解4八 UU s ef班附 r.Xh a Ciee klop q；罵結(jié)匚D e bu g*匚 pp 2 50.exe!_Uh.1WS字 N _-s

14、 -: 白 H I I I I III? 名名名名名名 口 p JB ihn JBi&u JB B -:C 3 匚-乜 C 厘 51 3 4 5樣S嘗置置置臺 坯刖3刖4印 主冃青青主I-1I11-11 -臺豐員呂賽員員一一貝吳曉叢篆初 問冋為為為為為V 邯廿由孑由口3貝口3貝口3貝an 入人人人人人壬 品 eF(三)密碼不同#in elude struct CListint password;int nu mber; struct CList *n ext;typedef struct CList CNode;typedef CNode *CL ink;CLink CreateList(in

15、t length)CLink head;CLink before;CLink new_no de;int i;head=new CNode;if(head=NULL)return NULL;cout Please In put Password 1 : head-password;head-nu mber=1;head- next=NULL;before=head;for(i=1;inu mber = i+1;cout Please In put Password nu mber : new_no de-password;new_no de-n ext = NULL;before-n ext=

16、new_no de;before=new_no de;new_no de-n ext =head;retur n head;int mai n()CLi nk head;CLink ptr,back,last;int i,j,m, n;cout Please In put the Number of Pers on s: n;cout Please In put the First Password M: m;head=CreateList (n);ptr=head;for(i=0;i n;i+)for(j=0;jn ext;cout 第i+1個出列的編號為:numberpassword;if

17、(ptr=head)last=head;while(last-n ext!=head) last=last- n ext;last-n ext=head-n ext; delete ptr;ptr=last- n ext; head=ptr;elseback- n ext=ptr- n ext; delete ptr;ptr=back- n ext;return 0;運行結(jié)果Please Input EPlisase Input Please Input (Please Input4iPlease Input iFlisase Input2Fliease Input h?th? Hunber of Fersoms: the First Password Ml number from whon startPas s wo rid 2 Pass wo rid 3 iPassword 4*Password 5 Password 6 *叮 bC:Ur.Zh aoD 酪 kte pI5韋不圍的 5:SD e bu gCpp. et-TLF05M1F EKy 勺勺勺令