综合题

  1. 【2010】设将 n（n > 1）个整数存放到一维数组 R 中，设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移 p （0 < p < n）个位置，即将 R 中的数据由（X0，X1，…，Xn-1）变换为（Xp，Xp+1，…，Xn-1，X0，X1，…，Xp-1）。

算法思想：使用逆置函数，对于将 ab 变为 ba 的过程，先对a 逆置得到 a^-1 然后对 b 逆置得到 a^-1 b^-1，最后将整个 部分逆置，（a^-1,b^-1）^-1 = ba。

  1. void Reserve(int R[], int form, int to) {
  2.     int i, temp;
  3.     for (i = 0; i < (to - form) / 2; i++) {
  4.         temp = R[form + i];
  5.         R[form + i] = R[to - i];
  6.         R[to - i] = temp;
  7.     }
  8. }
  10. void Converse (int R[], int n, int p) {
  11.     Reservr(R, 0,  p - 1);
  12.     Reserve(R, p, n - 1);
  13.     Reserve(R, 0, n - 1);
  14. }
  1. 【2011】长度 L 的升序序列 S，[L / 2] 称为中位数，两序列中位数是他们所含元素升序的中位数。现有 等长两个升序序列 A 和 B，设计一个算法找出 A、B 中位数。

算法思想：分别求出两升序序列的中位数，分别设为 a，b，作比较。若 a = b ，则就是两序列中位数。若不相等则舍弃较大中位数序类中的大于中位数的元素，同时舍弃较小中位数中小于中位数的元素。将剩余元素按照升序排列，再次对其求中位数，重复上述过程，直到两序列中仅含有一个元素，较小元素为所求中位数。

  1. int M_Search (int A[], int B[], int n) {
  2.     itn s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
  3.     //分别代表序列a，b的首位数、末位数和中位数；
  4.     while (s1 != d1 || s2 != d2) {
  5.         m1 = (s1 + d1) / 2;
  6.         m2 = (s2 + d2) / 2;
  7.         if (A[m1] == B[m2])
  8.             return A[m1];
  9.         if(A[m1] < B[m2]) {
  10.             if ((s1 + d1) % 2 == 0) {
  11.                 s1 = m1;
  12.                 d2 = m2;
  13.             }
  14.             else {
  15.                 s1 = m1 + 1;
  16.                 d2 = m2;
  17.             }
  18.          else {
  19.             if ((m2 + d2) % 2 == 0) {
  20.                 if ((s1 + d1) % 2 == 0) {
  21.                     d1 = m1;
  22.                     s2 = m2;
  23.                 } else {
  24.                     d1 = m1;
  25.                     s2 = m2 + 1;
  26.                 }
  27.             }
  28.           }
  29.         }
  30.     }
  31.     return A[s1] < B[s2] ? A[s1] : B[s2];
  32. }