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表示顺序围坐在圆桌周围的人 并采用数组表示作为求解过程中使用的数据结构。然后使用n=9,s=1,m=5,以及n=9,s=1,m=0, 或者n=9,s=1,m=10作为输入数据,检查你的程序的正确性和健壮性。最后分析所完成算法的时间 复杂度 【解答】函数源程序清单如下: void Josephus( int A[l, int n, s, m)i int i,j, k, Imp; if(m==0){ out<<"m=0是无效的参数!"<<endl for(i=0;1<m;计+)4[=i+1 初始化,执行n次*/ 报名起始位置* for(k=n;k>l;i--)( 逐个出局,执行m1次* i=(i+m-1)%k /寻找出局位置* 出局者交换到第k-1位置* [k-1=mp; 全部逆置,得到出局序列* =[k;型[k=A{n-k+1;A[n什1=mp 第第第 人出 1人出 7人出 局局局 第4人出局,i=2 第第第 3人 人 人 出出出 局局局 第2人出局,i=0 8人出 逆置[5[7 第最 终出局 局顺 序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 表示顺序围坐在圆桌周围的人， 并采用数组表示作为求解过程中使用的数据结构。然后使用 n = 9, s = 1, m = 5，以及 n = 9, s = 1, m = 0， 或者 n = 9, s = 1, m = 10 作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间 复杂度。 【解答】函数源程序清单如下： void Josephus( int A[ ], int n, s, m ) { int i, j, k, tmp; if ( m == 0 ) { cout << "m = 0 是无效的参数！" << endl; return; } for ( i = 0; i < n; i++ ) A[i] = i + 1; /*初始化，执行 n 次*/ i = s - 1; /*报名起始位置*/ for ( k = n; k > 1; i-- ) { /*逐个出局，执行 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 < k-1; j++ ) A[j] = A[j+1]; A[k-1] = tmp; } } for ( k = 0; k < n / 2; k++ ) { /*全部逆置, 得到出局序列*/ tmp = A[k]; A[k] = A[n-k+1]; A[n-k+1] = tmp; } } 例：n = 9, s = 1, m = 5 0 1 2 3 4 5 6 7 8 k = 9 1 2 3 4 5 6 7 8 9 第 5 人出局, i = 4 k = 8 1 2 3 4 6 7 8 9 5 第 1 人出局, i = 0 k = 7 2 3 4 6 7 8 9 1 5 第 7 人出局, i = 4 k = 6 2 3 4 6 8 9 7 1 5 第 4 人出局, i = 2 k = 5 2 3 6 8 9 4 7 1 5 第 3 人出局, i = 1 k = 4 2 6 8 9 3 4 7 1 5 第 6 人出局, i = 1 k = 3 2 8 9 6 3 4 7 1 5 第 9 人出局, i = 2 k = 2 2 8 9 6 3 4 7 1 5 第 2 人出局, i = 0 8 2 9 6 3 4 7 1 5 第 8 人出局, i = 0 逆置 5 1 7 4 3 6 9 2 8 最终出局顺序