算法课第五章

Posted on

递归与递推

快速幂

问题描述：

求a的m次幂，要求时间复杂度log(n)

当然，一般不会求a的幂次，因为很容易越界，更常见的是求modN(a, m, n)

  • 递归实现：

    1
    2
    3
    4
    5
    6
    long long pow1(a, m) {
      if (m == 0)
        return 1;
      if (m & 1) a*pow1(a, m-1);
      else a*a*pow1(a, m/2);
    }

  • 递推实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int ans = 1;
    while(m) {
      if (m&1) {
        ans *= a;
        --m;
      }
      a = a*a;
      m /= 2;
    }

算法思维扩展：（往届一道考题）

寻找多位元素

问题描述:

输入数组A，找出A[1, … , n]中的多位元素（多位元素：数量大于一半）

  • 代码实现
    核心思想：如何找出多位元素的候选值 O(n), 之后再判断候选值是否为多位元素
    一个序列，同时删去两个不同的数，该数组的多位元素不变

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 伪代码，只是阐述算法思想
    int condidate(int c) {
      int count = 1, i;
      for (i=c+1; i<n && count; ++i) 
        count += (A[i] == A[c] ? 1:-1);
      if (count == 0) condidate(i);
      return A[c];
    }

    int findDuo() {
      int c = condidate(0);
      int count = 0;
      for (int i=0; i<n; ++i)
        if (A[i] == c) count++;
      if (count > n/2) return c;
      else none;
    }