Skip to main content

1.1 數學中的遞迴 vs 程式中的遞迴

數學中的遞迴

在高一數學課時，學習到使用遞迴解決數學上的問題，以下幾個是簡單的範例

  1. 有一位小朋友要走樓梯上樓，他一次可以往上走一階或一次走兩階，問你若要走 $n$ 階，共有幾種走法?

    • 在此我們可以藉由上一階、上兩階的特性，將問題轉換成，若我要走到第 $i$ 階，則他必是從 $i - 1$ 和 $i - 2$ 階走過來的，下一步，就可以列成遞迴關係式

    \[F(x)= \begin {cases} F(x-1)+F(x-2) & \text{if }x>1 \\ 1 & \text{if } x\leq 1\end{cases}\]

  2. 請將一個等差數列 $F(x)=3x+5$ 傳換成遞迴關係式

    • 很容易的第一項需要特別定義 $F(0)$，接下來的這一項就會式上一項再加3，列成關係式 \[F(x)= \begin {cases} F(x-1)+3 & \text{if }x>0 \\ 5 & \text{if }x=0\end{cases}\]

典型利用遞迴來找到解決問題的方法

  • 當遇到一個不易解決的問題時，試著找出分割這個問題的模式(建立遞迴關係式)
  • 找到之後藉由分割來將這個問題不斷地縮小
  • 當問題縮小到一定的大小時，我們可以直接解決該問題(決定終止條件)
  • 最後合併各個已解決小問題的答案即得到原問題的答案。(設計遞迴函式)

程式中的遞迴

　　在上面的一些例子中，都是使用學過的數學遞迴來解決一些數學上的問題，若是請你將上述問題變成程式問題，作法跟數學一模一樣，可以想像成$F(x)$就是程式當中的呼叫函數，換句話說，只需要藉由呼叫同一個函數的前幾項，就可以找到答案。接下來我們將上面兩個問題轉換成程式

  1. 小朋友上樓梯
    • 題目連結
    • 在此題中，唯一需要做的事就是將函數的回傳值設定為$F(x)=F(x-1)+F(x-2)$，再去注意中止條件即可
    • 程式碼
      /*
          |----|   |----|
          |    |   |    |
          |    ----|    |
          |             |
          |    ----|    |
          |    |   |    |
          |----|   |----|

          */
  #pragma GCC optimize("O3,unroll-loops")
  #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

  #include <bits/stdc++.h>
  #define ll long long
  #define fastio ios::sync_with_stdio(0), cin.tie(0)

  using namespace std;

  struct TYPE {
    int ma, mi, ans;
  };

  const int SIZE = 1 << 16;
  // 15:32678 16:65536 17:131072 18:2624144 19:524288 20:1048576
  struct segment_tree
  {
    // start from 1
    TYPE node[SIZE];
    TYPE merge(TYPE a, TYPE b) {
      TYPE ret;
      ret.ma = max(a.ma, b.ma);
      ret.mi = min(a.mi, b.mi);
      ret.ans = ret.ma - ret.mi;
      return ret;
    }
    void pull(int idx) {
      node[idx] = merge(node[idx * 2], node[idx * 2 + 1]);
    }
    void init(int L, int R, int idx, vector<TYPE> &input) {
      if(L == R) {
        node[idx] = input[L];
        return;
      }
      int now = (L + R) / 2;
      init(L, now, idx * 2, input);
      init(now + 1, R, idx * 2 + 1, input);
      pull(idx);
    }
    TYPE query(int L, int R, int idx, int l, int r) {
      if(L >= l && R <= r) return node[idx];
      int now = (L + R) / 2;
      if(r <= now) return query(L, now, idx * 2, l, r);
      if(l > now) return query(now + 1, R, idx * 2 + 1, l, r);
      return merge(query(L, now, idx * 2, l, r), query(now + 1, R, idx * 2 + 1, l, r));
    }
    void update(int L, int R, int idx, int p, TYPE v) {
      if(L == R) {
        node[idx] = v;
        return;
      }
      int now = (L + R) / 2;
      if(p <= now) update(L, now, idx * 2, p, v);
      else update(now + 1, R, idx * 2 + 1, p, v);
      pull(idx);
    }
  };

  void solve()
  {
    int n, m, k;
    cin >> n >> m >> k;
    vector<TYPE> v(n + 1);
    for(int i = 1; i <= n; i++) {
      int in;
      cin >> in;
      v[i] = {in, in, in};
    }
    segment_tree seg;
    seg.init(1, n, 1, v);
    for(int i = n; i >= m; i--) {
      // cerr << "-----\n";
      int j = 1;
      vector<int> tmp;
      while(j <= n) {
        int a = j + i - 1;
        while(a <= n && seg.query(1, n, 1, j, a).ans <= k) {
          a++;
        }
        a--;
        if(seg.query(1, n, 1, j, a).ans <= k) {
          tmp.push_back(a - j + 1);
          j = a + 1;
        }
        else {
          break;
        }
      }
      int ans = 0;
      for(int aa : tmp) ans += aa;
      if(ans == n) {
        cout << tmp.size() << '\n';
        for(int aa : tmp) {
          cout << aa << ' ';
        }
        cout << '\n';
        return;
      }
    }
    cout << "-1\n";
    return;
  }

  int main()
  {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    while(t--)
    {
      solve();
    }
    return 0;
  }
Back to top