第2章数组 Type* Next (i return current last? &data[++current]: NULL; J ∥取当前表项的后继表项的值,置为当前表项 Type Prior(i return current >0? &datal--current: NULL; 3 取当前表项的前驱表项的值,置为当前表项 int Is Empty (i return last ==-1; ∥判断顺序表空否,空则返回1;否则返回 int IsFull(){ return last= Maxsize-l;}∥判断顺序表满否,满则返回1;否则返回0 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, tmp; if(m=0){ out<<"m=0是无效的参数!"<<endl for(i=0;1<n;H+)A[=i+1; 初始化,执行n次* 报名起始位置* for(k=n;k>I; i--)( 逐个出局,执行n1次*/ /寻找出局位置* f(il=k-1){ tmp=A[]; 出局者交换到第k-1位置* for(j=i;j<k-1; j++)ADJ=A[+1]: Ak-1= tmp; for(k=0;k<n/2;k++){ /全部逆置,得到出局序列* tmp=ak]: akk]=A[n-k+1: A[n-k+1]=tmp 例:n=9,s=1,m=5第 2 章 数组 10 Type * Next ( ) { return current < last ? &data[++current] : NULL; } //取当前表项的后继表项的值，置为当前表项 Type * Prior ( ) { return current > 0 ? &data[--current] : NULL; } //取当前表项的前驱表项的值，置为当前表项 int IsEmpty ( ) { return last == -1; } //判断顺序表空否, 空则返回 1; 否则返回 0 int IsFull ( ) { return last == MaxSize-1; } //判断顺序表满否, 满则返回 1; 否则返回 0 } 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