例:n=9,s=1,m=0 报错信息m=0是无效的参数! 67896 第1人出局,i=0 第3人出局,i=1 第6人出局,i=3 第2人出局,i=0 第9人出局,i=4 第5人出局,i=1 第7人出局,i=1 第4人出局,i=0 第8人出局,i=0 逆置「「3[629[5[74[8最终出局顺序 当m=1时,时间代价最大。达到(n-1)+(n-2)+……+1=m(n-1)2≈Om2)。 2-3设有一个线性表(eo,el,…,en2,en)存放在一个一维数组 Alarray Size]中的前n个数组元素位置 请编写一个函数将这个线性表原地逆置,即将数组的前n个原址内容置换为(en1,en2,…,en,eo)。 【解答】 template<class Type> void inverse( Type A[, int n)& Type tmp or(inti=0;i<=(n-1)/2;汁+){ m=4;=A[n-i-1l;A[n--1=mp; 2-7设有一个二维数组A[m][m,假设A[O]存放位置在64410),4[22存放位置在67610,每个元素 占一个空间,问A[3B3o存放在什么位置?脚注(0表示用10进制表示 【解答】 设数组元素A[[存放在起始地址为Loc(i,j)的存储单元中 Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676 n=(676-2-644)/2=15 ∴Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692. 2-9设有一个nxn的对称矩阵A,如图(a)所示。为了节约存储,可以只存对角线及对角线以上的元素 或者只存对角线或对角线以下的元素。前者称为上三角矩阵,后者称为下三角矩阵。我们把它们按行 存放于一个一维数组B中,如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问: (1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素? 心,(2)若在一维数组B中从0号位置开始存放,则如图(a)所示的对称矩阵中的任一元素a在只存上 角部分的情形下(图(b)应存于一维数组的什么下标位置?给出计算公式。 (3)若在一维数组B中从0号位置开始存放,则如图(a)所示的对称矩阵中的任一元素a在只存下 角部分的情形下(图(c)应存于一维数组的什么下标位置?给出计算公式 【解答】例：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 3 1 第 4 人出局, i = 0 8 4 7 5 9 2 6 3 1 第 8 人出局, i = 0 逆置 1 3 6 2 9 5 7 4 8 最终出局顺序 当 m = 1 时，时间代价最大。达到( n-1 ) + ( n-2 ) + ∙∙∙∙∙∙ + 1 = n(n-1)/2  O(n 2 )。 2-3 设有一个线性表 (e0, e1, …, en-2, en -1) 存放在一个一维数组 A[arraySize]中的前 n 个数组元素位置。 请编写一个函数将这个线性表原地逆置，即将数组的前 n 个原址内容置换为 (en-1, en-2, …, e1, e0)。 【解答】 template<class Type> void inverse ( Type A[ ], int n ) { Type tmp; for ( int i = 0; i <= ( n-1 ) / 2; i++ ) { tmp = A[i]; A[i] = A[n-i-1]; A[n-i-1] = tmp; } } 2-7 设有一个二维数组 A[m][n]，假设 A[0][0]存放位置在 644(10)，A[2][2]存放位置在 676(10)，每个元素 占一个空间，问 A[3][3](10)存放在什么位置？脚注(10)表示用 10 进制表示。 【解答】 设数组元素 A[i][j]存放在起始地址为 Loc ( i, j ) 的存储单元中。 ∵ Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676. ∴ n = ( 676 - 2 - 644 ) / 2 = 15 ∴ Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692. 2-9 设有一个 nn 的对称矩阵 A，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素， 或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行 存放于一个一维数组 B 中，如图(b)和图(c)所示。并称之为对称矩阵 A 的压缩存储方式。试问： (1) 存放对称矩阵 A 上三角部分或下三角部分的一维数组 B 有多少元素？ (2) 若在一维数组 B 中从 0 号位置开始存放，则如图(a)所示的对称矩阵中的任一元素 aij 在只存上 三角部分的情形下(图(b))应存于一维数组的什么下标位置？给出计算公式。 (3) 若在一维数组 B 中从 0 号位置开始存放，则如图(a)所示的对称矩阵中的任一元素 aij 在只存下 三角部分的情形下(图(c))应存于一维数组的什么下标位置？给出计算公式。 【解答】