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

1、用順序表解決約瑟夫環(huán)問題計算機科學與工程學院算法與數(shù)據(jù)結構試驗報告一專業(yè)班級試驗地點學生學號指導教師學生姓名試驗時間試驗項目算法與數(shù)據(jù)結構試驗類別基礎性（） 設計性（） 綜合性（2） 其它（）試 驗 目 的 及 要 求（1）掌握用VC+上機調試線性表的基本方法；（2）掌握順序表的存儲結構以及基本運算的實現(xiàn)。成績評定表類另S評分標準分值得分合計上機表現(xiàn)積極出勤、遵守紀律主動完成設計任務30分程序與報告程序代碼規(guī)范、功能正確報告詳實完整、體現(xiàn)收獲70分備注:評閱教師：日期：年 月 日試驗內容一、實驗目的和要求1、實驗目的：（1）掌握用VC+上機調試線性表的基本方法；（2）掌握順序表的存儲結構以及基

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

3、t， 輸出并將其從數(shù)組中刪除（即將后面的元素前移一個位置），每次報數(shù)的起始位 置就是上次報數(shù)的出列位置。反復執(zhí)行直到出列n個人為止。三、源程序代碼#in clude#in clude#i nclude #defi ne MaxSize 100 typedef struct Listint dataMaxSize;int len gth;*Sqlist;void In itList(Sqlist &L)L=(Sqlist)malloc(sizeof(Sqlist);L-le ngth=O;void CreateList(Sqlist &L)int n;printf(您想輸入的人數(shù)為:);sca

4、nf(%d,&n);printf(最初的順序表為:n);for(i nt i=0;i datai=i+1;prin tf(%d ,L-datai);L-le ngth=n;prin tf(n);void josephus(Sqlist &L,i nt m)int i,j,t;t=0;printf(最后的順序表為:);for(i=L-le ngth;i=1;i-)t=(t+m-1)%i;prin tf(%d 丄-datat);for(j=t+1;jdataj-1=L-dataj;prin tf(n);void mai n()int tt;Sqlist L;In itList( L);Create

5、List(L);printf(您想出列的序號為:);sea nf(%d，& tt);josephus(L,tt);四、測試用例(盡量覆蓋所有分支)1.當nm且n%m!=0時，即當n不是m的倍數(shù)時:n=12，m=5時約瑟夫環(huán)的實驗結果為：12311 12：516 3 9 4 12cantinue_8 F L丄 2 6 1LProcvm 卜iIesWCWlsg応出MyJrojects,q Debuq-.qj.exer!.e ko thj 5 s Jy + s X -XJrpxb 的序b的序砂 人順煜列順an 需j出的$ 總刀 阻U 口 S2.當 nm且n%m=0時，即當n是m的倍數(shù)時:n=15，m

6、=5時約瑟夫環(huán)的實驗結果為 AHSDev9BH yPrafeiwMXwcuwe幣想輸入的入數(shù)為汽5最初的順序表為=1 2 3 4 5 6 ? S 9 10 11 12 13 14 15您想岀列的序號為瀉5 10 15 6 12 3 11 4 14 ? 0 13 2 7 1侵后的順序一rress any key to continue3.當*m且n%m=0時，即當n是m的約數(shù)時:n=4, m=12時約瑟夫環(huán)的實驗結果為4.當 *m且n%m!=0時，即當n不是m的約數(shù)時:計算機科學與工程學院n=3, m=7時約瑟夫環(huán)的實驗結果為5 .當n或m任一個足夠大時n=150， m=7時約瑟夫環(huán)的實驗結果為

7、E: H9ev98yProjects yirh tv Debugvuhtvxe*. 您is輸入的人數(shù)為訂 最初欝順序袤為孑1 2 3 4 & t 7 8 9 10 11 12 12 14 1S 16 1? 1Q 19 20 21 22 23 24 2& 2G 27 28 29 3(31 22 23 34 3S 3G 37 3S 39 40 41 42 43 44 45 4G 47 48 49 0 G1 52 旳 G4 旺?7列59G9 1門 &2 6M&4&S 1&9 河1 7172 173 羽 7&76 177 781 79朗1B1 2S384甘石86878S09 90(9192 ?3 94

8、1 9S96 97 981 991001011021031Q410510G10710810911911111211311411SLit117 11611912012112212312412&12t1271281291311221抽1341J&136137 13613914014114214314414514147148 147 156您想出列的茫號為許最后的順序表為” 14 21 28 3& 42 49 &G G3 70 77 Q4 91 9S 10G 112 119 12fc 133 146 147 4 12 28 29 37 45 53 G1 齡丹氈?4 102 110 110 12? 135 142 1 16 19 3(J 39 4S 58 &7 7t 87 9t 106 115 124 134 144 3 15 25 36 47 59 71 81 92 103 114 125 137 1449 23 34 50 62 74 R& 103 113 129 137 2 17 32 46 64 79 93 108 122 138 5 22 40 5573 90 109 129 i45 13 33 4 7E 97 117 136 Q 31 57 92 134 130 lS 27 ED 85 li