设n个人围坐在一个圆桌周围

《设n个人围坐在一个圆桌周围》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、顺序表2-1设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n=9,s=1,m=5为例，人工模拟Josephus的求解过程以求得问题的解。【解答】出局人的顺序为5,1,7,4,3,6,9,2,8。2-2试编写一个求解Josephus问题的函数。用整数序列1,2,3,……,n表示顺序围坐在圆桌周围的人，并采用数组表示作

2、为求解过程中使用的数据结构。然后使用n=9,s=1,m=5，以及n=9,s=1,m=0，或者n=9,s=1,m=10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。【解答】函数源程序清单如下：voidJosephus(intA[],intn,s,m){inti,j,k,tmp;if(m==0){cout<<"m=0是无效的参数！"<1;i--){/*逐

3、个出局，执行n-1次*/if(i==k)i=0;i=(i+m-1)%k;/*寻找出局位置*/if(i!=k-1){tmp=A[i];/*出局者交换到第k-1位置*/for(j=i;j

4、8915第7人出局,i=4k=623689715第4人出局,i=2k=526894715第3人出局,i=1k=428934715第6人出局,i=1k=328634715第9人出局,i=2k=289634715第2人出局,i=0829634715第8人出局,i=0逆置517436928最终出局顺序例：n=9,s=1,m=0报错信息m=0是无效的参数！例：n=9,s=1,m=10012345678k=923456789第1人出局,i=0k=824567891第3人出局,i=1k=724578931第6人出局,i=3k=64578963

5、1第2人出局,i=0k=545782631第9人出局,i=4k=447892631第5人出局,i=1k=348592631第7人出局,i=1k=287592631第4人出局,i=0847592631第8人出局,i=0逆置136295748最终出局顺序当m=1时，时间代价最大。达到(n-1)+(n-2)+∙∙∙∙∙∙+1=n(n-1)/2»O(n2)。2-3设有一个线性表(e0,e1,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容

6、置换为(en-1,en-2,…,e1,e0)。【解答】32templatevoidinverse(TypeA[],intn){Typetmp;for(inti=0;i<=(n-1)/2;i++){tmp=A[i];A[i]=A[n-i-1];A[n-i-1]=tmp;}}2-4顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素?【解答】若设顺序表中已有n=last+1个元素，last是顺序表的数据

7、成员，表明最后表项的位置。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。插入时平均移动元素个数AMN(AveragyMovingNumber)为删除时平均移动元素个数AMN为2-5利用顺序表的操作，实现以下的函数。(1)从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。(2)从顺序表中删

8、除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。(3)向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。(4)从顺序表中删除具有给定值x的所有元素。(5)从顺序表中删除其值在给定值