1、中央电大开放教育（http:/）第二章数组部分习题解答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、, 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 1; i- ) /*逐个出局，执行 n-1 次*/if ( i = k ) i = 0;i = ( i + m
3、- 1 ) % k; /*寻找出局位置*/if ( i != k-1 ) tmp = Ai; /*出局者交换到第 k-1 位置*/for ( j = i; j void inverse ( Type A , int n ) Type tmp;for ( int i = 0; i j，数组元素 Aij在数组 B 中没有存放，可以找它的对称元素 Aji。在数组 B 的第 (2n-j) * (j-1) / 2 + i 位置中找到。如果第 0 行第 0 列也计入，数组 B 从 0 号位置开始存放，则数组元素 Aij在数组 B 中的存放位置可以改为当 i j 时，= (2n-i+1) * i / 2 +
4、 j - i = ( 2n - i - 1 ) * i / 2 + j当 i j 时，= (2n - j - 1) * j / 2 + i (3) 只存下三角部分时，若 i j，则数组元素 Aij前面有 i-1 行（1i-1，第 0 行第 0 列不算)，第 1 行有 1 个元素，第 2 行有 2 个元素，第 i-1 行有 i-1 个元素。在第 i 行中，第 j 号元素排在第 j 个元素位置，因此，数组元素 Aij在数组 B 中的存放位置为1 + 2 + + (i-1) + j = ( i-1)*i / 2 + j若 i include “string.h“void frequency( Stringif ( !len ) cout include “string.h“const int charnumber = 128; /*ASCII 码字符集的大小*/void frequency( String i 0 ) cout “( “ i “ ) : t“ Ci “t“;测试结果
