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

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

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

3、i)pt, 輸出并將其從數(shù)組中刪除(即將后面的元素前移一個位置)，每次報數(shù)的起始位 置就是上次報數(shù)的出列位置。反復(fù)執(zhí)行直到出列n個人為止。三、源程序代碼#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;vo

4、id CreateList(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("最后的順序表為：”);for(

5、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(“您想出列的序號為：”)；scanf("%d”,&tt);josephus(L,tt);四、測試用例(盡量覆蓋所有分支)1 .當(dāng)n>m且n%m!=0時，即當(dāng)n不是 m的倍數(shù)時

6、:n=12, m=5時約瑟夫環(huán)的實驗結(jié)果為, 'D:Program FilDevSB'' MyPrajectgjXDebuggj.exer算法與數(shù)據(jù)結(jié)構(gòu)試驗報告8：129 1B 11 12：510 3 9 4 12 coniinue.2 .當(dāng)n>m且n%m=0時，即當(dāng)n是m的倍數(shù)時:n=15, m=5時約瑟夫環(huán)的實驗結(jié)果為Q 'T:HSDev9BlM您想甄入的人數(shù)為二居最初的順序表為二1 2 3 4 5 6 7 S 9 10 11 12 13 14 1S唇想出列的序節(jié)為:5最后的順序表為:5 10 15 6 12 3 11 4 14 7 9 13 2 7 1Press anv Jsev to continue3 .當(dāng)n<m且n%m=0時，即當(dāng)n是 m的約數(shù)時:n=4, m=