約瑟夫環(huán)問(wèn)題 實(shí)驗(yàn)報(bào)告

數(shù)學(xué)與計(jì)算機(jī)學(xué)院約瑟夫環(huán)問(wèn)題實(shí)驗(yàn)報(bào)告年級(jí)10級(jí)學(xué)號(hào)2010434062姓名成績(jī)專(zhuān)業(yè)電氣信息（計(jì)算機(jī)類(lèi)）實(shí)驗(yàn)地點(diǎn)主樓402指導(dǎo)教師史青宣實(shí)驗(yàn)項(xiàng)目約瑟夫環(huán)問(wèn)題實(shí)驗(yàn)日期2011年12月26日一、實(shí)驗(yàn)?zāi)康谋緦?shí)驗(yàn)的目的是進(jìn)一步理解線(xiàn)性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，進(jìn)一步提高使用理論知識(shí)指導(dǎo)解決實(shí)際問(wèn)題的能力。二、實(shí)驗(yàn)問(wèn)題描述設(shè)編號(hào)為1，2，···，n的n個(gè)人圍坐一圈，約定編號(hào)為k（1≤k≤n）的人從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人出列，他的下一位又從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列，依次類(lèi)推，直到所有人出列為止，由此產(chǎn)生一個(gè)出隊(duì)編號(hào)的序列。三、實(shí)驗(yàn)步驟1、實(shí)驗(yàn)問(wèn)題分析①由于當(dāng)某個(gè)人退出圓圈后，報(bào)數(shù)的工作要從下一個(gè)人開(kāi)始繼續(xù)，剩下的人仍要是圍成一個(gè)圓圈，可以使用循環(huán)表；由于退出圓圈的工作對(duì)應(yīng)著表中結(jié)點(diǎn)的刪除操作，對(duì)于這種刪除操作頻繁的情況，應(yīng)該選用效率較高的鏈表結(jié)構(gòu)；為了程序指針每一次都指向一個(gè)具體的代表一個(gè)人的結(jié)點(diǎn)而不需要進(jìn)行判斷，鏈表不帶表頭結(jié)點(diǎn)。所以，對(duì)于所有人圍成的圓圈所對(duì)對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)采用一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表來(lái)描述。設(shè)頭指針為p，并根據(jù)具體情況移動(dòng)可以采用數(shù)據(jù)類(lèi)型定義：Typedefstructnode{intnumber;structnode*next;}Lnode,*Linklist;②為了記錄退出的人的先后順序，采用一個(gè)順序表進(jìn)行存儲(chǔ)，程序結(jié)束后再輸入依次退出的人的編號(hào)順序。由于只記錄各個(gè)結(jié)點(diǎn)的number值就可以，所以定義一個(gè)整型一維數(shù)組。如“intquite[N];”N為一個(gè)根據(jù)實(shí)際問(wèn)題定義的一個(gè)足夠大的整數(shù)。2、功能（函數(shù)）設(shè)計(jì)根據(jù)上述分析，該算法可以由3個(gè)功能函數(shù)實(shí)現(xiàn)。Main（）用做數(shù)據(jù)的輸入和函數(shù)的調(diào)用，Init()做鏈表的初始化工作，使用Josephus()做刪除結(jié)點(diǎn)和保存輸出順序的工作，OutRing()完成序列的輸出工作。1.建立單循環(huán)鏈表函數(shù)LinkListInitRingList(intn)；2.產(chǎn)生Josephus順序函數(shù)voidJosephus(LinkListL,intn,intk,intm,intquit[N])3.輸出順序表voidPrint(intn,intquit[N])四、實(shí)驗(yàn)結(jié)果（程序）及分析1.實(shí)驗(yàn)的的源代碼：//約瑟夫環(huán)問(wèn)題.cpp:Definestheentrypointfortheconsoleapplication.////#include"stdafx.h"#include"iostream.h"#defineN34typedefstructNode{ intdata; structNode*next;}Lnode,*LinkList;LinkListInitRingList(intn)//尾插法建立單循環(huán)鏈表{ Lnode*L,*r,*s; L=newLnode;//不帶頭結(jié)點(diǎn) r=L; for(inti=1;i<n;i++) { s=newLnode; r->data=i; r->next=s; r=s; } r->data=n; r->next=L;//鏈表首尾相連 L=r;//L指向循環(huán)鏈表的尾結(jié)點(diǎn) returnL;}voidJosephus(LinkListL,intn,intk,intm,intquit[N]){ inti,j; Lnode*p,*q; p=L; for(intr=1;r<m;r++) p=p->next; for(i=0;i<n;i++) { for(j=1;j<=k-1;j++) p=p->next; q=p->next; p->next=q->next; quit[i]=q->data; deleteq; }}voidPrint(intn,intquit[N]){ inti; for(i=0;i<n;i++) cout<<quit[i]<<""; cout<<endl;}intmain(intargc,char*argv[]){ LinkListL; intn; intk; intm; cout<<"請(qǐng)輸入圍坐一圈的人數(shù)n的值:"<<endl; cin>>n; L=InitRingList(n); intquit[N]; cout<<"約定從編號(hào)為m的值開(kāi)始數(shù)，請(qǐng)輸入m的值:"<<endl;cin>>m; while(m>n||m<1) {cout<<"輸入錯(cuò)誤，請(qǐng)重新輸入："<<endl; cin>>m; } cout<<"要求數(shù)到k的人出列，請(qǐng)輸入k的值:"<<endl; cin>>k; cout<<"順序?yàn)?";Josephus(L,n,k,m,quit); Print(n,quit); return0;}2.測(cè)試數(shù)據(jù)A．當(dāng)n的初始值為7，k的值為5，m的值為1時(shí)，正確的出列順序?yàn)椋?、3、2、4、7、1、6，經(jīng)程序運(yùn)行測(cè)試，結(jié)果如下：可知程序運(yùn)行正確。B．程序的容錯(cuò)性測(cè)試，當(dāng)輸入m的值不符合問(wèn)題約定時(shí)，應(yīng)有錯(cuò)誤提示給用戶(hù)，指導(dǎo)用戶(hù)正確輸入，并做出相應(yīng)處理，保證程序運(yùn)