考研论坛 - 软件硕士（mse） - [推荐]数据结构（c＋＋）习题解答(页 1) 简化版本.htm

研究生硕士考题 数据结构C++部分 多道好题和答案

                  试编写一个求解Josephus问题的函数。用整数序列1, 2, 3, ……, 
                  n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n = 9, s = 1, m = 
                  5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 
                  10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。<BR>【解答】函数源程序清单如下：<BR>&nbsp; 
                  &nbsp; &nbsp; &nbsp; void Josephus( int A[ ], int n, s, m ) 
                  {<BR>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  int i, j, k, tmp;<BR>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; if ( m == 0 ) {<BR>cout &lt;&lt; "m = 0是无效的参数！" 
                  &lt;&lt; endl; <BR>return;<BR>}<BR>for ( i = 0; i &lt; n; i++ 
                  )&nbsp;&nbsp;A[ i ] = i + 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  /*初始化，执行n次*/<BR>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; i = s - 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  /*报名起始位置*/<BR>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; for ( k = n; k &gt; 1; i-- ) {&nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  /*逐个出局，执行n-1次*/<BR>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ( i == k ) i = 
                  0;<BR>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  i = ( i + m - 1 ) % k;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /*寻找出局位置*/<BR>if ( i 
                  != k-1 ) {<BR>&nbsp; &nbsp;tmp = A[ i ];&nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; /*出局者交换到第k-1位置*/<BR>&nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp; &nbsp; for ( j = i; j &lt; k-1; j++ ) A[j] = 
                  A[j+1];<BR>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; A[k-1] = 
                  tmp;<BR>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<BR>&nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<BR>&nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for ( k = 0; k &lt; n / 2; 
                  k++ ) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  /*全部逆置, 得到出局序列*/<BR>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tmp = A[k]; A[k] = 
                  A[n-k+1]; A[n-k+1] = tmp;<BR>&nbsp; &nbsp; &nbsp; &nbsp; 
                  &nbsp; &nbsp; &nbsp; &nbsp; }<BR>&nbsp; &nbsp; &nbsp; &nbsp; 
                  }<BR>例：n = 9, s = 1, m = 5<BR>&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; 
                  &nbsp;&nbsp;&nbsp;<BR><BR>&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;0 &nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;2&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; &nbsp; <BR>k = 9&nbsp; 
                  &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;2&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;9&nbsp; &nbsp; &nbsp; &nbsp; 第5人出局, i = 
                  4<BR>k = 8&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;1&nbsp; 
                  &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;2&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;9&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; &nbsp; 第1人出局, i = 
                  0<BR>k = 7&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;2&nbsp; 
                  &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;9&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; &nbsp; 第7人出局, i = 
                  4<BR>k = 6&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;2&nbsp; 
                  &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;9&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; &nbsp; 第4人出局, i = 
                  2<BR>k = 5&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;2&nbsp; 
                  &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;9&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; &nbsp; 第3人出局, i = 
                  1<BR>k = 4&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;2&nbsp; 
                  &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;9&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; &nbsp; 第6人出局, i = 
                  1<BR>k = 3&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;2&nbsp; 
                  &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;9&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; &nbsp; 第9人出局, i = 
                  2<BR>k = 2&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;2&nbsp; 
                  &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;9&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; &nbsp; 第2人出局, i = 
                  0<BR>&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; 
                  &nbsp; &nbsp;&nbsp;&nbsp;2&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;9&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;1 
                  &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; 
                  &nbsp; 第8人出局, i = 0<BR>逆置&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;9&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;2&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; &nbsp; 
                  最终出局顺序<BR>&nbsp; &nbsp; &nbsp; &nbsp; 例：n = 9, s = 1, m = 
                  0<BR>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
                  报错信息&nbsp;&nbsp;m = 0是无效的参数！<BR>例：n = 9, s = 1, m = 10&nbsp; 
                  &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;<BR>&nbsp; &nbsp; 
                  &nbsp; &nbsp;&nbsp;&nbsp;0 &nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;2&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;6&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;7&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;8&nbsp; &nbsp; &nbsp; &nbsp; <BR>k = 9&nbsp; 
                  &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;1&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;2&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;3&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;4&nbsp; &nbsp; &nbsp; 
                  &nbsp;&nbsp;&nbsp;5&nbsp; &nbsp; &nbsp;