用順序表解決約瑟夫環(huán)問題

1、計(jì)算機(jī)科學(xué)與工程學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告一專業(yè)班級(jí)試驗(yàn)地點(diǎn)學(xué)生學(xué)號(hào)指導(dǎo)教師學(xué)生姓名試驗(yàn)時(shí)間試驗(yàn)項(xiàng)目算法與數(shù)據(jù)結(jié)構(gòu)試驗(yàn)類別基礎(chǔ)性（） 設(shè)計(jì)性（） 綜合性（） 其它（ ）試驗(yàn)?zāi)康募耙螅?） 掌握用VC+上機(jī)調(diào)試線性表的基本方法； （2）掌握順序表的存儲(chǔ)結(jié)構(gòu)以及基本運(yùn)算的實(shí)現(xiàn)。成 績 評(píng) 定 表類 別評(píng) 分 標(biāo) 準(zhǔn)分值得分合 計(jì)上機(jī)表現(xiàn)積極出勤、遵守紀(jì)律主動(dòng)完成設(shè)計(jì)任務(wù)30分程序與報(bào)告程序代碼規(guī)范、功能正確報(bào)告詳實(shí)完整、體現(xiàn)收獲70分備注： 評(píng)閱教師： 日 期： 年 月 日試 驗(yàn) 內(nèi) 容 一、實(shí)驗(yàn)?zāi)康暮鸵?、實(shí)驗(yàn)?zāi)康模海?）掌握用VC+上機(jī)調(diào)試線性表的基本方法； （2）掌握順序表的存儲(chǔ)結(jié)構(gòu)以及

2、基本運(yùn)算的實(shí)現(xiàn)。2、實(shí)驗(yàn)內(nèi)容約瑟夫環(huán)問題：設(shè)編號(hào)為1，2，3，n的n(n>0)個(gè)人按順時(shí)針方向圍坐一圈，m為任意一個(gè)正整數(shù)。從第一個(gè)人開始順時(shí)針方向自1起順序報(bào)數(shù)，報(bào)到m時(shí)停止并且報(bào)m的人出列，再從他的下一個(gè)人開始重新從1報(bào)數(shù)，報(bào)到m時(shí)停止并且報(bào)m的人出列。如此下去，直到所有人全部出列為止。要求設(shè)計(jì)一個(gè)程序模擬此過程，對(duì)任意給定的m和n，求出出列編號(hào)序列。3、實(shí)驗(yàn)要求：用順序表實(shí)現(xiàn)。2、 設(shè)計(jì)分析根據(jù)實(shí)驗(yàn)要求，采用順序表來完成本次實(shí)驗(yàn)。實(shí)驗(yàn)中采用一維數(shù)組屁【】，先將n個(gè)人的編號(hào)存入到p0pn-1。從編號(hào)為1的人 (下標(biāo)t=0)開始循環(huán)報(bào)數(shù)，數(shù)到m的人(下標(biāo)t=(t+m-1)%i)pt，輸

3、出并將其從數(shù)組中刪除（即將后面的元素前移一個(gè)位置），每次報(bào)數(shù)的起始位置就是上次報(bào)數(shù)的出列位置。反復(fù)執(zhí)行直到出列n個(gè)人為止。3、 源程序代碼#include<stdio.h>#include<stdlib.h>#include <iostream.h>#define MaxSize 100typedef struct Listint dataMaxSize;int length;*Sqlist;void InitList(Sqlist &L)L=(Sqlist)malloc(sizeof(Sqlist);L->length=0;void Crea

4、teList(Sqlist &L) int n; printf("您想輸入的人數(shù)為:");scanf("%d",&n);printf("最初的順序表為:n");for(int i=0;i<n;i+)L->datai=i+1;printf("%d ",L->datai);L->length=n;printf("n");void josephus(Sqlist &L,int m)int i,j,t;t=0; printf("最后的順序表為:&

5、quot;);for(i=L->length;i>=1;i-) t=(t+m-1)%i;printf("%d ",L->datat);for(j=t+1;j<=i-1;j+)L->dataj-1=L->dataj;printf("n");void main()int tt;Sqlist L;InitList( L);CreateList(L);printf("您想出列的序號(hào)為:");scanf("%d",&tt);josephus(L,tt);四、測(cè)試用例（盡量覆蓋所有分支） 1.當(dāng)n>m且n%m!=0時(shí)，即當(dāng)n不是m的倍數(shù)時(shí)：n=12，m=5時(shí)約瑟夫環(huán)的實(shí)驗(yàn)結(jié)果為2.當(dāng)n>m且n%m=0時(shí)，即當(dāng)n是m的倍數(shù)時(shí)：n=15，m=5時(shí)約瑟夫環(huán)的實(shí)驗(yàn)結(jié)果為3. 當(dāng)n<m且n%m=0時(shí)，即當(dāng)n是m的約數(shù)時(shí)：n=4，m=12時(shí)約瑟夫環(huán)的實(shí)驗(yàn)結(jié)果