数据结构课程部分习题解答.docVIP

数据结构课程第二章部分习题解答 第二章 数组 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 最终出局顺序 例：n = 9, s = 1, m = 0 报错信息 m = 0是无效的参数！ 例：n = 9, s = 1, m = 10 0 1 2 3 4 5 6 7 8 k = 9 1 2 3 4 5 6 7 8 9 第1人出局, i = 0 k = 8 2 3 4 5 6 7 8 9 1 第3人出局, i = 1 k = 7 2 4 5 6 7 8 9 3 1 第6人出局, i = 3 k = 6 2 4 5 7 8 9 6 3 1 第2人出局, i = 0 k = 5 4 5 7 8 9 2 6 3 1 第9人出局, i = 4 k = 4 4 5 7 8 9 2 6 3 1 第5人出局, i = 1 k = 3 4 7 8 5 9 2 6 3 1 第7人出局, i = 1 k = 2 4 8 7 5 9 2 6