数据结构课程第二章部分习题解答
第二章 数组
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 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

下一页